A wrapper around the types and functions from Data.Graph to make programming with them less painful. Also
implements some extra useful goodies such as `successors`

and `sccGraph`

, and improves the documentation of
the behaviour of some functions.

As it wraps Data.Graph, this module only supports directed graphs with unlabelled edges.

Incorporates code from the `containers`

package which is (c) The University of Glasgow 2002 and based
on code described in:

*Lazy Depth-First Search and Linear Graph Algorithms in Haskell*,
by David King and John Launchbury

- type Edge i = (i, i)
- data Graph i v
- vertex :: Ord i => Graph i v -> i -> v
- fromListSimple :: Ord v => [(v, [v])] -> Graph v v
- fromList :: Ord i => [(i, v, [i])] -> Graph i v
- fromListLenient :: Ord i => [(i, v, [i])] -> Graph i v
- fromListBy :: Ord i => (v -> i) -> [(v, [i])] -> Graph i v
- fromVerticesEdges :: Ord i => [(i, v)] -> [Edge i] -> Graph i v
- toList :: Ord i => Graph i v -> [(i, v, [i])]
- vertices :: Graph i v -> [i]
- edges :: Graph i v -> [Edge i]
- successors :: Ord i => Graph i v -> i -> [i]
- outdegree :: Ord i => Graph i v -> i -> Int
- indegree :: Ord i => Graph i v -> i -> Int
- transpose :: Graph i v -> Graph i v
- reachableVertices :: Ord i => Graph i v -> i -> [i]
- hasPath :: Ord i => Graph i v -> i -> i -> Bool
- topologicalSort :: Graph i v -> [i]
- depthNumbering :: Ord i => Graph i v -> [i] -> Graph i (v, Maybe Int)
- data SCC i
- = AcyclicSCC i
- | CyclicSCC [i]

- stronglyConnectedComponents :: Graph i v -> [SCC i]
- sccGraph :: Ord i => Graph i v -> Graph (Set i) (Map i v)

# Documentation

A directed graph

fromListSimple :: Ord v => [(v, [v])] -> Graph v vSource

Construct a `Graph`

where the vertex data double up as the indices.

Unlike `Data.Graph.graphFromEdges`

, vertex data that is listed as edges that are not actually themselves
present in the input list are reported as an error.

fromList :: Ord i => [(i, v, [i])] -> Graph i vSource

Construct a `Graph`

that contains the given vertex data, linked up according to the supplied index and edge list.

Unlike `Data.Graph.graphFromEdges`

, indexes in the edge list that do not correspond to the index of some item in the
input list are reported as an error.

fromListLenient :: Ord i => [(i, v, [i])] -> Graph i vSource

Construct a `Graph`

that contains the given vertex data, linked up according to the supplied index and edge list.

Like `Data.Graph.graphFromEdges`

, indexes in the edge list that do not correspond to the index of some item in the
input list are silently ignored.

fromListBy :: Ord i => (v -> i) -> [(v, [i])] -> Graph i vSource

Construct a `Graph`

that contains the given vertex data, linked up according to the supplied key extraction
function and edge list.

Unlike `Data.Graph.graphFromEdges`

, indexes in the edge list that do not correspond to the index of some item in the
input list are reported as an error.

fromVerticesEdges :: Ord i => [(i, v)] -> [Edge i] -> Graph i vSource

toList :: Ord i => Graph i v -> [(i, v, [i])]Source

Morally, the inverse of `fromList`

. The order of the elements in the output list is unspecified, as is the order of the edges
in each node's adjacency list. For this reason, `toList . fromList`

is not necessarily the identity function.

successors :: Ord i => Graph i v -> i -> [i]Source

Find the vertices we can reach from a vertex with the given indentity

transpose :: Graph i v -> Graph i vSource

The graph formed by flipping all the edges, so edges from i to j now go from j to i

reachableVertices :: Ord i => Graph i v -> i -> [i]Source

List all of the vertices reachable from the given starting point

hasPath :: Ord i => Graph i v -> i -> i -> BoolSource

Is the second vertex reachable by following edges from the first vertex?

It is worth sharing a partial application of `hasPath`

to the first vertex if you are testing for several
vertices being reachable from it.

topologicalSort :: Graph i v -> [i]Source

Topological sort of of the graph (http://en.wikipedia.org/wiki/Topological_sort). If the graph is acyclic, vertices will only appear in the list once all of those vertices with arrows to them have already appeared.

Vertex *i* precedes *j* in the output whenever *j* is reachable from *i* but not vice versa.

depthNumbering :: Ord i => Graph i v -> [i] -> Graph i (v, Maybe Int)Source

Number the vertices in the graph by how far away they are from the given roots. The roots themselves have depth 0,
and every subsequent link we traverse adds 1 to the depth. If a vertex is not reachable it will have a depth of `Nothing`

.

AcyclicSCC i | |

CyclicSCC [i] |

stronglyConnectedComponents :: Graph i v -> [SCC i]Source

Strongly connected components (http://en.wikipedia.org/wiki/Strongly_connected_component).

The SCCs are listed in a *reverse topological order*. That is to say, any edges *to* a node in the SCC originate either *from*:

1) Within the SCC itself (in the case of a `CyclicSCC`

only)
2) Or from a node in a SCC later on in the list

Vertex *i* strictly precedes *j* in the output whenever *i* is reachable from *j* but not vice versa.
Vertex *i* occurs in the same SCC as *j* whenever both *i* is reachable from *j* and *j* is reachable from *i*.