type Graph = Array Vertex [Vertex]
Adjacency list representation of a graph, mapping each vertex to its list of successors.
The type is an adjacency list representation of a finite, directed
graph with vertices of type GraphInt.
The type represents a
strongly-connected component
of a graph.SCC
The implementation is based on
David King and John Launchbury, "Structuring Depth-First Search Algorithms in Haskell", Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 344-354, 1995, https://doi.org/10.1145/199448.199530.
type Graph = Array Vertex [Vertex]Adjacency list representation of a graph, mapping each vertex to its list of successors.
type Bounds = (Vertex, Vertex)The bounds of an Array.
type Edge = (Vertex, Vertex)An edge from the first vertex to the second.
type Vertex = IntAbstract representation of vertices.
type Table a = Array Vertex aTable indexed by a contiguous set of vertices.
Note: This is included for backwards compatibility.
graphFromEdges :: Ord key => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key]), key -> Maybe Vertex)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.
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 == ("a",'a',"b")
vertexFromKey 'a' == Just 0Get the label for a given key.
let getNodePart (n, _, _) = n
(graph, nodeFromVertex, vertexFromKey) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c']), ("c", 'c', [])]
getNodePart . nodeFromVertex <$> vertexFromKey 'a' == Just "A"graphFromEdges' :: Ord key => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key]))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.
buildG :: Bounds -> [Edge] -> GraphO(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.
buildG (0,-1) [] == array (0,-1) []
buildG (0,2) [(0,1), (1,2)] == array (0,1) [(0,[1]),(1,[2])]
buildG (0,2) [(0,1), (0,2), (1,2)] == array (0,2) [(0,[2,1]),(1,[2]),(2,[])]vertices :: Graph -> [Vertex]O(V). Returns the list of vertices in the graph.
vertices (buildG (0,-1) []) == []vertices (buildG (0,2) [(0,1),(1,2)]) == [0,1,2]edges :: Graph -> [Edge]O(V+E). Returns the list of edges in the graph.
edges (buildG (0,-1) []) == []edges (buildG (0,2) [(0,1),(1,2)]) == [(0,1),(1,2)]outdegree :: Graph -> Array Vertex IntO(V+E). A table of the count of edges from each node.
outdegree (buildG (0,-1) []) == array (0,-1) []outdegree (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,1),(1,1),(2,0)]indegree :: Graph -> Array Vertex IntO(V+E). A table of the count of edges into each node.
indegree (buildG (0,-1) []) == array (0,-1) []indegree (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,0),(1,1),(2,1)]transposeG :: Graph -> GraphO(V+E). The graph obtained by reversing all edges.
transposeG (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,[]),(1,[0]),(2,[1])]dfs :: Graph -> [Vertex] -> [Tree Vertex]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.
dff :: Graph -> [Tree Vertex]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.
topSort :: Graph -> [Vertex]O(V+E). A topological sort of the graph.
The order is partially specified by the condition that a vertex i
precedes j whenever j is reachable from i but not vice versa.
Note: A topological sort exists only when there are no cycles in the graph.
If the graph has cycles, the output of this function will not be a
topological sort. In such a case consider using scc.
reverseTopSort :: Graph -> [Vertex]O(V+E). Reverse ordering of `topSort`.
See note in topSort.
components :: Graph -> [Tree Vertex]O(V+E). The connected components of a graph.
Two vertices are connected if there is a path between them, traversing
edges in either direction.
scc :: Graph -> [Tree Vertex]O(V+E). The strongly connected components of a graph, in reverse
topological order.
scc (buildG (0,3) [(3,1),(1,2),(2,0),(0,1)])
== [Node {rootLabel = 0, subForest = [Node {rootLabel = 1, subForest = [Node {rootLabel = 2, subForest = []}]}]}
,Node {rootLabel = 3, subForest = []}]bcc :: Graph -> [Tree [Vertex]]O(V+E). The biconnected components of a graph.
An undirected graph is biconnected if the deletion of any vertex
leaves it connected.
The input graph is expected to be undirected, i.e. for every edge in the graph the reverse edge is also in the graph. If the graph is not undirected the output is arbitrary.
reachable :: Graph -> Vertex -> [Vertex]O(V+E). Returns the list of vertices reachable from a given vertex.
reachable (buildG (0,0) []) 0 == [0]reachable (buildG (0,2) [(0,1), (1,2)]) 0 == [0,1,2]path :: Graph -> Vertex -> Vertex -> BoolO(V+E). Returns True if the second vertex reachable from the first.
path (buildG (0,0) []) 0 0 == Truepath (buildG (0,2) [(0,1), (1,2)]) 0 2 == Truepath (buildG (0,2) [(0,1), (1,2)]) 2 0 == FalseCyclicSCC :: [vertex] -> SCC vertexPartial pattern synonym for backward compatibility with containers < 0.7.
data SCC vertexStrongly connected component.
AcyclicSCC :: vertex -> SCC vertexvertexA single vertex that is not in any cycle.
NECyclicSCC :: (NonEmpty vertex) -> SCC vertex(NonEmpty vertex)A maximal set of mutually reachable vertices.
stronglyConnComp :: Ord key => [(node, key, [key])] -> [SCC node]O((V+E) \log V). 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"][(node, key, [key])]The graph: a list of nodes uniquely identified by keys, with a list of keys of nodes this node has edges to. The out-list may contain keys that don't correspond to nodes of the graph; such edges are ignored.
stronglyConnCompR :: Ord key => [(node, key, [key])] -> [SCC (node, key, [key])]O((V+E) \log V). 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])][(node, key, [key])]The graph: a list of nodes uniquely identified by keys, with a list of keys of nodes this node has edges to. The out-list may contain keys that don't correspond to nodes of the graph; such edges are ignored.
[SCC (node, key, [key])]Reverse topologically sorted
flattenSCC :: SCC vertex -> [vertex]The vertices of a strongly connected component.
flattenSCC = .toList . flattenSCC1
This function is retained for backward compatibility,
flattenSCC1 has the more precise type.
flattenSCC1 :: SCC vertex -> NonEmpty vertexThe vertices of a strongly connected component.
flattenSCCs :: [SCC a] -> [a]The vertices of a list of strongly connected components.
data Tree aNon-empty, possibly infinite, multi-way trees; also known as rose trees.
Node :: a -> [Tree a] -> Tree arootLabel :: Tree a -> alabel value
subForest :: Tree a -> [Tree a]zero or more child trees
type Forest a = [Tree a]This type synonym exists primarily for historical reasons.
instance Eq vertex => Eq (SCC vertex)instance Show vertex => Show (SCC vertex)instance Read vertex => Read (SCC vertex)instance Data vertex => Data (SCC vertex)instance Generic1 SCCinstance Generic (SCC vertex)instance Lift vertex => Lift (SCC vertex)instance Eq1 SCCinstance Show1 SCCinstance Read1 SCCinstance F.Foldable SCCinstance F1.Foldable1 SCCinstance Traversable SCCinstance NFData a => NFData (SCC a)instance NFData1 SCCinstance Functor SCCCommunity contribution. The service has not verified this documentation. The generator reported 15 diagnostics.
Target: Linux on x86-64. Some inferred types and resolved links are not available.
Generator: aihc-haddock-aa6debbd-web-3
Metadata snapshot: 634f718c0d8cd970c4e2c511d2345d8fd36c6dc32b06343c2b4e914ffccbce7f
Open the dependency plan · Download the documentation model