Data.Graph.Dynamic.Levels

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:

• A prime suffix (') indicates a simpler or less polymorphic version of a function or datatype. For example, see empty and empty', and Graph and Graph'.
• An underscore suffix (_) means that the return value is ignored. For example, see link and link_.

Type

data Graph t s v

type Graph' s v = Graph Tree s v

Construction

empty :: (Eq v, Hashable v, Tree t, PrimMonad m) => m (Graph t (PrimState m) v)

O(1)

Create an empty graph.

empty' :: (Eq v, Hashable v, PrimMonad m) => m (Graph' (PrimState m) v)

Simple version of empty.

edgeless :: (Eq v, Hashable v, Tree t, PrimMonad m) => [v] -> m (Graph t (PrimState m) v)

Create a graph with the given vertices but no edges.

edgeless' :: (Eq v, Hashable v, PrimMonad m) => [v] -> m (Graph' (PrimState m) v)

Simple version of edgeless.

complete :: (Eq v, Hashable v, Tree t, PrimMonad m) => [v] -> m (Graph t (PrimState m) v)

Create the complete graph with the given vertices.

complete' :: (Eq v, Hashable v, PrimMonad m) => [v] -> m (Graph' (PrimState m) v)

Simple version of complete

Queries

connected :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> v -> m Bool

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

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

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)

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

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

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

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

Version of cut which ignores the result.

insert :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m Bool

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

Version of insert which ignores the result.

delete :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> v -> m Bool

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

Version of delete which ignores the result.

Advanced/internal

spanningForest :: (Eq v, Hashable v, Tree t, PrimMonad m) => Graph t (PrimState m) v -> m (Forest v)

Obtain the current spanning forest.