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

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

Contents | |||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

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

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