Data.Graph.DGraph

DGraph data type

data DGraph v e

Directed Graph of Vertices in v and Arcs with attributes in e

Instances

Graph DGraph

Defined in Data.Graph.DGraph

Methods

empty :: Hashable v => DGraph v e

order :: DGraph v e -> Int

size :: (Hashable v, Eq v) => DGraph v e -> Int

density :: (Hashable v, Eq v) => DGraph v e -> Double

vertices :: DGraph v e -> [v]

edgeTriples :: (Hashable v, Eq v) => DGraph v e -> [(v, v, e)]

edgePairs :: (Hashable v, Eq v) => DGraph v e -> [(v, v)]

containsVertex :: (Hashable v, Eq v) => DGraph v e -> v -> Bool

areAdjacent :: (Hashable v, Eq v) => DGraph v e -> v -> v -> Bool

adjacentVertices :: (Hashable v, Eq v) => DGraph v e -> v -> [v]

adjacentVertices' :: (Hashable v, Eq v) => DGraph v e -> v -> [(v, v, e)]

reachableAdjacentVertices :: (Hashable v, Eq v) => DGraph v e -> v -> [v]

reachableAdjacentVertices' :: (Hashable v, Eq v) => DGraph v e -> v -> [(v, v, e)]

vertexDegree :: (Hashable v, Eq v) => DGraph v e -> v -> Int

degrees :: (Hashable v, Eq v) => DGraph v e -> [Int]

maxDegree :: (Hashable v, Eq v) => DGraph v e -> Int

minDegree :: (Hashable v, Eq v) => DGraph v e -> Int

avgDegree :: (Hashable v, Eq v) => DGraph v e -> Double

insertVertex :: (Hashable v, Eq v) => v -> DGraph v e -> DGraph v e

insertVertices :: (Hashable v, Eq v) => [v] -> DGraph v e -> DGraph v e

containsEdgePair :: (Hashable v, Eq v) => DGraph v e -> (v, v) -> Bool

incidentEdgeTriples :: (Hashable v, Eq v) => DGraph v e -> v -> [(v, v, e)]

incidentEdgePairs :: (Hashable v, Eq v) => DGraph v e -> v -> [(v, v)]

edgeTriple :: (Hashable v, Eq v) => DGraph v e -> v -> v -> Maybe (v, v, e)

insertEdgeTriple :: (Hashable v, Eq v) => (v, v, e) -> DGraph v e -> DGraph v e

insertEdgeTriples :: (Hashable v, Eq v) => [(v, v, e)] -> DGraph v e -> DGraph v e

insertEdgePair :: (Hashable v, Eq v) => (v, v) -> DGraph v () -> DGraph v ()

insertEdgePairs :: (Hashable v, Eq v) => [(v, v)] -> DGraph v () -> DGraph v ()

removeVertex :: (Hashable v, Eq v) => v -> DGraph v e -> DGraph v e

removeVertices :: (Hashable v, Eq v) => [v] -> DGraph v e -> DGraph v e

removeEdgePair :: (Hashable v, Eq v) => (v, v) -> DGraph v e -> DGraph v e

removeEdgePairs :: (Hashable v, Eq v) => [(v, v)] -> DGraph v e -> DGraph v e

removeEdgePairAndVertices :: (Hashable v, Eq v) => (v, v) -> DGraph v e -> DGraph v e

isolatedVertices :: (Hashable v, Eq v) => DGraph v e -> [v]

isSimple :: (Hashable v, Eq v) => DGraph v e -> Bool

union :: (Hashable v, Eq v) => DGraph v e -> DGraph v e -> DGraph v e

intersection :: (Hashable v, Eq v, Eq e) => DGraph v e -> DGraph v e -> DGraph v e

toList :: (Hashable v, Eq v) => DGraph v e -> [(v, [(v, e)])]

fromList :: (Hashable v, Eq v) => [(v, [(v, e)])] -> DGraph v e

fromAdjacencyMatrix :: [[Int]] -> Maybe (DGraph Int ())

(Hashable v, Eq v) => Functor (DGraph v)

Defined in Data.Graph.DGraph

Methods

fmap :: (a -> b) -> DGraph v a -> DGraph v b

(<$) :: a -> DGraph v b -> DGraph v a

(Hashable v, Eq v) => Foldable (DGraph v)

Defined in Data.Graph.DGraph

Methods

fold :: Monoid m => DGraph v m -> m

foldMap :: Monoid m => (a -> m) -> DGraph v a -> m

foldr :: (a -> b -> b) -> b -> DGraph v a -> b

foldr' :: (a -> b -> b) -> b -> DGraph v a -> b

foldl :: (b -> a -> b) -> b -> DGraph v a -> b

foldl' :: (b -> a -> b) -> b -> DGraph v a -> b

foldr1 :: (a -> a -> a) -> DGraph v a -> a

foldl1 :: (a -> a -> a) -> DGraph v a -> a

toList :: DGraph v a -> [a]

null :: DGraph v a -> Bool

length :: DGraph v a -> Int

elem :: Eq a => a -> DGraph v a -> Bool

maximum :: Ord a => DGraph v a -> a

minimum :: Ord a => DGraph v a -> a

sum :: Num a => DGraph v a -> a

product :: Num a => DGraph v a -> a

(Eq v, Eq e) => Eq (DGraph v e)

Defined in Data.Graph.DGraph

Methods

(==) :: DGraph v e -> DGraph v e -> Bool

(/=) :: DGraph v e -> DGraph v e -> Bool

(Hashable v, Eq v, Read v, Read e) => Read (DGraph v e)

Defined in Data.Graph.DGraph

Methods

readsPrec :: Int -> ReadS (DGraph v e)

readList :: ReadS [DGraph v e]

readPrec :: ReadPrec (DGraph v e)

readListPrec :: ReadPrec [DGraph v e]

(Hashable v, Eq v, Show v, Show e) => Show (DGraph v e)

Defined in Data.Graph.DGraph

Methods

showsPrec :: Int -> DGraph v e -> ShowS

show :: DGraph v e -> String

showList :: [DGraph v e] -> ShowS

Generic (DGraph v e)

Defined in Data.Graph.DGraph

Associated Types

type Rep (DGraph v e) :: Type -> Type

Methods

from :: DGraph v e -> Rep (DGraph v e) x

to :: Rep (DGraph v e) x -> DGraph v e

(Hashable v, Eq v) => Semigroup (DGraph v e)

Defined in Data.Graph.DGraph

Methods

(<>) :: DGraph v e -> DGraph v e -> DGraph v e

sconcat :: NonEmpty (DGraph v e) -> DGraph v e

stimes :: Integral b => b -> DGraph v e -> DGraph v e

(Hashable v, Eq v) => Monoid (DGraph v e)

Defined in Data.Graph.DGraph

Methods

mempty :: DGraph v e

mappend :: DGraph v e -> DGraph v e -> DGraph v e

mconcat :: [DGraph v e] -> DGraph v e

(Arbitrary v, Arbitrary e, Hashable v, Num v, Ord v) => Arbitrary (DGraph v e)

Defined in Data.Graph.DGraph

Methods

arbitrary :: Gen (DGraph v e)

shrink :: DGraph v e -> [DGraph v e]

(NFData v, NFData e) => NFData (DGraph v e)

Defined in Data.Graph.DGraph

Methods

rnf :: DGraph v e -> ()

type Rep (DGraph v e)

Defined in Data.Graph.DGraph

type Rep (DGraph v e)

Functions on DGraph

insertArc :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e

Insert a directed Arc into a DGraph

The involved vertices are inserted if they don't exist. If the graph already contains the Arc, its attribute gets updated

insertArcs :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e -> DGraph v e

Same as insertArc but for a list of Arcs

removeArc :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e

Remove the directed Arc from a DGraph if present. The involved vertices are left untouched

removeArcs :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e -> DGraph v e

Same as removeArc but for a list of Arcs

removeArcAndVertices :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e

Remove the directed Arc from a DGraph if present. The involved vertices also get removed

arcs :: forall v e. (Hashable v, Eq v) => DGraph v e -> [Arc v e]

Retrieve the Arcs of a DGraph

containsArc :: (Hashable v, Eq v) => DGraph v e -> Arc v e -> Bool

Tell if a directed Arc exists in the graph

inboundingArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e]

Retrieve the inbounding Arcs of a Vertex

outboundingArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e]

Retrieve the outbounding Arcs of a Vertex

incidentArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e]

Retrieve the incident Arcs of a Vertex

The incident arcs of a vertex are all the inbounding and outbounding arcs of the vertex

vertexIndegree :: (Hashable v, Eq v) => DGraph v e -> v -> Int

Indegree of a vertex

The indegree of a vertex is the number of inbounding Arcs to a vertex

vertexOutdegree :: (Hashable v, Eq v) => DGraph v e -> v -> Int

Outdegree of a vertex

The outdegree of a vertex is the number of outbounding Arcs from a vertex

indegrees :: (Hashable v, Eq v) => DGraph v e -> [Int]

Indegrees of all the vertices in a DGraph

outdegrees :: (Hashable v, Eq v) => DGraph v e -> [Int]

Outdegree of all the vertices in a DGraph

Query graph properties and characteristics

isBalanced :: (Hashable v, Eq v) => DGraph v e -> Bool

Tell if a DGraph is balanced

A directed graph is balanced when its indegree = outdegree

isSource :: (Hashable v, Eq v) => DGraph v e -> v -> Bool

Tell if a vertex is a source

A vertex is a source when its indegree = 0

isSink :: (Hashable v, Eq v) => DGraph v e -> v -> Bool

Tell if a vertex is a sink

A vertex is a sink when its outdegree = 0

isInternal :: (Hashable v, Eq v) => DGraph v e -> v -> Bool

Tell if a vertex is internal

A vertex is internal when its neither a source nor a sink

Transformations

transpose :: (Hashable v, Eq v) => DGraph v e -> DGraph v e

Get the transpose of a DGraph

The transpose of a directed graph is another directed graph where all of its arcs are reversed

toUndirected :: (Hashable v, Eq v) => DGraph v e -> UGraph v e

Convert a directed DGraph to an undirected UGraph by converting all of its Arcs into Edges

List conversions

toArcsList :: (Hashable v, Eq v) => DGraph v e -> [Arc v e]

Convert a DGraph to a list of Arcs discarding isolated vertices

Note that because toArcsList discards isolated vertices:

fromArcsList . toArcsList /= id

fromArcsList :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e

Construct a DGraph from a list of Arcs

Pretty printing

prettyPrint :: (Hashable v, Eq v, Show v, Show e) => DGraph v e -> String

Pretty print a DGraph