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

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

toAdjacencyMatrix :: DGraph v e -> [[Int]]

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

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

Methods

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

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

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

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 e, Eq v) => Eq (DGraph v e)

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)

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)

Methods

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

show :: DGraph v e -> String

showList :: [DGraph v e] -> ShowS

Generic (DGraph v e)

Associated Types

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

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)

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)

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)

Methods

arbitrary :: Gen (DGraph v e)

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

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

Methods

rnf :: DGraph v e -> ()

type Rep (DGraph v e)

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

isSymmetric :: DGraph v e -> Bool

Tell if a DGraph is symmetric

A directed graph is symmetric if all of its Arcs are bi-directed

isOriented :: DGraph v e -> Bool

Tell if a DGraph is oriented

A directed graph is oriented if there are none bi-directed Arcs

Note: This is not the opposite of isSymmetric

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

Tell if a DGraph is balanced

A directed graph is balanced when its indegree = outdegree

isRegular :: DGraph v e -> Bool

Tell if a DGraph is regular

A directed graph is regular when all of its vertices have the same number of adjacent vertices AND when the indegree and outdegree of each vertex are equal to each other.

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