acme-circular-containers-0.1.0.0: Spineless containers which are fast to read but inefficient to update

Data.Graph.Wrapper.Circular

Synopsis

# Documentation

newtype Graph i v Source #

A graph-based representation of a Graph: a bunch of vertices (each with a unique i), each holding a value of type v and pointers to the neighbours of the vertex.

Graphs are not typically represented this way because if the graph has a cycle in it, we will not be able to make any changes to the graph without reallocating all the nodes which are part of that cycle and all the nodes which point to it. For this reason, we do not offer any update operations.

Constructors

 Graph FieldsgraphVertices :: Map i (Vertex i v)
Instances
 (Ord i, Eq v) => Eq (Graph i v) Source # Instance detailsMethods(==) :: Graph i v -> Graph i v -> Bool #(/=) :: Graph i v -> Graph i v -> Bool #

data Vertex i v Source #

Constructors

 Vertex FieldsvertexLabel :: v vertexNeighbours :: Map i (Vertex i v)

freeze :: forall i v. Ord i => Graph i v -> Graph i v Source #

freeze :: Ord i
-> Data.Graph.Wrapper.Graph i v
-> Data.Graph.Wrapper.Circular.Graph i v

O(n log n + k log k + k log n)

thaw :: forall i v. Ord i => Graph i v -> Graph i v Source #

thaw :: Ord i
-> Data.Graph.Wrapper.Circular.Graph i v
-> Data.Graph.Wrapper.Graph i v

O(n log n + k)