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


-- | Dynamic graph algorithms
--   
--   A library for dynamic graph algorithms, and in particular dynamic
--   connectivity.
@package dynamic-graphs
@version 0.1.0.2


-- | This is a very simple wrapper around the <tt>hashtables</tt> library
--   that uses <a>PrimMonad</a> rather than <tt>ST</tt>.
module Data.Graph.Dynamic.Internal.HashTable
type HashTable s k v = HashTable s k v
new :: PrimMonad m => m (HashTable (PrimState m) k v)
insert :: (Eq k, Hashable k, PrimMonad m) => HashTable (PrimState m) k v -> k -> v -> m ()
delete :: (Eq k, Hashable k, PrimMonad m) => HashTable (PrimState m) k v -> k -> m ()
lookup :: (Eq k, Hashable k, PrimMonad m) => HashTable (PrimState m) k v -> k -> m (Maybe v)

-- | Slow, only for debugging and testing.
toList :: PrimMonad m => HashTable (PrimState m) k v -> m [(k, v)]

module Data.Graph.Dynamic.Internal.Tree

-- | The chosen represenation of the tree has a big impact on the
--   performance of the algorithms. This typeclass allows us to swap them
--   out more easily.
class Tree (t :: * -> * -> * -> *) where {
    
    -- | A management structure used to create new trees
    type family TreeGen t :: * -> *;
}

-- | Create a tree gen itself
newTreeGen :: (Tree t, PrimMonad m) => Proxy t -> m (TreeGen t (PrimState m))

-- | Create a tree with a single element.
singleton :: (Tree t, PrimMonad m, Monoid v) => TreeGen t (PrimState m) -> a -> v -> m (t (PrimState m) a v)

-- | Join two trees together.
append :: (Tree t, PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v)

-- | Prepend a singleton tree
cons :: (Tree t, PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v)

-- | Append a singleton tree
snoc :: (Tree t, PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v)

-- | Split a tree, turning the argument into a singleton and returning the
--   left and right halves of the tree.
split :: (Tree t, PrimMonad m, Monoid v) => t (PrimState m) a v -> m (Maybe (t (PrimState m) a v), Maybe (t (PrimState m) a v))

-- | Check if two nodes belong to the same tree
connected :: (Tree t, PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m Bool

-- | Find the root of a tree
root :: (Tree t, PrimMonad m, Monoid v) => t (PrimState m) a v -> m (t (PrimState m) a v)

-- | Read the root of a tree. This is not allowed to modify the tree (e.g.,
--   no splaying allowed).
readRoot :: (Tree t, PrimMonad m, Monoid v) => t (PrimState m) a v -> m (t (PrimState m) a v)

-- | Read the label from a tree
label :: (Tree t, PrimMonad m, Monoid v) => t (PrimState m) a v -> m a

-- | Read the aggregate of a tree
aggregate :: (Tree t, PrimMonad m, Monoid v) => t (PrimState m) a v -> m v

-- | Convert a tree to a list
toList :: (Tree t, PrimMonad m, Monoid v) => t (PrimState m) a v -> m [a]
concat :: forall t m a v. (Tree t, PrimMonad m, Monoid v) => NonEmpty (t (PrimState m) a v) -> m (t (PrimState m) a v)

-- | These methods can be used for testing and debugging.
class Tree t => TestTree t
print :: (TestTree t, Show a) => t (PrimState IO) a v -> IO ()
assertInvariants :: (TestTree t, PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m ()
assertSingleton :: (TestTree t, PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m ()
assertRoot :: (TestTree t, PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m ()

module Data.Graph.Dynamic.Internal.Splay
data Tree s a v
singleton :: PrimMonad m => a -> v -> m (Tree (PrimState m) a v)

-- | <tt>lv</tt> must be a singleton tree
cons :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v)

-- | <tt>rv</tt> must be a singleton tree
snoc :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v)

-- | Appends two trees. Returns the root of the tree.
append :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v)
split :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m (Maybe (Tree (PrimState m) a v), Maybe (Tree (PrimState m) a v))
connected :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m Bool
root :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m (Tree (PrimState m) a v)
aggregate :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m v

-- | For debugging/testing.
toList :: PrimMonad m => Tree (PrimState m) a v -> m [a]
readRoot :: PrimMonad m => Tree (PrimState m) a v -> m (Tree (PrimState m) a v)

-- | For debugging/testing.
freeze :: PrimMonad m => Tree (PrimState m) a v -> m (Tree a)
print :: Show a => Tree (PrimState IO) a v -> IO ()
assertInvariants :: (PrimMonad m, Monoid v, Eq v, Show v) => Tree (PrimState m) a v -> m ()
instance GHC.Classes.Eq (Data.Graph.Dynamic.Internal.Splay.Tree s a v)
instance Data.Graph.Dynamic.Internal.Tree.Tree Data.Graph.Dynamic.Internal.Splay.Tree
instance Data.Graph.Dynamic.Internal.Tree.TestTree Data.Graph.Dynamic.Internal.Splay.Tree


-- | Randomly balanced tree.
module Data.Graph.Dynamic.Internal.Random
data Tree s a v
singleton :: PrimMonad m => Gen (PrimState m) -> a -> v -> m (Tree (PrimState m) a v)

-- | Appends two trees. Returns the root of the tree.
append :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v)
split :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m (Maybe (Tree (PrimState m) a v), Maybe (Tree (PrimState m) a v))
connected :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m Bool
root :: PrimMonad m => Tree (PrimState m) a v -> m (Tree (PrimState m) a v)
label :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m a
aggregate :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m v

-- | For debugging/testing.
toList :: PrimMonad m => Tree (PrimState m) a v -> m [a]

-- | For debugging/testing.
freeze :: PrimMonad m => Tree (PrimState m) a v -> m (Tree a)
print :: Show a => Tree (PrimState IO) a v -> IO ()
assertInvariants :: (PrimMonad m, Monoid v, Eq v, Show v) => Tree (PrimState m) a v -> m ()
assertSingleton :: PrimMonad m => Tree (PrimState m) a v -> m ()
assertRoot :: PrimMonad m => Tree (PrimState m) a v -> m ()
instance GHC.Classes.Eq (Data.Graph.Dynamic.Internal.Random.Tree s a v)
instance Data.Graph.Dynamic.Internal.Tree.Tree Data.Graph.Dynamic.Internal.Random.Tree
instance Data.Graph.Dynamic.Internal.Tree.TestTree Data.Graph.Dynamic.Internal.Random.Tree

module Data.Graph.Dynamic.Internal.Avl
data Tree s a v
singleton :: PrimMonad m => a -> v -> m (Tree (PrimState m) a v)
append :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v)
concat :: (PrimMonad m, Monoid v) => NonEmpty (Tree (PrimState m) a v) -> m (Tree (PrimState m) a v)
join :: (PrimMonad m, Monoid v) => Maybe (Tree (PrimState m) a v) -> Tree (PrimState m) a v -> Maybe (Tree (PrimState m) a v) -> m (Tree (PrimState m) a v)
split :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m (Maybe (Tree (PrimState m) a v), Maybe (Tree (PrimState m) a v))
root :: PrimMonad m => Tree (PrimState m) a v -> m (Tree (PrimState m) a v)
connected :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m Bool
label :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m a
aggregate :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m v

-- | For debugging/testing.
toList :: PrimMonad m => Tree (PrimState m) a v -> m [a]

-- | For debugging/testing.
freeze :: PrimMonad m => Tree (PrimState m) a v -> m (Tree a)
print :: Show a => Tree (PrimState IO) a v -> IO ()
assertInvariants :: (PrimMonad m, Monoid v, Eq v, Show v) => Tree (PrimState m) a v -> m ()
assertSingleton :: PrimMonad m => Tree (PrimState m) a v -> m ()
assertRoot :: PrimMonad m => Tree (PrimState m) a v -> m ()
instance GHC.Show.Show v => GHC.Show.Show (Data.Graph.Dynamic.Internal.Avl.Aggs v)
instance GHC.Classes.Eq v => GHC.Classes.Eq (Data.Graph.Dynamic.Internal.Avl.Aggs v)
instance Data.Graph.Dynamic.Internal.Tree.Tree Data.Graph.Dynamic.Internal.Avl.Tree
instance GHC.Classes.Eq (Data.Graph.Dynamic.Internal.Avl.Tree s a v)
instance Data.Graph.Dynamic.Internal.Tree.TestTree Data.Graph.Dynamic.Internal.Avl.Tree


-- | This module provides dynamic connectivity for an acyclic graph (i.e. a
--   forest).
--   
--   It is based on: <i>Finding biconnected components and computing tree
--   functions in logarithmic parallel time</i> by <i>Robert E. Tarjan and
--   Uzi Vishki</i> (1984).
--   
--   We use two naming conventions in this module:
--   
--   <ul>
--   <li>A prime suffix (<tt>'</tt>) indicates a simpler or less
--   polymorphic version of a function or datatype. For example, see
--   <a>empty</a> and <a>empty'</a>, and <a>Graph</a> and
--   <a>Graph'</a>.</li>
--   <li>An underscore suffix (<tt>_</tt>) means that the return value is
--   ignored. For example, see <a>link</a> and <a>link_</a>.</li>
--   </ul>
module Data.Graph.Dynamic.EulerTour

-- | The most general type for an Euler Tour Forest. Used by other modules.
data Forest t a s v

-- | Graph type polymorphic in the tree used to represent sequences.
type Graph t s v = Forest t () s v

-- | Simple graph type.
type Graph' s v = Graph Tree s v

-- | <i>O(1)</i>
--   
--   Create the empty tree.
empty :: forall t m v a. (Tree t, PrimMonad m) => (v -> v -> a) -> m (Forest t a (PrimState m) v)

-- | Simple version of <a>empty</a>.
empty' :: PrimMonad m => m (Graph' (PrimState m) v)

-- | <i>O(v*log(v))</i>
--   
--   Create a graph with the given vertices but no edges.
edgeless :: (Eq v, Hashable v, Tree t, PrimMonad m, Monoid a) => (v -> v -> a) -> [v] -> m (Forest t a (PrimState m) v)

-- | Simple version of <a>edgeless</a>.
edgeless' :: (Eq v, Hashable v, PrimMonad m) => [v] -> m (Graph' (PrimState m) v)

-- | Create a graph from a <a>Tree</a>. Note that the values in nodes must
--   be unique.
fromTree :: forall v m t a. (Eq v, Hashable v, Tree t, PrimMonad m, Monoid a) => (v -> v -> a) -> Tree v -> m (Forest t a (PrimState m) v)

-- | Simple version of <a>fromTree</a>.
fromTree' :: (Eq v, Hashable v, PrimMonad m) => Tree v -> m (Graph' (PrimState m) v)

-- | <i>O(log(v))</i>
--   
--   Check if a path exists in between two vertices.
connected :: (Eq v, Hashable v, Tree t, PrimMonad m, Monoid a) => Forest t a (PrimState m) v -> v -> v -> m Bool

-- | <i>O(log(v))</i>
--   
--   Check if this edge exists in the graph.
edge :: (Eq v, Hashable v, Tree t, PrimMonad m) => Forest t a (PrimState m) v -> v -> v -> m Bool

-- | <i>O(log(v))</i>
--   
--   Check if this vertex exists in the graph.
vertex :: (Eq v, Hashable v, Tree t, PrimMonad m) => Forest t a (PrimState m) v -> v -> m Bool

-- | <i>O(log(v) + n</i> where <i>n</i> is the number of neighbours
--   
--   Get all neighbours of the given vertex.
neighbours :: (Eq v, Hashable v, Tree t, PrimMonad m, Monoid a) => Forest t a (PrimState m) v -> v -> m [v]

-- | <i>O(log(v))</i>
--   
--   Insert an edge in between two vertices. If the vertices are already
--   connected, we don't do anything, since this is an acyclic graph.
--   Returns whether or not an edge was actually inserted.
link :: (Eq v, Hashable v, Tree t, PrimMonad m, Monoid a) => Forest t a (PrimState m) v -> v -> v -> m Bool

-- | Version of <a>link</a> which ignores the result.
link_ :: (Eq v, Hashable v, Tree t, PrimMonad m, Monoid a) => Forest t a (PrimState m) v -> v -> v -> m ()

-- | <i>O(log(v))</i>
--   
--   Remove an edge in between two vertices. If there is no edge in between
--   these vertices, do nothing. Return whether or not an edge was actually
--   removed.
cut :: (Eq v, Hashable v, Tree t, PrimMonad m, Monoid a) => Forest t a (PrimState m) v -> v -> v -> m Bool

-- | Version of <a>cut</a> which ignores the result.
cut_ :: (Eq v, Hashable v, Tree t, PrimMonad m, Monoid a) => Forest t a (PrimState m) v -> v -> v -> m ()

-- | <i>O(log(v))</i>
--   
--   Insert a new vertex. Do nothing if it is already there. Returns
--   whether or not a vertex was inserted in the graph.
insert :: (Eq v, Hashable v, Tree t, PrimMonad m, Monoid a) => Forest t a (PrimState m) v -> v -> m Bool

-- | Version of <a>insert</a> which ignores the result.
insert_ :: (Eq v, Hashable v, Tree t, PrimMonad m, Monoid a) => Forest t a (PrimState m) v -> v -> m ()

-- | <i>O(n*log(v))</i> where <i>n</i> is the number of neighbours
--   
--   Remove a vertex from the graph, if it exists. If it is connected to
--   any other vertices, those edges are cut first. Returns whether or not
--   a vertex was removed from the graph.
delete :: (Eq v, Hashable v, Tree t, PrimMonad m, Monoid a) => Forest t a (PrimState m) v -> v -> m Bool

-- | Version of <a>delete</a> which ignores the result.
delete_ :: (Eq v, Hashable v, Tree t, PrimMonad m, Monoid a) => Forest t a (PrimState m) v -> v -> m ()
findRoot :: (Eq v, Hashable v, Tree t, PrimMonad m, s ~ PrimState m, Monoid a) => Forest t a s v -> v -> m (Maybe (t s (v, v) a))
componentSize :: (Eq v, Hashable v, Tree t, PrimMonad m, s ~ PrimState m) => Forest t (Sum Int) s v -> v -> m Int

-- | Obtain the current spanning forest.
spanningForest :: (Eq v, Hashable v, Tree t, Monoid a, PrimMonad m) => Forest t a (PrimState m) v -> m (Forest v)
print :: (Show a, Monoid b, TestTree t) => Forest t b RealWorld a -> IO ()


-- | This module implements full dynamic grah connectivity.
--   
--   It is based on: <i>Poly-logarithmic deterministic fully-dynamic
--   algorithms for connectivity, minimum spanning tree, 2-edge, and
--   biconnectivity</i> by <i>Jacob Holm, Kristian de Lichtenberg and
--   Mikkel Thorup</i> (1998).
--   
--   We use two naming conventions in this module:
--   
--   <ul>
--   <li>A prime suffix (<tt>'</tt>) indicates a simpler or less
--   polymorphic version of a function or datatype. For example, see
--   <a>empty</a> and <a>empty'</a>, and <a>Graph</a> and
--   <a>Graph'</a>.</li>
--   <li>An underscore suffix (<tt>_</tt>) means that the return value is
--   ignored. For example, see <a>link</a> and <a>link_</a>.</li>
--   </ul>
module Data.Graph.Dynamic.Levels
data Graph t s v
type Graph' s v = Graph Tree s v

-- | <i>O(1)</i>
--   
--   Create an empty graph.
empty :: (Eq v, Hashable v, Tree t, PrimMonad m) => m (Graph t (PrimState m) v)

-- | Simple version of <a>empty</a>.
empty' :: (Eq v, Hashable v, PrimMonad m) => m (Graph' (PrimState m) v)

-- | Create a graph with the given vertices but no edges.
edgeless :: (Eq v, Hashable v, Tree t, PrimMonad m) => [v] -> m (Graph t (PrimState m) v)

-- | Simple version of <a>edgeless</a>.
edgeless' :: (Eq v, Hashable v, PrimMonad m) => [v] -> m (Graph' (PrimState m) v)

-- | Create the complete graph with the given vertices.
complete :: (Eq v, Hashable v, Tree t, PrimMonad m) => [v] -> m (Graph t (PrimState m) v)

-- | Simple version of <a>complete</a>
complete' :: (Eq v, Hashable v, PrimMonad m) => [v] -> m (Graph' (PrimState m) v)

-- | <i>O(log(v))</i>
--   
--   Check if a path exists in between two vertices.
connected :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m Bool

-- | Check if this edge exists in the graph.
edge :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m Bool

-- | Check if this vertex exists in the graph.
vertex :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m Bool

-- | Get all neighbours of the given vertex.
neighbours :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m (HashSet v)

-- | <i>O(log(v))</i>
--   
--   Insert an edge in between two vertices. If the vertices already have
--   an edge between them don't do anything. Returns whether or not an edge
--   was actually inserted.
link :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m Bool

-- | Version of <a>link</a> which ignores the result.
link_ :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m ()

-- | Ammortized <i>O(log² v)</i>
--   
--   Remove an edge in between two vertices. If there is no edge in between
--   these vertices, do nothing. Return whether or not an edge was actually
--   removed.
cut :: forall t m v. (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m Bool

-- | Version of <a>cut</a> which ignores the result.
cut_ :: forall t m v. (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m ()

-- | Insert a new vertex. Do nothing if it is already there. Returns
--   whether or not a vertex was inserted in the graph.
insert :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m Bool

-- | Version of <a>insert</a> which ignores the result.
insert_ :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m ()

-- | Remove a vertex from the graph, if it exists. If it is connected to
--   any other vertices, those edges are cut first. Returns whether or not
--   a vertex was removed from the graph.
delete :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m Bool

-- | Version of <a>delete</a> which ignores the result.
delete_ :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m ()

-- | Obtain the current spanning forest.
spanningForest :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> m (Forest v)