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


-- | Exposes things that are considered to be too unstable for inclusion in
--   the exports of <a>Data.Graph.Wrapper</a>.
--   
--   Use of this module should be avoided as it will change frequently and
--   changes to this module alone will not necessarily follow the Package
--   Versioning Policy.
module Data.Graph.Wrapper.Internal

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

-- | A directed graph
data Graph i v
G :: Graph -> Array Vertex i -> Array Vertex v -> Graph i v
graph :: Graph i v -> Graph
indexGVertexArray :: Graph i v -> Array Vertex i
gVertexVertexArray :: Graph i v -> Array Vertex v
traverseWithKey :: Applicative t => (i -> a -> t b) -> Graph i a -> t (Graph i b)
indexGVertex :: Ord i => Graph i v -> i -> Vertex
gVertexIndex :: Graph i v -> Vertex -> i
gVertexVertex :: Graph i v -> Vertex -> v

-- | Retrieve data associated with the vertex
vertex :: Ord i => Graph i v -> i -> v
indexGVertex' :: Ord i => Array Vertex i -> i -> Vertex
indexGVertex'_maybe :: Ord i => Array Vertex i -> i -> Maybe Vertex

-- | 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]
instance Traversable (Graph i)
instance Foldable (Graph i)
instance Functor (Graph i)
instance (Ord i, Show i, Show v) => Show (Graph i v)


-- | 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 <a>graphFromEdges</a>, 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 <a>graphFromEdges</a>, 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 index and edge list.
--   
--   Like <a>graphFromEdges</a>, indexes in the edge list that do not
--   correspond to the index of some item in the input list are silently
--   ignored.
fromListLenient :: 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 <a>graphFromEdges</a>, 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

-- | Morally, the inverse of <a>fromList</a>. 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, <tt>toList . fromList</tt> is
--   not necessarily the identity function.
toList :: Ord i => Graph i v -> [(i, v, [i])]

-- | 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?
--   
--   It is worth sharing a partial application of <a>hasPath</a> to the
--   first vertex if you are testing for several vertices being reachable
--   from it.
hasPath :: Ord i => Graph i v -> i -> 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>i</i> precedes <i>j</i> in the output whenever <i>j</i> is
--   reachable from <i>i</i> but not vice versa.
topologicalSort :: Graph i v -> [i]

-- | 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 <a>Nothing</a>.
depthNumbering :: Ord i => Graph i v -> [i] -> Graph i (v, Maybe Int)
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>i</i> strictly precedes <i>j</i> in the output whenever
--   <i>i</i> is reachable from <i>j</i> but not vice versa. Vertex
--   <i>i</i> occurs in the same SCC as <i>j</i> whenever both <i>i</i> is
--   reachable from <i>j</i> and <i>j</i> is reachable from <i>i</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)
traverseWithKey :: Applicative t => (i -> a -> t b) -> Graph i a -> t (Graph i b)
instance Show i => Show (SCC i)
instance Traversable SCC
instance Foldable SCC
instance Functor SCC