| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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