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


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


-- | 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
unLPath :: LPath a -> [LNode 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 where matchAny g = case labNodes g of { [] -> error "Match Exception, Empty Graph" (v, _) : _ -> (c, g') where (Just c, g') = match v g } noNodes = length . labNodes nodeRange g | isEmpty g = error "nodeRange of empty graph" | otherwise = (minimum vs, maximum vs) where vs = nodes g labEdges = ufold (\ (_, v, _, s) -> (map (\ (l, w) -> (v, w, l)) s ++)) []
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

-- | Map functions over both the <a>Node</a> and <a>Edge</a> labels in a
--   graph.
nemap :: DynGraph gr => (a -> c) -> (b -> d) -> gr a b -> gr c d

-- | 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]

-- | Drop the label component of an edge.
toEdge :: LEdge b -> Edge

-- | The label in an edge.
edgeLabel :: LEdge b -> b

-- | Add a label to an edge.
toLEdge :: Edge -> b -> LEdge b

-- | 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>.
--   
--   NOTE: in the case of multiple edges, this will delete <i>all</i> such
--   edges from the graph as there is no way to distinguish between them.
--   If you need to delete only a single such edge, please use
--   <a>delLEdge</a>.
delEdge :: DynGraph gr => Edge -> gr a b -> gr a b

-- | Remove an <a>LEdge</a> from the <a>Graph</a>.
--   
--   NOTE: in the case of multiple edges with the same label, this will
--   only delete the <i>first</i> such edge. To delete all such edges,
--   please use <tt>delAllLedges</tt>.
delLEdge :: (DynGraph gr, Eq b) => LEdge b -> gr a b -> gr a b

-- | Remove all edges equal to the one specified.
delAllLEdge :: (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.
--   
--   The list should be in the order such that earlier <a>Context</a>s
--   depend upon later ones (i.e. as produced by <tt><a>ufold</a> (:)
--   []</tt>).
buildGr :: DynGraph gr => [Context a b] -> gr a b

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

-- | Build a graph out of the contexts for which the predicate is true.
gfiltermap :: DynGraph gr => (Context a b -> MContext c d) -> gr a b -> gr c d

-- | Returns the subgraph only containing the nodes which satisfy the given
--   predicate.
nfilter :: DynGraph gr => (Node -> Bool) -> gr a b -> gr a b

-- | Returns the subgraph only containing the labelled nodes which satisfy
--   the given predicate.
labnfilter :: Graph gr => (LNode a -> Bool) -> gr a b -> gr a b

-- | Returns the subgraph only containing the nodes whose labels satisfy
--   the given predicate.
labfilter :: DynGraph gr => (a -> Bool) -> gr a b -> gr a b

-- | Returns the subgraph induced by the supplied nodes.
subgraph :: DynGraph gr => [Node] -> gr a b -> gr a b

-- | 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 the labelled links coming into or going from a <a>Context</a>.
lneighbors :: Graph gr => gr a b -> Node -> Adj b

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

-- | Checks if there is a directed edge between two nodes.
hasEdge :: Graph gr => gr a b -> Edge -> Bool

-- | Checks if there is an undirected edge between two nodes.
hasNeighbor :: Graph gr => gr a b -> Node -> Node -> Bool

-- | Checks if there is a labelled edge between two nodes.
hasLEdge :: (Graph gr, Eq b) => gr a b -> LEdge b -> Bool

-- | Checks if there is an undirected labelled edge between two nodes.
hasNeighborAdj :: (Graph gr, Eq b) => gr a b -> Node -> (b, Node) -> Bool
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 labelled links coming into or going from a <a>Context</a>.
lneighbors' :: Context a b -> Adj b

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

-- | Pretty-print the graph. Note that this loses a lot of information,
--   such as edge inverses, etc.
prettify :: (DynGraph gr, Show a, Show b) => gr a b -> String

-- | Pretty-print the graph to stdout.
prettyPrint :: (DynGraph gr, Show a, Show b) => gr a b -> IO ()

-- | OrdGr comes equipped with an Ord instance, so that graphs can be used
--   as e.g. Map keys.
newtype OrdGr gr a b
OrdGr :: gr a b -> OrdGr gr a b
unOrdGr :: OrdGr gr a b -> gr a b
instance Show b => Show (GroupEdges b)
instance Read b => Read (GroupEdges b)
instance Read (gr a b) => Read (OrdGr gr a b)
instance Show (gr a b) => Show (OrdGr gr a b)
instance (Graph gr, Ord a, Ord b) => Ord (OrdGr gr a b)
instance (Graph gr, Ord a, Ord b) => Eq (OrdGr gr a b)
instance Eq b => Eq (GroupEdges b)
instance Ord a => Ord (LPath a)
instance Eq a => Eq (LPath a)
instance 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 <a>Tree</a>.
preorder :: Tree a -> [a]

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


-- | 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 Generic (Gr a b)
instance Datatype D1Gr
instance Constructor C1_0Gr
instance (NFData a, NFData b) => NFData (Gr a b)
instance DynGraph Gr
instance Graph Gr
instance (Read a, Read b) => Read (Gr a b)
instance (Show a, Show b) => Show (Gr a b)
instance (Eq a, Ord b) => Eq (Gr a b)


-- | Monadic Graphs
module Data.Graph.Inductive.Monad
class Monad m => GraphM m gr where matchAnyM g = do { vs <- labNodesM g; case vs of { [] -> fail "Match Exception, Empty Graph" (v, _) : _ -> do { (Just c, g') <- matchM v g; return (c, g') } } } noNodesM = labNodesM >>. length nodeRangeM g = do { isE <- isEmptyM g; if isE then fail "nodeRangeM of empty graph" else do { vs <- nodesM g; return (minimum vs, maximum vs) } } labEdgesM = ufoldM (\ (p, v, _, s) -> ((map (i v) p ++ map (o v) s) ++)) [] where o v = \ (l, w) -> (v, w, l) i v = \ (l, w) -> (w, v, l)
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
newtype 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 GraphM IO SGr
instance (Show a, Show b) => Show (IO (SGr a b))
instance (Show a, Show b) => Show (SGr a b)


-- | 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)


-- | 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 NodeMap a

-- | Create a new, empty mapping.
new :: 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 Eq a => Eq (NodeMap a)
instance Show a => Show (NodeMap a)
instance (Ord a, Read a) => Read (NodeMap a)
instance NFData a => NFData (NodeMap a)

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 Eq a => Eq (DFSTree a)
instance Show a => Show (DFSTree a)
instance Read a => Read (DFSTree a)
instance Eq a => Eq (LOWTree a)
instance Show a => Show (LOWTree a)
instance Read a => Read (LOWTree a)


-- | Depth-first search algorithms.
--   
--   Names consist of:
--   
--   <ol>
--   <li>An optional direction parameter, specifying which nodes to visit
--   next.<ul><li><i><tt>x</tt></i> undirectional: ignore edge
--   direction</li><li><i><tt>r</tt></i> reversed: walk edges in
--   reverse</li><li><i><tt>x</tt></i> user defined: speciy which paths to
--   follow</li></ul></li>
--   <li>"df" for depth-first</li>
--   <li>A structure parameter, specifying the type of the
--   result.<ul><li><i><tt>s</tt></i> Flat list of
--   results</li><li><i><tt>f</tt></i> Structured <a>Tree</a> of
--   results</li></ul></li>
--   <li>An optional "With", which instead of putting the found nodes
--   directly into the result, adds the result of a computation on them
--   into it.</li>
--   <li>An optional prime character, in which case all nodes of the graph
--   will be visited, instead of a user-given subset.</li>
--   </ol>
module Data.Graph.Inductive.Query.DFS
type CFun a b c = Context a b -> c

-- | Depth-first search.
dfs :: Graph gr => [Node] -> gr a b -> [Node]
dfs' :: Graph gr => gr a b -> [Node]

-- | Directed depth-first forest.
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]

-- | Most general DFS algorithm to create a list of results. The other
--   list-returning functions such as <a>dfs</a> are all defined in terms
--   of this one.
--   
--   <pre>
--   <a>xdfsWith</a> d f vs = <a>preorderF</a> . <a>xdffWith</a> d f vs
--   </pre>
xdfsWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [c]

-- | Most general DFS algorithm to create a forest of results, otherwise
--   very similar to <a>xdfsWith</a>. The other forest-returning functions
--   such as <a>dff</a> are all defined in terms of this one.
xdfWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> ([Tree c], gr a b)

-- | Discard the graph part of the result of <a>xdfWith</a>.
--   
--   <pre>
--   xdffWith d f vs g = fst (xdfWith d f vs g)
--   </pre>
xdffWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [Tree c]

-- | Undirected depth-first search, obtained by following edges regardless
--   of their direction.
udfs :: Graph gr => [Node] -> gr a b -> [Node]
udfs' :: Graph gr => gr a b -> [Node]

-- | Undirected depth-first forest, obtained by following edges regardless
--   of their direction.
udff :: Graph gr => [Node] -> gr a b -> [Tree Node]
udff' :: Graph gr => gr a b -> [Tree Node]
udffWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [Tree c]
udffWith' :: Graph gr => CFun a b c -> gr a b -> [Tree c]

-- | Reverse depth-first forest, obtained by following predecessors.
rdff :: Graph gr => [Node] -> gr a b -> [Tree Node]
rdff' :: Graph gr => gr a b -> [Tree Node]

-- | Reverse depth-first search, obtained by following predecessors.
rdfs :: Graph gr => [Node] -> gr a b -> [Node]
rdfs' :: Graph gr => gr a b -> [Node]
rdffWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [Tree c]
rdffWith' :: Graph gr => CFun a b c -> gr a b -> [Tree c]

-- | <a>Topological sorting</a>, i.e. a list of <a>Node</a>s so that if
--   there's an edge between a source and a target node, the source appears
--   earlier in the result.
topsort :: Graph gr => gr a b -> [Node]

-- | <a>topsort</a>, returning only the labels of the nodes.
topsort' :: Graph gr => gr a b -> [a]

-- | Collection of strongly connected components
scc :: Graph gr => gr a b -> [[Node]]

-- | Collection of nodes reachable from a starting point.
reachable :: Graph gr => Node -> gr a b -> [Node]

-- | Collection of connected components
components :: Graph gr => gr a b -> [[Node]]

-- | Number of connected components
noComponents :: Graph gr => gr a b -> Int

-- | Is the graph connected?
isConnected :: Graph gr => gr a b -> Bool

-- | The condensation of the given graph, i.e., the graph of its strongly
--   connected components.
condensation :: Graph gr => gr a b -> gr [Node] ()

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)]


-- | Maximum Independent Node Sets
module Data.Graph.Inductive.Query.Indep

-- | Calculate the maximum independent node set of the specified graph.
indep :: DynGraph gr => gr a b -> [Node]

-- | The maximum independent node set along with its size.
indepSize :: DynGraph gr => gr a b -> ([Node], Int)


-- | 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
newtype 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)</li>
--   <li>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 Monad m => Monad (GT m g)
instance Monad m => Applicative (GT m g)
instance Monad m => Functor (GT m g)

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 ()


-- | Tree-based implementation of <a>Graph</a> and <a>DynGraph</a>
--   
--   You will probably have better performance using the
--   <a>Data.Graph.Inductive.PatriciaTree</a> implementation instead.
module Data.Graph.Inductive.Tree
data Gr a b
type UGr = Gr () ()
instance Generic (Gr a b)
instance Datatype D1Gr
instance Constructor C1_0Gr
instance (NFData a, NFData b) => NFData (Gr a b)
instance DynGraph Gr
instance Graph Gr
instance (Read a, Read b) => Read (Gr a b)
instance (Show a, Show b) => Show (Gr a b)
instance (Eq a, Ord b) => Eq (Gr a b)


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

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
type RTree = [Path]
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 <tt>G=(V,E)</tt> with source <tt>s</tt>
--   and sink <tt>t</tt> where each edge <tt>(u,v)</tt> in <tt>E</tt> has a
--   nonnegative capacity <tt>c(u,v)&gt;=0</tt>, and we wish to find a flow
--   of maximum value from <tt>s</tt> to <tt>t</tt>.
--   
--   A flow in <tt>G=(V,E)</tt> is a real-valued function
--   <tt>f:VxV-&gt;R</tt> 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 <tt>|f|=Sum {f(s,v)|v in V}</tt>,
--   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 <tt>s</tt> to
--   <tt>t</tt> 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 => [Edge] -> [LEdge 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) => gr a b -> gr a (b, b, b)

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

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

-- | Compute the flow from <tt>s</tt> to <tt>t</tt> on a graph whose edges
--   are labeled with <tt>(x,y,z)=(max capacity,current flow,residual
--   capacity)</tt> and all edges are of the form <tt>a&lt;----&gt;b</tt>.
--   First compute the residual graph, that is, delete those edges whose
--   residual capacity is zero. Then compute the shortest augmenting path
--   from <tt>s</tt> to <tt>t</tt>, 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 <tt>s</tt>
--   to <tt>t</tt> 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
--   <tt>x</tt>, 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 graph 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


-- | 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 Eq Direction
instance Ord Direction
instance Show Direction
instance Read Direction


-- | Pairing heap implementation of dictionary
module Data.Graph.Inductive.Internal.Heap
data Heap a b
Empty :: Heap a b
Node :: a -> b -> [Heap a b] -> Heap a b
prettyHeap :: (Show a, Show b) => Heap a b -> String
printPrettyHeap :: (Show a, Show b) => Heap a b -> IO ()
empty :: Heap a b
unit :: 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 :: Heap a b -> Bool
findMin :: 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 (Eq a, Eq b) => Eq (Heap a b)
instance (Show a, Show b) => Show (Heap a b)
instance (Read a, Read b) => Read (Heap a b)
instance (NFData a, NFData b) => NFData (Heap a b)


-- | 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 :: LRTree b -> Node -> Node -> Path
type LRTree a = [LPath a]


-- | Shortest path algorithms
module Data.Graph.Inductive.Query.SP

-- | Tree of shortest paths from a certain node to the rest of the
--   (reachable) nodes.
--   
--   Corresponds to <a>dijkstra</a> applied to a heap in which the only
--   known node is the starting node, with a path of length 0 leading to
--   it.
spTree :: (Graph gr, Real b) => Node -> gr a b -> LRTree b

-- | Shortest path between two nodes.
sp :: (Graph gr, Real b) => Node -> Node -> gr a b -> Path

-- | Length of the shortest path between two nodes.
spLength :: (Graph gr, Real b) => Node -> Node -> gr a b -> b

-- | Dijkstra's shortest path algorithm.
dijkstra :: (Graph gr, Real b) => Heap b (LPath b) -> gr a b -> LRTree b
type LRTree a = [LPath a]
data Heap a b


-- | Graph Voronoi Diagram
--   
--   These functions can be used to create a <i>shortest path forest</i>
--   where the roots are specified.
module Data.Graph.Inductive.Query.GVD

-- | Representation of a shortest path forest.
type Voronoi a = LRTree a
type LRTree a = [LPath a]

-- | Produce a shortest path forest (the roots of which are those nodes
--   specified) from nodes in the graph <i>to</i> one of the root nodes (if
--   possible).
gvdIn :: (DynGraph gr, Real b) => [Node] -> gr a b -> Voronoi b

-- | Produce a shortest path forest (the roots of which are those nodes
--   specified) from nodes in the graph <i>from</i> one of the root nodes
--   (if possible).
gvdOut :: (Graph gr, Real b) => [Node] -> gr a b -> Voronoi b

-- | Return the nodes reachable to/from (depending on how the
--   <a>Voronoi</a> was constructed) from the specified root node (if the
--   specified node is not one of the root nodes of the shortest path
--   forest, an empty list will be returned).
voronoiSet :: Node -> Voronoi b -> [Node]

-- | Try to determine the nearest root node to the one specified in the
--   shortest path forest.
nearestNode :: Real b => Node -> Voronoi b -> Maybe Node

-- | The distance to the <a>nearestNode</a> (if there is one) in the
--   shortest path forest.
nearestDist :: Node -> Voronoi b -> Maybe b

-- | Try to construct a path to/from a specified node to one of the root
--   nodes of the shortest path forest.
nearestPath :: Node -> Voronoi b -> Maybe Path

module Data.Graph.Inductive.Query

module Data.Graph.Inductive

-- | Version info
version :: IO ()