Safe Haskell | None |
---|---|
Language | Haskell2010 |
This module implements full dynamic grah connectivity.
It is based on: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity by Jacob Holm, Kristian de Lichtenberg and Mikkel Thorup (1998).
We use two naming conventions in this module:
Synopsis
- data Graph t s v
- type Graph' s v = Graph Tree s v
- empty :: (Eq v, Hashable v, Tree t, PrimMonad m) => m (Graph t (PrimState m) v)
- empty' :: (Eq v, Hashable v, PrimMonad m) => m (Graph' (PrimState m) v)
- edgeless :: (Eq v, Hashable v, Tree t, PrimMonad m) => [v] -> m (Graph t (PrimState m) v)
- edgeless' :: (Eq v, Hashable v, PrimMonad m) => [v] -> m (Graph' (PrimState m) v)
- complete :: (Eq v, Hashable v, Tree t, PrimMonad m) => [v] -> m (Graph t (PrimState m) v)
- complete' :: (Eq v, Hashable v, PrimMonad m) => [v] -> m (Graph' (PrimState m) v)
- connected :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m Bool
- edge :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m Bool
- vertex :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m Bool
- neighbours :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m (HashSet v)
- link :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m Bool
- link_ :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m ()
- cut :: forall t m v. (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m Bool
- cut_ :: forall t m v. (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m ()
- insert :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m Bool
- insert_ :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m ()
- delete :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m Bool
- delete_ :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m ()
- spanningForest :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> m (Forest v)
Type
Construction
empty :: (Eq v, Hashable v, Tree t, PrimMonad m) => m (Graph t (PrimState m) v) Source #
O(1)
Create an empty graph.
empty' :: (Eq v, Hashable v, PrimMonad m) => m (Graph' (PrimState m) v) Source #
Simple version of empty
.
edgeless :: (Eq v, Hashable v, Tree t, PrimMonad m) => [v] -> m (Graph t (PrimState m) v) Source #
Create a graph with the given vertices but no edges.
edgeless' :: (Eq v, Hashable v, PrimMonad m) => [v] -> m (Graph' (PrimState m) v) Source #
Simple version of edgeless
.
complete :: (Eq v, Hashable v, Tree t, PrimMonad m) => [v] -> m (Graph t (PrimState m) v) Source #
Create the complete graph with the given vertices.
complete' :: (Eq v, Hashable v, PrimMonad m) => [v] -> m (Graph' (PrimState m) v) Source #
Simple version of complete
Queries
connected :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m Bool Source #
O(log(v))
Check if a path exists in between two vertices.
edge :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m Bool Source #
Check if this edge exists in the graph.
vertex :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m Bool Source #
Check if this vertex exists in the graph.
neighbours :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m (HashSet v) Source #
Get all neighbours of the given vertex.
Modifying
link :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m Bool Source #
O(log(v))
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 () Source #
Version of link
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 Bool Source #
Ammortized O(log² v)
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 () Source #
Version of cut
which ignores the result.
insert :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m Bool Source #
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 () Source #
Version of insert
which ignores the result.
delete :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m Bool Source #
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 () Source #
Version of delete
which ignores the result.