Adjacency list representation of a graph, mapping each vertex to its list of successors.

The bounds of an @Array@.

An edge from the first vertex to the second.

Abstract representation of vertices.

Table indexed by a contiguous set of vertices.

(O((V+E) \log V)). Build a graph from a list of nodes uniquely identified by keys, with a list of keys of nodes this node should have edges to.

This function takes an adjacency list representing a graph with vertices of type @key@ labeled by values of type @node@ and produces a @Graph@-based representation of that list. The @Graph@ result represents the /shape/ of the graph, and the functions describe a) how to retrieve the label and adjacent vertices of a given vertex, and b) how to retrieve a vertex given a key.

@(graph, nodeFromVertex, vertexFromKey) = graphFromEdges edgeList@

• @graph :: Graph@ is the raw, array based adjacency list for the graph.
• @nodeFromVertex :: Vertex -> (node, key, [key])@ returns the node associated with the given 0-based @Int@ vertex; see /warning/ below. This runs in (O(1)) time.
• @vertexFromKey :: key -> Maybe Vertex@ returns the @Int@ vertex for the key if it exists in the graph, @Nothing@ otherwise. This runs in (O(\log V)) time.

To safely use this API you must either extract the list of vertices directly from the graph or first call @vertexFromKey k@ to check if a vertex corresponds to the key @k@. Once it is known that a vertex exists you can use @nodeFromVertex@ to access the labelled node and adjacent vertices. See below for examples.

Note: The out-list may contain keys that don't correspond to nodes of the graph; they are ignored.

Warning: The @nodeFromVertex@ function will cause a runtime exception if the given @Vertex@ does not exist.

==== Examples

An empty graph.

(graph, nodeFromVertex, vertexFromKey) = graphFromEdges [] graph = array (0,-1) []

A graph where the out-list references unspecified nodes (@'c'@), these are ignored.

(graph, _, _) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c'])] array (0,1) [(0,[1]),(1,[])]

A graph with 3 vertices: ("a") -> ("b") -> ("c")

(graph, nodeFromVertex, vertexFromKey) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c']), ("c", 'c', [])] graph == array (0,2) [(0,[1]),(1,[2]),(2,[])] nodeFromVertex 0 == Just ("a",'a',['b']) vertexFromKey 'a' == Just 0

Get the label for a given key.

let getNodePart (n, _, _) = n (graph, nodeFromVertex, vertexFromKey) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c']), ("c", 'c', [])] Maybe.andThen (Maybe.map getNodePart << nodeFromVertex) (vertexFromKey 'a') == Just "A"

(O((V+E) \log V)). Identical to 'graphFromEdges', except that the return value does not include the function which maps keys to vertices. This version of 'graphFromEdges' is for backwards compatibility.

(O(V+E)). Build a graph from a list of edges.

Warning: This function will cause a runtime exception if a vertex in the edge list is not within the given @Bounds@.

==== Examples

buildG (0,-1) [] == array (0,-1) [] buildG (0,2) [(0,1), (1,2)] == array (0,2) [(0,[1]),(1,[2]),(2,[])] buildG (0,2) [(0,1), (0,2), (1,2)] == array (0,2) [(0,[2,1]),(1,[2]),(2,[])]

(O(V)). Returns the list of vertices in the graph.

==== Examples

vertices (buildG (0,-1) []) == []

vertices (buildG (0,2) [(0,1),(1,2)]) == [0,1,2]

(O(V+E)). Returns the list of edges in the graph.

==== Examples

edges (buildG (0,-1) []) == []

edges (buildG (0,2) [(0,1),(1,2)]) == [(0,1),(1,2)]

(O(V+E)). A table of the count of edges from each node.

==== Examples

outdegree (buildG (0,-1) []) == array (0,-1) []

outdegree (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,1),(1,1),(2,0)]

(O(V+E)). A table of the count of edges into each node.

==== Examples

indegree (buildG (0,-1) []) == array (0,-1) []

indegree (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,0),(1,1),(2,1)]

(O(V+E)). The graph obtained by reversing all edges.

==== Examples

transposeG (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,[]),(1,[0]),(2,[1])]

(O(V+E)). A spanning forest of the part of the graph reachable from the listed vertices, obtained from a depth-first search of the graph starting at each of the listed vertices in order.

This function deviates from King and Launchbury's implementation by bundling together the functions generate, prune, and chop for efficiency reasons.

This diverges from the original Haskell implementation by using a stack instead of SetM monadic structure. This allows the function to be non-recursive and thus more efficient.

(O(V+E)). A spanning forest of the graph, obtained from a depth-first search of the graph starting from each vertex in an unspecified order.

The strongly connected components of a graph, in reverse topological order.

scc (buildG ( 0, 3 ) [ ( 3, 1 ), ( 1, 2 ), ( 2, 0 ), ( 0, 1 ) ])
    == [ Tree.tree 0 [ Tree.tree 1 [ Tree.tree 2 [] ] ]
       , Tree.tree 3 []
       ]

Strongly connected component.

The strongly connected components of a directed graph, reverse topologically sorted.

stronglyConnComp [ ( "a", 0, [ 1 ] ), ( "b", 1, [ 2, 3 ] ), ( "c", 2, [ 1 ] ), ( "d", 3, [ 3 ] ) ]
    == [ CyclicSCC [ "d" ], CyclicSCC [ "b", "c" ], AcyclicSCC "a" ]

The strongly connected components of a directed graph, reverse topologically sorted. The function is the same as 'stronglyConnComp', except that all the information about each node retained. This interface is used when you expect to apply 'SCC' to (some of) the result of 'SCC', so you don't want to lose the dependency information.

stronglyConnCompR [ ( "a", 0, [ 1 ] ), ( "b", 1, [ 2, 3 ] ), ( "c", 2, [ 1 ] ), ( "d", 3, [ 3 ] ) ]
    == [ CyclicSCC [ ( "d", 3, [ 3 ] ) ], CyclicSCC [ ( "b", 1, [ 2, 3 ] ), ( "c", 2, [ 1 ] ) ], AcyclicSCC ( "a", 0, [ 1 ] ) ]

The vertices of a strongly connected component.

The vertices of a list of strongly connected components.

Array structure