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


-- | Martin Erwig's Functional Graph Library
--   
--   Martin Erwig's Functional Graph Library
@package fgl
@version 5.4.2.2


-- | Threading Combinators.
module Data.Graph.Inductive.Internal.Thread
type Split t i r = i -> t -> (r, t)
type SplitM t i r = Split t i (Maybe r)
type Thread t i r = (t, Split t i r)
type Collect r c = (r -> c -> c, c)
threadList' :: (Collect r c) -> (Split t i r) -> [i] -> t -> (c, t)
threadList :: (Collect r c) -> (Split t i r) -> [i] -> t -> (c, t)
threadMaybe' :: (r -> a) -> Split t i r -> Split t j (Maybe i) -> Split t j (Maybe a)
threadMaybe :: (i -> r -> a) -> Split t i r -> SplitM t j i -> SplitM t j a
splitPar :: Split t i r -> Split u j s -> Split (t, u) (i, j) (r, s)
splitParM :: SplitM t i r -> Split u j s -> SplitM (t, u) (i, j) (r, s)


-- | Static and Dynamic Inductive Graphs
module Data.Graph.Inductive.Graph

-- | Unlabeled node
type Node = Int

-- | Labeled node
type LNode a = (Node, a)

-- | Quasi-unlabeled node
type UNode = LNode ()

-- | Unlabeled edge
type Edge = (Node, Node)

-- | Labeled edge
type LEdge b = (Node, Node, b)

-- | Quasi-unlabeled edge
type UEdge = LEdge ()

-- | Labeled links to or from a <a>Node</a>.
type Adj b = [(b, Node)]

-- | Links to the <a>Node</a>, the <a>Node</a> itself, a label, links from
--   the <a>Node</a>.
type Context a b = (Adj b, Node, a, Adj b)
type MContext a b = Maybe (Context a b)

-- | <a>Graph</a> decomposition - the context removed from a <a>Graph</a>,
--   and the rest of the <a>Graph</a>.
type Decomp g a b = (MContext a b, g a b)

-- | The same as <a>Decomp</a>, only more sure of itself.
type GDecomp g a b = (Context a b, g a b)

-- | Unlabeled context.
type UContext = ([Node], Node, [Node])

-- | Unlabeled decomposition.
type UDecomp g = (Maybe UContext, g)

-- | Unlabeled path
type Path = [Node]

-- | Labeled path
newtype LPath a
LP :: [LNode a] -> LPath a

-- | Quasi-unlabeled path
type UPath = [UNode]

-- | Minimum implementation: <a>empty</a>, <a>isEmpty</a>, <a>match</a>,
--   <a>mkGraph</a>, <a>labNodes</a>
class Graph gr
empty :: Graph gr => gr a b
isEmpty :: Graph gr => gr a b -> Bool
match :: Graph gr => Node -> gr a b -> Decomp gr a b
mkGraph :: Graph gr => [LNode a] -> [LEdge b] -> gr a b
labNodes :: Graph gr => gr a b -> [LNode a]
matchAny :: Graph gr => gr a b -> GDecomp gr a b
noNodes :: Graph gr => gr a b -> Int
nodeRange :: Graph gr => gr a b -> (Node, Node)
labEdges :: Graph gr => gr a b -> [LEdge b]
class Graph gr => DynGraph gr
(&) :: DynGraph gr => Context a b -> gr a b -> gr a b

-- | Fold a function over the graph.
ufold :: Graph gr => ((Context a b) -> c -> c) -> c -> gr a b -> c

-- | Map a function over the graph.
gmap :: DynGraph gr => (Context a b -> Context c d) -> gr a b -> gr c d

-- | Map a function over the <a>Node</a> labels in a graph.
nmap :: DynGraph gr => (a -> c) -> gr a b -> gr c b

-- | Map a function over the <a>Edge</a> labels in a graph.
emap :: DynGraph gr => (b -> c) -> gr a b -> gr a c

-- | List all <a>Node</a>s in the <a>Graph</a>.
nodes :: Graph gr => gr a b -> [Node]

-- | List all <a>Edge</a>s in the <a>Graph</a>.
edges :: Graph gr => gr a b -> [Edge]

-- | List N available <a>Node</a>s, i.e. <a>Node</a>s that are not used in
--   the <a>Graph</a>.
newNodes :: Graph gr => Int -> gr a b -> [Node]

-- | <a>True</a> if the <a>Node</a> is present in the <a>Graph</a>.
gelem :: Graph gr => Node -> gr a b -> Bool

-- | Insert a <a>LNode</a> into the <a>Graph</a>.
insNode :: DynGraph gr => LNode a -> gr a b -> gr a b

-- | Insert a <a>LEdge</a> into the <a>Graph</a>.
insEdge :: DynGraph gr => LEdge b -> gr a b -> gr a b

-- | Remove a <a>Node</a> from the <a>Graph</a>.
delNode :: Graph gr => Node -> gr a b -> gr a b

-- | Remove an <a>Edge</a> from the <a>Graph</a>.
delEdge :: DynGraph gr => Edge -> gr a b -> gr a b

-- | Remove an <a>LEdge</a> from the <a>Graph</a>.
delLEdge :: (DynGraph gr, Eq b) => LEdge b -> gr a b -> gr a b

-- | Insert multiple <a>LNode</a>s into the <a>Graph</a>.
insNodes :: DynGraph gr => [LNode a] -> gr a b -> gr a b

-- | Insert multiple <a>LEdge</a>s into the <a>Graph</a>.
insEdges :: DynGraph gr => [LEdge b] -> gr a b -> gr a b

-- | Remove multiple <a>Node</a>s from the <a>Graph</a>.
delNodes :: Graph gr => [Node] -> gr a b -> gr a b

-- | Remove multiple <a>Edge</a>s from the <a>Graph</a>.
delEdges :: DynGraph gr => [Edge] -> gr a b -> gr a b

-- | Build a <a>Graph</a> from a list of <a>Context</a>s.
buildGr :: DynGraph gr => [Context a b] -> gr a b

-- | Build a quasi-unlabeled <a>Graph</a>.
mkUGraph :: Graph gr => [Node] -> [Edge] -> gr () ()

-- | Find the context for the given <a>Node</a>. Causes an error if the
--   <a>Node</a> is not present in the <a>Graph</a>.
context :: Graph gr => gr a b -> Node -> Context a b

-- | Find the label for a <a>Node</a>.
lab :: Graph gr => gr a b -> Node -> Maybe a

-- | Find the neighbors for a <a>Node</a>.
neighbors :: Graph gr => gr a b -> Node -> [Node]

-- | Find all <a>Node</a>s that have a link from the given <a>Node</a>.
suc :: Graph gr => gr a b -> Node -> [Node]

-- | Find all <a>Node</a>s that link to to the given <a>Node</a>.
pre :: Graph gr => gr a b -> Node -> [Node]

-- | Find all <a>Node</a>s that are linked from the given <a>Node</a> and
--   the label of each link.
lsuc :: Graph gr => gr a b -> Node -> [(Node, b)]

-- | Find all <a>Node</a>s that link to the given <a>Node</a> and the label
--   of each link.
lpre :: Graph gr => gr a b -> Node -> [(Node, b)]

-- | Find all outward-bound <a>LEdge</a>s for the given <a>Node</a>.
out :: Graph gr => gr a b -> Node -> [LEdge b]

-- | Find all inward-bound <a>LEdge</a>s for the given <a>Node</a>.
inn :: Graph gr => gr a b -> Node -> [LEdge b]

-- | The outward-bound degree of the <a>Node</a>.
outdeg :: Graph gr => gr a b -> Node -> Int

-- | The inward-bound degree of the <a>Node</a>.
indeg :: Graph gr => gr a b -> Node -> Int

-- | The degree of the <a>Node</a>.
deg :: Graph gr => gr a b -> Node -> Int
equal :: (Eq a, Eq b, Graph gr) => gr a b -> gr a b -> Bool

-- | The <a>Node</a> in a <a>Context</a>.
node' :: Context a b -> Node

-- | The label in a <a>Context</a>.
lab' :: Context a b -> a

-- | The <a>LNode</a> from a <a>Context</a>.
labNode' :: Context a b -> LNode a

-- | All <a>Node</a>s linked to or from in a <a>Context</a>.
neighbors' :: Context a b -> [Node]

-- | All <a>Node</a>s linked to in a <a>Context</a>.
suc' :: Context a b -> [Node]

-- | All <a>Node</a>s linked from in a <a>Context</a>.
pre' :: Context a b -> [Node]

-- | All <a>Node</a>s linked from in a <a>Context</a>, and the label of the
--   links.
lpre' :: Context a b -> [(Node, b)]

-- | All <a>Node</a>s linked from in a <a>Context</a>, and the label of the
--   links.
lsuc' :: Context a b -> [(Node, b)]

-- | All outward-directed <a>LEdge</a>s in a <a>Context</a>.
out' :: Context a b -> [LEdge b]

-- | All inward-directed <a>LEdge</a>s in a <a>Context</a>.
inn' :: Context a b -> [LEdge b]

-- | The outward degree of a <a>Context</a>.
outdeg' :: Context a b -> Int

-- | The inward degree of a <a>Context</a>.
indeg' :: Context a b -> Int

-- | The degree of a <a>Context</a>.
deg' :: Context a b -> Int
instance [overlap ok] Show a => Show (LPath a)


-- | Basic Graph Algorithms
module Data.Graph.Inductive.Basic

-- | Reverse the direction of all edges.
grev :: DynGraph gr => gr a b -> gr a b

-- | Make the graph undirected, i.e. for every edge from A to B, there
--   exists an edge from B to A.
undir :: (Eq b, DynGraph gr) => gr a b -> gr a b

-- | Remove all labels.
unlab :: DynGraph gr => gr a b -> gr () ()

-- | Return all <a>Context</a>s for which the given function returns
--   <a>True</a>.
gsel :: Graph gr => (Context a b -> Bool) -> gr a b -> [Context a b]

-- | Directed graph fold.
gfold :: Graph gr => ((Context a b) -> [Node]) -> ((Context a b) -> c -> d) -> (Maybe d -> c -> c, c) -> [Node] -> gr a b -> c

-- | Filter based on edge property.
efilter :: DynGraph gr => (LEdge b -> Bool) -> gr a b -> gr a b

-- | Filter based on edge label property.
elfilter :: DynGraph gr => (b -> Bool) -> gr a b -> gr a b

-- | <a>True</a> if the graph has any edges of the form (A, A).
hasLoop :: Graph gr => gr a b -> Bool

-- | The inverse of <a>hasLoop</a>.
isSimple :: Graph gr => gr a b -> Bool

-- | Flatten a <a>Tree</a>, returning the elements in post-order.
postorder :: Tree a -> [a]

-- | Flatten multiple <a>Tree</a>s in post-order.
postorderF :: [Tree a] -> [a]

-- | Flatten a <a>Tree</a>, returning the elements in pre-order. Equivalent
--   to <a>flatten</a> in <tt>Data.Tree</tt>.
preorder :: Tree a -> [a]

-- | Flatten multiple <a>Tree</a>s in pre-order.
preorderF :: [Tree a] -> [a]


-- | Monadic Graphs
module Data.Graph.Inductive.Monad
class Monad m => GraphM m gr
emptyM :: GraphM m gr => m (gr a b)
isEmptyM :: GraphM m gr => m (gr a b) -> m Bool
matchM :: GraphM m gr => Node -> m (gr a b) -> m (Decomp gr a b)
mkGraphM :: GraphM m gr => [LNode a] -> [LEdge b] -> m (gr a b)
labNodesM :: GraphM m gr => m (gr a b) -> m [LNode a]
matchAnyM :: GraphM m gr => m (gr a b) -> m (GDecomp gr a b)
noNodesM :: GraphM m gr => m (gr a b) -> m Int
nodeRangeM :: GraphM m gr => m (gr a b) -> m (Node, Node)
labEdgesM :: GraphM m gr => m (gr a b) -> m [LEdge b]

-- | graph fold
ufoldM :: GraphM m gr => ((Context a b) -> c -> c) -> c -> m (gr a b) -> m c
nodesM :: GraphM m gr => m (gr a b) -> m [Node]
edgesM :: GraphM m gr => m (gr a b) -> m [Edge]
newNodesM :: GraphM m gr => Int -> m (gr a b) -> m [Node]
delNodeM :: GraphM m gr => Node -> m (gr a b) -> m (gr a b)
delNodesM :: GraphM m gr => [Node] -> m (gr a b) -> m (gr a b)
mkUGraphM :: GraphM m gr => [Node] -> [Edge] -> m (gr () ())
contextM :: GraphM m gr => m (gr a b) -> Node -> m (Context a b)
labM :: GraphM m gr => m (gr a b) -> Node -> m (Maybe a)


-- | Static IOArray-based Graphs
module Data.Graph.Inductive.Monad.IOArray
data SGr a b
SGr :: (GraphRep a b) -> SGr a b
type GraphRep a b = (Int, Array Node (Context' a b), IOArray Node Bool)
type Context' a b = Maybe (Adj b, a, Adj b)
type USGr = SGr () ()
defaultGraphSize :: Int
emptyN :: Int -> IO (SGr a b)

-- | filter list (of successors/predecessors) through a boolean ST array
--   representing deleted marks
removeDel :: IOArray Node Bool -> Adj b -> IO (Adj b)
instance [overlap ok] GraphM IO SGr
instance [overlap ok] (Show a, Show b) => Show (IO (SGr a b))
instance [overlap ok] (Show a, Show b) => Show (SGr a b)


-- | Simple graphviz output.
module Data.Graph.Inductive.Graphviz
data Orient
Portrait :: Orient
Landscape :: Orient

-- | Formats a graph for use in graphviz.
graphviz :: (Graph g, Show a, Show b) => g a b -> String -> (Double, Double) -> (Int, Int) -> Orient -> String

-- | Format a graph for graphviz with reasonable defaults: title of "fgl",
--   8.5x11 pages, one page, landscape orientation
graphviz' :: (Graph g, Show a, Show b) => g a b -> String
instance [overlap ok] Eq Orient
instance [overlap ok] Show Orient


-- | An efficient implementation of <a>Graph</a> using big-endian patricia
--   tree (i.e. <a>Data.IntMap</a>).
--   
--   This module provides the following specialised functions to gain more
--   performance, using GHC's RULES pragma:
--   
--   <ul>
--   <li><a>insNode</a></li>
--   <li><a>insEdge</a></li>
--   <li><a>gmap</a></li>
--   <li><a>nmap</a></li>
--   <li><a>emap</a></li>
--   </ul>
module Data.Graph.Inductive.PatriciaTree
data Gr a b
type UGr = Gr () ()
instance [overlap ok] DynGraph Gr
instance [overlap ok] Graph Gr


-- | Depth-First Search
module Data.Graph.Inductive.Query.DFS
type CFun a b c = Context a b -> c
dfs :: Graph gr => [Node] -> gr a b -> [Node]
dfs' :: Graph gr => gr a b -> [Node]
dff :: Graph gr => [Node] -> gr a b -> [Tree Node]
dff' :: Graph gr => gr a b -> [Tree Node]
dfsWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [c]
dfsWith' :: Graph gr => CFun a b c -> gr a b -> [c]
dffWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [Tree c]
dffWith' :: Graph gr => CFun a b c -> gr a b -> [Tree c]
xdfsWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [c]
xdfWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> ([Tree c], gr a b)
xdffWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [Tree c]
udfs :: Graph gr => [Node] -> gr a b -> [Node]
udfs' :: Graph gr => gr a b -> [Node]
udff :: Graph gr => [Node] -> gr a b -> [Tree Node]
udff' :: Graph gr => gr a b -> [Tree Node]
rdff :: Graph gr => [Node] -> gr a b -> [Tree Node]
rdff' :: Graph gr => gr a b -> [Tree Node]
rdfs :: Graph gr => [Node] -> gr a b -> [Node]
rdfs' :: Graph gr => gr a b -> [Node]
topsort :: Graph gr => gr a b -> [Node]
topsort' :: Graph gr => gr a b -> [a]
scc :: Graph gr => gr a b -> [[Node]]
reachable :: Graph gr => Node -> gr a b -> [Node]
components :: Graph gr => gr a b -> [[Node]]
noComponents :: Graph gr => gr a b -> Int
isConnected :: Graph gr => gr a b -> Bool


-- | Maximum Independent Node Sets
module Data.Graph.Inductive.Query.Indep
indep :: DynGraph gr => gr a b -> [Node]

module Data.Graph.Inductive.Query.ArtPoint

-- | Finds the articulation points for a connected undirected graph, by
--   using the low numbers criteria:
--   
--   a) The root node is an articulation point iff it has two or more
--   children.
--   
--   b) An non-root node v is an articulation point iff there exists at
--   least one child w of v such that lowNumber(w) &gt;= dfsNumber(v).
ap :: Graph gr => gr a b -> [Node]
instance [overlap ok] Eq a => Eq (DFSTree a)
instance [overlap ok] Eq a => Eq (LOWTree a)

module Data.Graph.Inductive.Query.BCC

-- | Finds the bi-connected components of an undirected connected graph. It
--   first finds the articulation points of the graph. Then it disconnects
--   the graph on each articulation point and computes the connected
--   components.
bcc :: DynGraph gr => gr a b -> [gr a b]

module Data.Graph.Inductive.Query.Dominators

-- | return the set of dominators of the nodes of a graph, given a root
dom :: Graph gr => gr a b -> Node -> [(Node, [Node])]

-- | return immediate dominators for each node of a graph, given a root
iDom :: Graph gr => gr a b -> Node -> [(Node, Node)]

module Data.Graph.Inductive.Query.TransClos

-- | Finds the transitive closure of a directed graph. Given a graph
--   G=(V,E), its transitive closure is the graph: G* = (V,E*) where
--   E*={(i,j): i,j in V and there is a path from i to j in G}
trc :: DynGraph gr => gr a b -> gr a ()


-- | Monadic Graph Algorithms
module Data.Graph.Inductive.Query.Monad
mapFst :: (a -> b) -> (a, c) -> (b, c)
mapSnd :: (a -> b) -> (c, a) -> (c, b)
(><) :: (a -> b) -> (c -> d) -> (a, c) -> (b, d)
orP :: (a -> Bool) -> (b -> Bool) -> (a, b) -> Bool
data GT m g a
MGT :: (m g -> m (a, g)) -> GT m g a
apply :: GT m g a -> m g -> m (a, g)
apply' :: Monad m => GT m g a -> g -> m (a, g)
applyWith :: Monad m => (a -> b) -> GT m g a -> m g -> m (b, g)
applyWith' :: Monad m => (a -> b) -> GT m g a -> g -> m (b, g)
runGT :: Monad m => GT m g a -> m g -> m a
condMGT' :: Monad m => (s -> Bool) -> GT m s a -> GT m s a -> GT m s a
recMGT' :: Monad m => (s -> Bool) -> GT m s a -> (a -> b -> b) -> b -> GT m s b
condMGT :: Monad m => (m s -> m Bool) -> GT m s a -> GT m s a -> GT m s a
recMGT :: Monad m => (m s -> m Bool) -> GT m s a -> (a -> b -> b) -> b -> GT m s b
getNode :: GraphM m gr => GT m (gr a b) Node
getContext :: GraphM m gr => GT m (gr a b) (Context a b)
getNodes' :: (Graph gr, GraphM m gr) => GT m (gr a b) [Node]
getNodes :: GraphM m gr => GT m (gr a b) [Node]
sucGT :: GraphM m gr => Node -> GT m (gr a b) (Maybe [Node])
sucM :: GraphM m gr => Node -> m (gr a b) -> m (Maybe [Node])

-- | encapsulates a simple recursion schema on graphs
graphRec :: GraphM m gr => GT m (gr a b) c -> (c -> d -> d) -> d -> GT m (gr a b) d
graphRec' :: (Graph gr, GraphM m gr) => GT m (gr a b) c -> (c -> d -> d) -> d -> GT m (gr a b) d
graphUFold :: GraphM m gr => (Context a b -> c -> c) -> c -> GT m (gr a b) c
graphNodesM0 :: GraphM m gr => GT m (gr a b) [Node]
graphNodesM :: GraphM m gr => GT m (gr a b) [Node]
graphNodes :: GraphM m gr => m (gr a b) -> m [Node]
graphFilterM :: GraphM m gr => (Context a b -> Bool) -> GT m (gr a b) [Context a b]
graphFilter :: GraphM m gr => (Context a b -> Bool) -> m (gr a b) -> m [Context a b]

-- | Monadic graph algorithms are defined in two steps:
--   
--   <ol>
--   <li>define the (possibly parameterized) graph transformer (e.g.,
--   dfsGT) (2) run the graph transformer (applied to arguments) (e.g.,
--   dfsM)</li>
--   </ol>
dfsGT :: GraphM m gr => [Node] -> GT m (gr a b) [Node]

-- | depth-first search yielding number of nodes
dfsM :: GraphM m gr => [Node] -> m (gr a b) -> m [Node]
dfsM' :: GraphM m gr => m (gr a b) -> m [Node]

-- | depth-first search yielding dfs forest
dffM :: GraphM m gr => [Node] -> GT m (gr a b) [Tree Node]
graphDff :: GraphM m gr => [Node] -> m (gr a b) -> m [Tree Node]
graphDff' :: GraphM m gr => m (gr a b) -> m [Tree Node]
instance [overlap ok] Monad m => Monad (GT m g)


-- | Inward directed trees as lists of paths.
module Data.Graph.Inductive.Internal.RootPath
type RTree = [Path]
type LRTree a = [LPath a]
getPath :: Node -> RTree -> Path
getLPath :: Node -> LRTree a -> LPath a
getDistance :: Node -> LRTree a -> a
getLPathNodes :: Node -> LRTree a -> Path
instance [overlap ok] Ord a => Ord (LPath a)
instance [overlap ok] Eq a => Eq (LPath a)

module Data.Graph.Inductive.Internal.Queue
data Queue a
MkQueue :: [a] -> [a] -> Queue a
mkQueue :: Queue a
queuePut :: a -> Queue a -> Queue a
queuePutList :: [a] -> Queue a -> Queue a
queueGet :: Queue a -> (a, Queue a)
queueEmpty :: Queue a -> Bool


-- | Breadth-First Search Algorithms
module Data.Graph.Inductive.Query.BFS
bfs :: Graph gr => Node -> gr a b -> [Node]
bfsn :: Graph gr => [Node] -> gr a b -> [Node]
bfsWith :: Graph gr => (Context a b -> c) -> Node -> gr a b -> [c]
bfsnWith :: Graph gr => (Context a b -> c) -> [Node] -> gr a b -> [c]
level :: Graph gr => Node -> gr a b -> [(Node, Int)]
leveln :: Graph gr => [(Node, Int)] -> gr a b -> [(Node, Int)]
bfe :: Graph gr => Node -> gr a b -> [Edge]
bfen :: Graph gr => [Edge] -> gr a b -> [Edge]
bft :: Graph gr => Node -> gr a b -> RTree
lbft :: Graph gr => Node -> gr a b -> LRTree b
esp :: Graph gr => Node -> Node -> gr a b -> Path
lesp :: Graph gr => Node -> Node -> gr a b -> LPath b


-- | Maximum Flow algorithm We are given a flow network G=(V,E) with source
--   s and sink t where each edge (u,v) in E has a nonnegative capacity
--   c(u,v)&gt;=0, and we wish to find a flow of maximum value from s to t.
--   
--   A flow in G=(V,E) is a real-valued function f:VxV-&gt;R that
--   satisfies:
--   
--   <pre>
--   For all u,v in V, f(u,v)&lt;=c(u,v)
--   For all u,v in V, f(u,v)=-f(v,u)
--   For all u in V-{s,t}, Sum{f(u,v):v in V } = 0
--   </pre>
--   
--   The value of a flow f is defined as |f|=Sum {f(s,v)|v in V}, i.e., the
--   total net flow out of the source.
--   
--   In this module we implement the Edmonds-Karp algorithm, which is the
--   Ford-Fulkerson method but using the shortest path from s to t as the
--   augmenting path along which the flow is incremented.
module Data.Graph.Inductive.Query.MaxFlow

-- | <pre>
--                   i                                 0
--   For each edge a---&gt;b this function returns edge b---&gt;a .
--            i
--   Edges a&lt;---&gt;b are ignored
--            j
--   </pre>
getRevEdges :: (Num b, Ord b) => [(Node, Node)] -> [(Node, Node, b)]

-- | <pre>
--                   i                                  0
--   For each edge a---&gt;b insert into graph the edge a&lt;---b . Then change the
--                              i         (i,0,i)
--   label of every edge from a----&gt;b to a-------&gt;b
--   </pre>
--   
--   where label (x,y,z)=(Max Capacity, Current flow, Residual capacity)
augmentGraph :: (DynGraph gr, Num b, Ord b) => gr a b -> gr a (b, b, b)

-- | Given a successor or predecessor list for node u and given node v,
--   find the label corresponding to edge (u,v) and update the flow and
--   residual capacity of that edge's label. Then return the updated list.
updAdjList :: (Num b, Ord b) => [((b, b, b), Node)] -> Node -> b -> Bool -> [((b, b, b), Node)]

-- | Update flow and residual capacity along augmenting path from s to t in
--   graph G. For a path [u,v,w,...] find the node u in G and its successor
--   and predecessor list, then update the corresponding edges (u,v) and
--   (v,u) on those lists by using the minimum residual capacity of the
--   path.
updateFlow :: (DynGraph gr, Num b, Ord b) => Path -> b -> gr a (b, b, b) -> gr a (b, b, b)

-- | Compute the flow from s to t on a graph whose edges are labeled with
--   (x,y,z)=(max capacity,current flow,residual capacity) and all edges
--   are of the form a&lt;----&gt;b. First compute the residual graph, that
--   is, delete those edges whose residual capacity is zero. Then compute
--   the shortest augmenting path from s to t, and finally update the flow
--   and residual capacity along that path by using the minimum capacity of
--   that path. Repeat this process until no shortest path from s to t
--   exist.
mfmg :: (DynGraph gr, Num b, Ord b) => gr a (b, b, b) -> Node -> Node -> gr a (b, b, b)

-- | Compute the flow from s to t on a graph whose edges are labeled with
--   x, which is the max capacity and where not all edges need to be of the
--   form a&lt;----&gt;b. Return the flow as a grap whose edges are labeled
--   with (x,y,z)=(max capacity,current flow,residual capacity) and all
--   edges are of the form a&lt;----&gt;b
mf :: (DynGraph gr, Num b, Ord b) => gr a b -> Node -> Node -> gr a (b, b, b)

-- | Compute the maximum flow from s to t on a graph whose edges are
--   labeled with x, which is the max capacity and where not all edges need
--   to be of the form a&lt;----&gt;b. Return the flow as a grap whose
--   edges are labeled with (y,x) = (current flow, max capacity).
maxFlowgraph :: (DynGraph gr, Num b, Ord b) => gr a b -> Node -> Node -> gr a (b, b)

-- | Compute the value of a maximumflow
maxFlow :: (DynGraph gr, Num b, Ord b) => gr a b -> Node -> Node -> b


-- | Pairing heap implementation of dictionary
module Data.Graph.Inductive.Internal.Heap
data Ord a => Heap a b
Empty :: Heap a b
Node :: a -> b -> [Heap a b] -> Heap a b
empty :: Ord a => Heap a b
unit :: Ord a => a -> b -> Heap a b
insert :: Ord a => (a, b) -> Heap a b -> Heap a b
merge :: Ord a => Heap a b -> Heap a b -> Heap a b
mergeAll :: Ord a => [Heap a b] -> Heap a b
isEmpty :: Ord a => Heap a b -> Bool
findMin :: Ord a => Heap a b -> (a, b)
deleteMin :: Ord a => Heap a b -> Heap a b
splitMin :: Ord a => Heap a b -> (a, b, Heap a b)
build :: Ord a => [(a, b)] -> Heap a b
toList :: Ord a => Heap a b -> [(a, b)]
heapsort :: Ord a => [a] -> [a]
instance [overlap ok] (Eq b, Ord a) => Eq (Heap a b)
instance [overlap ok] (Show a, Ord a, Show b) => Show (Heap a b)

module Data.Graph.Inductive.Query.SP
spTree :: (Graph gr, Real b) => Node -> gr a b -> LRTree b
spLength :: (Graph gr, Real b) => Node -> Node -> gr a b -> b
sp :: (Graph gr, Real b) => Node -> Node -> gr a b -> Path

-- | Implementation of Dijkstra's shortest path algorithm
dijkstra :: (Graph gr, Real b) => Heap b (LPath b) -> gr a b -> LRTree b


-- | Graph Voronoi Diagram
module Data.Graph.Inductive.Query.GVD
type Voronoi a = LRTree a
gvdIn :: (DynGraph gr, Real b) => [Node] -> gr a b -> Voronoi b
gvdOut :: (Graph gr, Real b) => [Node] -> gr a b -> Voronoi b
voronoiSet :: Real b => Node -> Voronoi b -> [Node]
nearestNode :: Real b => Node -> Voronoi b -> Maybe Node
nearestDist :: Real b => Node -> Voronoi b -> Maybe b
nearestPath :: Real b => Node -> Voronoi b -> Maybe Path


-- | Minimum-Spanning-Tree Algorithms
module Data.Graph.Inductive.Query.MST
msTreeAt :: (Graph gr, Real b) => Node -> gr a b -> LRTree b
msTree :: (Graph gr, Real b) => gr a b -> LRTree b
msPath :: Real b => LRTree b -> Node -> Node -> Path


-- | Simple Finite Maps. This implementation provides several useful
--   methods that Data.FiniteMap does not.
module Data.Graph.Inductive.Internal.FiniteMap
data Ord a => FiniteMap a b
Empty :: FiniteMap a b
Node :: Int -> (FiniteMap a b) -> (a, b) -> (FiniteMap a b) -> FiniteMap a b
emptyFM :: Ord a => FiniteMap a b
addToFM :: Ord a => FiniteMap a b -> a -> b -> FiniteMap a b
delFromFM :: Ord a => FiniteMap a b -> a -> FiniteMap a b

-- | applies function to stored entry
updFM :: Ord a => FiniteMap a b -> a -> (b -> b) -> FiniteMap a b

-- | defines or aggregates entries
accumFM :: Ord a => FiniteMap a b -> a -> (b -> b -> b) -> b -> FiniteMap a b

-- | combines delFrom and lookup
splitFM :: Ord a => FiniteMap a b -> a -> Maybe (FiniteMap a b, (a, b))
isEmptyFM :: FiniteMap a b -> Bool
sizeFM :: Ord a => FiniteMap a b -> Int
lookupFM :: Ord a => FiniteMap a b -> a -> Maybe b
elemFM :: Ord a => FiniteMap a b -> a -> Bool

-- | applies lookup to an interval
rangeFM :: Ord a => FiniteMap a b -> a -> a -> [b]
minFM :: Ord a => FiniteMap a b -> Maybe (a, b)
maxFM :: Ord a => FiniteMap a b -> Maybe (a, b)
predFM :: Ord a => FiniteMap a b -> a -> Maybe (a, b)
succFM :: Ord a => FiniteMap a b -> a -> Maybe (a, b)

-- | combines splitFM and minFM
splitMinFM :: Ord a => FiniteMap a b -> Maybe (FiniteMap a b, (a, b))
fmToList :: Ord a => FiniteMap a b -> [(a, b)]
instance [overlap ok] (Eq b, Ord a) => Eq (FiniteMap a b)
instance [overlap ok] (Show a, Show b, Ord a) => Show (FiniteMap a b)


-- | Tree-based implementation of <a>Graph</a> and <a>DynGraph</a>
module Data.Graph.Inductive.Tree
data Gr a b
type UGr = Gr () ()
instance [overlap ok] DynGraph Gr
instance [overlap ok] Graph Gr
instance [overlap ok] (Show a, Show b) => Show (Gr a b)


-- | Utility methods to automatically generate and keep track of a mapping
--   between node labels and <a>Node</a>s.
module Data.Graph.Inductive.NodeMap
data Ord a => NodeMap a

-- | Create a new, empty mapping.
new :: Ord a => NodeMap a

-- | Generate a mapping containing the nodes in the given graph.
fromGraph :: (Ord a, Graph g) => g a b -> NodeMap a

-- | Generate a labelled node from the given label. Will return the same
--   node for the same label.
mkNode :: Ord a => NodeMap a -> a -> (LNode a, NodeMap a)

-- | Generate a labelled node and throw away the modified <a>NodeMap</a>.
mkNode_ :: Ord a => NodeMap a -> a -> LNode a

-- | Construct a list of nodes.
mkNodes :: Ord a => NodeMap a -> [a] -> ([LNode a], NodeMap a)

-- | Construct a list of nodes and throw away the modified <a>NodeMap</a>.
mkNodes_ :: Ord a => NodeMap a -> [a] -> [LNode a]

-- | Generate a <a>LEdge</a> from the node labels.
mkEdge :: Ord a => NodeMap a -> (a, a, b) -> Maybe (LEdge b)

-- | Generates a list of <a>LEdge</a>s.
mkEdges :: Ord a => NodeMap a -> [(a, a, b)] -> Maybe [LEdge b]
insMapNode :: (Ord a, DynGraph g) => NodeMap a -> a -> g a b -> (g a b, NodeMap a, LNode a)
insMapNode_ :: (Ord a, DynGraph g) => NodeMap a -> a -> g a b -> g a b
insMapEdge :: (Ord a, DynGraph g) => NodeMap a -> (a, a, b) -> g a b -> g a b
delMapNode :: (Ord a, DynGraph g) => NodeMap a -> a -> g a b -> g a b
delMapEdge :: (Ord a, DynGraph g) => NodeMap a -> (a, a) -> g a b -> g a b
insMapNodes :: (Ord a, DynGraph g) => NodeMap a -> [a] -> g a b -> (g a b, NodeMap a, [LNode a])
insMapNodes_ :: (Ord a, DynGraph g) => NodeMap a -> [a] -> g a b -> g a b
insMapEdges :: (Ord a, DynGraph g) => NodeMap a -> [(a, a, b)] -> g a b -> g a b
delMapNodes :: (Ord a, DynGraph g) => NodeMap a -> [a] -> g a b -> g a b
delMapEdges :: (Ord a, DynGraph g) => NodeMap a -> [(a, a)] -> g a b -> g a b
mkMapGraph :: (Ord a, DynGraph g) => [a] -> [(a, a, b)] -> (g a b, NodeMap a)

-- | Graph construction monad; handles passing both the <a>NodeMap</a> and
--   the <a>Graph</a>.
type NodeMapM a b g r = State (NodeMap a, g a b) r

-- | Run a construction; return the value of the computation, the modified
--   <a>NodeMap</a>, and the modified <a>Graph</a>.
run :: (DynGraph g, Ord a) => g a b -> NodeMapM a b g r -> (r, (NodeMap a, g a b))

-- | Run a construction and only return the <a>Graph</a>.
run_ :: (DynGraph g, Ord a) => g a b -> NodeMapM a b g r -> g a b

-- | Monadic node construction.
mkNodeM :: (Ord a, DynGraph g) => a -> NodeMapM a b g (LNode a)
mkNodesM :: (Ord a, DynGraph g) => [a] -> NodeMapM a b g [LNode a]
mkEdgeM :: (Ord a, DynGraph g) => (a, a, b) -> NodeMapM a b g (Maybe (LEdge b))
mkEdgesM :: (Ord a, DynGraph g) => [(a, a, b)] -> NodeMapM a b g (Maybe [LEdge b])
insMapNodeM :: (Ord a, DynGraph g) => a -> NodeMapM a b g (LNode a)
insMapEdgeM :: (Ord a, DynGraph g) => (a, a, b) -> NodeMapM a b g ()
delMapNodeM :: (Ord a, DynGraph g) => a -> NodeMapM a b g ()
delMapEdgeM :: (Ord a, DynGraph g) => (a, a) -> NodeMapM a b g ()
insMapNodesM :: (Ord a, DynGraph g) => [a] -> NodeMapM a b g [LNode a]
insMapEdgesM :: (Ord a, DynGraph g) => [(a, a, b)] -> NodeMapM a b g ()
delMapNodesM :: (Ord a, DynGraph g) => [a] -> NodeMapM a b g ()
delMapEdgesM :: (Ord a, DynGraph g) => [(a, a)] -> NodeMapM a b g ()
instance [overlap ok] (Ord a, Show a) => Show (NodeMap a)


-- | Alternative Maximum Flow
module Data.Graph.Inductive.Query.MaxFlow2
type Network = Gr () (Double, Double)
ekSimple :: Network -> Node -> Node -> (Network, Double)
ekFused :: Network -> Node -> Node -> (Network, Double)
ekList :: Network -> Node -> Node -> (Network, Double)
instance [overlap ok] Eq Direction
instance [overlap ok] Show Direction

module Data.Graph.Inductive.Query

module Data.Graph.Inductive

-- | Version info
version :: IO ()


-- | Example Graphs
module Data.Graph.Inductive.Example

-- | generate list of unlabeled nodes
genUNodes :: Int -> [UNode]

-- | generate list of labeled nodes
genLNodes :: Enum a => a -> Int -> [LNode a]

-- | denote unlabeled edges
labUEdges :: [Edge] -> [UEdge]

-- | empty (unlabeled) edge list
noEdges :: [UEdge]
a :: Gr Char ()
b :: Gr Char ()
c :: Gr Char ()
e :: Gr Char ()
loop :: Gr Char ()
ab :: Gr Char ()
abb :: Gr Char ()
dag3 :: Gr Char ()
e3 :: Gr () String
cyc3 :: Gr Char String
g3 :: Gr Char String
g3b :: Gr Char String
dag4 :: Gr Int ()
d1 :: Gr Int Int
d3 :: Gr Int Int
a' :: IO (SGr Char ())
b' :: IO (SGr Char ())
c' :: IO (SGr Char ())
e' :: IO (SGr Char ())
loop' :: IO (SGr Char ())
ab' :: IO (SGr Char ())
abb' :: IO (SGr Char ())
dag3' :: IO (SGr Char ())
e3' :: IO (SGr () String)
dag4' :: IO (SGr Int ())
d1' :: IO (SGr Int Int)
d3' :: IO (SGr Int Int)
ucycle :: Graph gr => Int -> gr () ()
star :: Graph gr => Int -> gr () ()
ucycleM :: GraphM m gr => Int -> m (gr () ())
starM :: GraphM m gr => Int -> m (gr () ())
clr479 :: Gr Char ()
clr489 :: Gr Char ()
clr486 :: Gr String ()
clr508 :: Gr Char Int
clr528 :: Gr Char Int
clr595 :: Gr Int Int
gr1 :: Gr Int Int
kin248 :: Gr Int ()
vor :: Gr String Int
clr479' :: IO (SGr Char ())
clr489' :: IO (SGr Char ())
clr486' :: IO (SGr String ())
clr508' :: IO (SGr Char Int)
clr528' :: IO (SGr Char Int)
kin248' :: IO (SGr Int ())
vor' :: IO (SGr String Int)