GraphSCC-1.0.4: Tarjan's algorithm for computing the strongly connected components of a graph.
Safe HaskellSafe
LanguageHaskell98

Data.Graph.SCC

Synopsis
  • scc :: Graph -> ([(Int, [Vertex])], Vertex -> Int)
  • sccList :: Graph -> [SCC Vertex]
  • sccListR :: Graph -> [SCC (Vertex, [Vertex])]
  • sccGraph :: Graph -> [(SCC Int, Int, [Int])]
  • stronglyConnComp :: Ord key => [(node, key, [key])] -> [SCC node]
  • stronglyConnCompR :: Ord key => [(node, key, [key])] -> [SCC (node, key, [key])]

Documentation

scc :: Graph -> ([(Int, [Vertex])], Vertex -> Int) Source #

Computes the strongly connected components (SCCs) of the graph in O(vertices) time. The resulting tuple contains:

  • A (reversed) topologically sorted list of SCCs. Each SCCs is assigned a unique identifier of type Int.
  • An O(1) mapping from vertices in the original graph to the identifier of their SCC. This mapping will raise an "out of bounds" exception if it is applied to integers that do not correspond to vertices in the input graph.

This function assumes that the adjacency lists in the original graph mention only nodes that are in the graph. Violating this assumption will result in "out of bounds" array exception.

sccList :: Graph -> [SCC Vertex] Source #

Compute the list of strongly connected components of a graph. The components are topologically sorted: if v1 in C1 points to v2 in C2, then C2 will come before C1 in the list.

sccListR :: Graph -> [SCC (Vertex, [Vertex])] Source #

Compute the list of strongly connected components of a graph. Each component contains the adjecency information from the original graph. The components are topologically sorted: if v1 in C1 points to v2 in C2, then C2 will come before C1 in the list.

sccGraph :: Graph -> [(SCC Int, Int, [Int])] Source #

Quotient a graph with the relation that relates vertices that belong to the same SCC. The vertices in the new graph are the SCCs of the old graph, and there is an edge between two components, if there is an edge between any of their vertices. The entries in the resulting list are in reversed-topologically sorted: if v1 in C1 points to v2 in C2, then C1 will come before C2 in the list.

stronglyConnComp :: Ord key => [(node, key, [key])] -> [SCC node] Source #

stronglyConnCompR :: Ord key => [(node, key, [key])] -> [SCC (node, key, [key])] Source #