-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A wrapper around the standard Data.Graph with a less awkward interface
--   
--   A wrapper around the standard Data.Graph with a less awkward interface
@package graph-wrapper
@version 0.1


-- | A wrapper around the types and functions from <a>Data.Graph</a> to
--   make programming with them less painful. Also implements some extra
--   useful goodies such as <a>successors</a> and <a>sccGraph</a>, and
--   improves the documentation of the behaviour of some functions.
--   
--   As it wraps <a>Data.Graph</a>, this module only supports directed
--   graphs with unlabelled edges.
--   
--   Incorporates code from the <tt>containers</tt> package which is (c)
--   The University of Glasgow 2002 and based on code described in:
--   
--   <i>Lazy Depth-First Search and Linear Graph Algorithms in Haskell</i>,
--   by David King and John Launchbury
module Data.Graph.Wrapper

-- | An edge from the first vertex to the second
type Edge i = (i, i)

-- | A directed graph
data Graph i v

-- | Retrieve data associated with the vertex
vertex :: (Ord i) => Graph i v -> i -> v

-- | Construct a <a>Graph</a> where the vertex data double up as the
--   indices.
--   
--   Unlike <tt>Data.Graph.graphFromEdges</tt>, vertex data that is listed
--   as edges that are not actually themselves present in the input list
--   are reported as an error.
fromListSimple :: (Ord v) => [(v, [v])] -> Graph v v

-- | Construct a <a>Graph</a> that contains the given vertex data, linked
--   up according to the supplied index and edge list.
--   
--   Unlike <tt>Data.Graph.graphFromEdges</tt>, indexes in the edge list
--   that do not correspond to the index of some item in the input list are
--   reported as an error.
fromList :: (Ord i) => [(i, v, [i])] -> Graph i v

-- | Construct a <a>Graph</a> that contains the given vertex data, linked
--   up according to the supplied key extraction function and edge list.
--   
--   Unlike <tt>Data.Graph.graphFromEdges</tt>, 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 v

-- | Construct a <a>Graph</a> directly from a list of vertices (and vertex
--   data).
--   
--   If either end of an <a>Edge</a> does not correspond to a supplied
--   vertex, an error will be raised.
fromVerticesEdges :: (Ord i) => [(i, v)] -> [Edge i] -> Graph i v

-- | Exhaustive list of vertices in the graph
vertices :: Graph i v -> [i]

-- | Exhaustive list of edges in the graph
edges :: Graph i v -> [Edge i]

-- | Find the vertices we can reach from a vertex with the given indentity
successors :: (Ord i) => Graph i v -> i -> [i]

-- | Number of edges going out of the vertex.
--   
--   It is worth sharing a partial application of <a>outdegree</a> to the
--   <a>Graph</a> argument if you intend to query for the outdegrees of a
--   number of vertices.
outdegree :: (Ord i) => Graph i v -> i -> Int

-- | Number of edges going in to the vertex.
--   
--   It is worth sharing a partial application of <a>indegree</a> to the
--   <a>Graph</a> argument if you intend to query for the indegrees of a
--   number of vertices.
indegree :: (Ord i) => Graph i v -> i -> Int

-- | The graph formed by flipping all the edges, so edges from i to j now
--   go from j to i
transpose :: Graph i v -> Graph i v

-- | List all of the vertices reachable from the given starting point
reachableVertices :: (Ord i) => Graph i v -> i -> [i]

-- | Is the second vertex reachable by following edges from the first
--   vertex?
hasPath :: (Ord i) => Graph i v -> Edge i -> Bool

-- | Topological sort of of the graph
--   (<a>http://en.wikipedia.org/wiki/Topological_sort</a>). 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.
topologicalSort :: Graph i v -> [i]
data SCC i
AcyclicSCC :: i -> SCC i
CyclicSCC :: [i] -> SCC i

-- | Strongly connected components
--   (<a>http://en.wikipedia.org/wiki/Strongly_connected_component</a>).
--   
--   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 <a>CyclicSCC</a> 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.
stronglyConnectedComponents :: Graph i v -> [SCC i]

-- | 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.
sccGraph :: (Ord i) => Graph i v -> Graph (Set i) (Map i v)
instance (Show i) => Show (SCC i)
instance Traversable SCC
instance Foldable SCC
instance Functor SCC
instance Traversable (Graph i)
instance Foldable (Graph i)
instance Functor (Graph i)
instance (Ord i, Show i, Show v) => Show (Graph i v)