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
- fromListBy :: Ord i => (v -> i) -> [(v, [i])] -> Graph i v
- fromVerticesEdges :: Ord i => [(i, v)] -> [Edge i] -> Graph i v
- 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 -> Edge i -> Bool
- topologicalSort :: Graph i v -> [i]
- 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.

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

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 -> Edge i -> BoolSource

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

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.

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.