graph-wrapper-0.2.6.0: A wrapper around the standard Data.Graph with a less awkward interface

Data.Graph.Wrapper

Description

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

Synopsis

# Documentation

type Edge i = (i, i) Source #

An edge from the first vertex to the second

data Graph i v Source #

A directed graph

Instances
 Functor (Graph i) Source # Instance detailsDefined in Data.Graph.Wrapper.Internal Methodsfmap :: (a -> b) -> Graph i a -> Graph i b #(<$) :: a -> Graph i b -> Graph i a # Source # Instance detailsDefined in Data.Graph.Wrapper.Internal Methodsfold :: Monoid m => Graph i m -> m #foldMap :: Monoid m => (a -> m) -> Graph i a -> m #foldr :: (a -> b -> b) -> b -> Graph i a -> b #foldr' :: (a -> b -> b) -> b -> Graph i a -> b #foldl :: (b -> a -> b) -> b -> Graph i a -> b #foldl' :: (b -> a -> b) -> b -> Graph i a -> b #foldr1 :: (a -> a -> a) -> Graph i a -> a #foldl1 :: (a -> a -> a) -> Graph i a -> a #toList :: Graph i a -> [a] #null :: Graph i a -> Bool #length :: Graph i a -> Int #elem :: Eq a => a -> Graph i a -> Bool #maximum :: Ord a => Graph i a -> a #minimum :: Ord a => Graph i a -> a #sum :: Num a => Graph i a -> a #product :: Num a => Graph i a -> a # Source # Instance detailsDefined in Data.Graph.Wrapper.Internal Methodstraverse :: Applicative f => (a -> f b) -> Graph i a -> f (Graph i b) #sequenceA :: Applicative f => Graph i (f a) -> f (Graph i a) #mapM :: Monad m => (a -> m b) -> Graph i a -> m (Graph i b) #sequence :: Monad m => Graph i (m a) -> m (Graph i a) # (Ord i, Eq v) => Eq (Graph i v) Source # Instance detailsDefined in Data.Graph.Wrapper.Internal Methods(==) :: Graph i v -> Graph i v -> Bool #(/=) :: Graph i v -> Graph i v -> Bool # (Ord i, Show i, Show v) => Show (Graph i v) Source # Instance detailsDefined in Data.Graph.Wrapper.Internal MethodsshowsPrec :: Int -> Graph i v -> ShowS #show :: Graph i v -> String #showList :: [Graph i v] -> ShowS # vertex :: Ord i => Graph i v -> i -> v Source # Retrieve data associated with the vertex fromListSimple :: Ord v => [(v, [v])] -> Graph v v Source # Construct a Graph where the vertex data double up as the indices. Unlike 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 v Source # Construct a Graph that contains the given vertex data, linked up according to the supplied index and edge list. Unlike 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 v Source # Construct a Graph that contains the given vertex data, linked up according to the supplied index and edge list. Like 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 v Source # Construct a Graph that contains the given vertex data, linked up according to the supplied key extraction function and edge list. Unlike 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 v Source # Construct a Graph directly from a list of vertices (and vertex data). If either end of an Edge does not correspond to a supplied vertex, an error will be raised. 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. vertices :: Graph i v -> [i] Source # Exhaustive list of vertices in the graph edges :: Graph i v -> [Edge i] Source # Exhaustive list of edges in the graph successors :: Ord i => Graph i v -> i -> [i] Source # Find the vertices we can reach from a vertex with the given indentity outdegree :: Ord i => Graph i v -> i -> Int Source # Number of edges going out of the vertex. It is worth sharing a partial application of outdegree to the Graph argument if you intend to query for the outdegrees of a number of vertices. indegree :: Ord i => Graph i v -> i -> Int Source # Number of edges going in to the vertex. It is worth sharing a partial application of indegree to the Graph argument if you intend to query for the indegrees of a number of vertices. transpose :: Graph i v -> Graph i v Source # 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 -> Bool Source # 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. data SCC i Source # Constructors  AcyclicSCC i CyclicSCC [i] Instances  Source # Instance detailsDefined in Data.Graph.Wrapper Methodsfmap :: (a -> b) -> SCC a -> SCC b #(<$) :: a -> SCC b -> SCC a # Source # Instance detailsDefined in Data.Graph.Wrapper Methodsfold :: Monoid m => SCC m -> m #foldMap :: Monoid m => (a -> m) -> SCC a -> m #foldr :: (a -> b -> b) -> b -> SCC a -> b #foldr' :: (a -> b -> b) -> b -> SCC a -> b #foldl :: (b -> a -> b) -> b -> SCC a -> b #foldl' :: (b -> a -> b) -> b -> SCC a -> b #foldr1 :: (a -> a -> a) -> SCC a -> a #foldl1 :: (a -> a -> a) -> SCC a -> a #toList :: SCC a -> [a] #null :: SCC a -> Bool #length :: SCC a -> Int #elem :: Eq a => a -> SCC a -> Bool #maximum :: Ord a => SCC a -> a #minimum :: Ord a => SCC a -> a #sum :: Num a => SCC a -> a #product :: Num a => SCC a -> a # Source # Instance detailsDefined in Data.Graph.Wrapper Methodstraverse :: Applicative f => (a -> f b) -> SCC a -> f (SCC b) #sequenceA :: Applicative f => SCC (f a) -> f (SCC a) #mapM :: Monad m => (a -> m b) -> SCC a -> m (SCC b) #sequence :: Monad m => SCC (m a) -> m (SCC a) # Show i => Show (SCC i) Source # Instance detailsDefined in Data.Graph.Wrapper MethodsshowsPrec :: Int -> SCC i -> ShowS #show :: SCC i -> String #showList :: [SCC i] -> ShowS #

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.

sccGraph :: Ord i => Graph i v -> Graph (Set i) (Map i v) Source #

The graph formed by the strongly connected components of the input graph. Each node in the resulting graph is indexed by the set of vertex indices from the input graph that it contains.

traverseWithKey :: Applicative t => (i -> a -> t b) -> Graph i a -> t (Graph i b) Source #