| ||||||||

| ||||||||

| ||||||||

Description | ||||||||

A version of the graph algorithms described in:
| ||||||||

Synopsis | ||||||||

External interface | ||||||||

stronglyConnComp | ||||||||

| ||||||||

stronglyConnCompR | ||||||||

| ||||||||

data SCC vertex | ||||||||

| ||||||||

flattenSCC :: SCC vertex -> [vertex] | ||||||||

The vertices of a strongly connected component. | ||||||||

flattenSCCs :: [SCC a] -> [a] | ||||||||

The vertices of a list of strongly connected components. | ||||||||

Graphs | ||||||||

type Graph = Table [Vertex] | ||||||||

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

type Table a = Array Vertex a | ||||||||

Table indexed by a contiguous set of vertices. | ||||||||

type Bounds = (Vertex, Vertex) | ||||||||

The bounds of a Table.
| ||||||||

type Edge = (Vertex, Vertex) | ||||||||

An edge from the first vertex to the second. | ||||||||

type Vertex = Int | ||||||||

Abstract representation of vertices. | ||||||||

Building graphs | ||||||||

graphFromEdges :: Ord key => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key]), key -> Maybe Vertex) | ||||||||

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. The out-list may contain keys that don't correspond to nodes of the graph; they are ignored. | ||||||||

graphFromEdges' :: Ord key => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key])) | ||||||||

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] -> Graph | ||||||||

Build a graph from a list of edges. | ||||||||

transposeG :: Graph -> Graph | ||||||||

The graph obtained by reversing all edges. | ||||||||

Graph properties | ||||||||

vertices :: Graph -> [Vertex] | ||||||||

All vertices of a graph. | ||||||||

edges :: Graph -> [Edge] | ||||||||

All edges of a graph. | ||||||||

outdegree :: Graph -> Table Int | ||||||||

A table of the count of edges from each node. | ||||||||

indegree :: Graph -> Table Int | ||||||||

A table of the count of edges into each node. | ||||||||

Algorithms | ||||||||

dfs :: Graph -> [Vertex] -> Forest Vertex | ||||||||

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 -> Forest Vertex | ||||||||

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] | ||||||||

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.
| ||||||||

components :: Graph -> Forest Vertex | ||||||||

The connected components of a graph. Two vertices are connected if there is a path between them, traversing edges in either direction. | ||||||||

scc :: Graph -> Forest Vertex | ||||||||

The strongly connected components of a graph. | ||||||||

bcc :: Graph -> Forest [Vertex] | ||||||||

The biconnected components of a graph. An undirected graph is biconnected if the deletion of any vertex leaves it connected. | ||||||||

reachable :: Graph -> Vertex -> [Vertex] | ||||||||

A list of vertices reachable from a given vertex. | ||||||||

path :: Graph -> Vertex -> Vertex -> Bool | ||||||||

Is the second vertex reachable from the first? | ||||||||

module Data.Tree | ||||||||

Produced by Haddock version 0.7 |