Data.Graph.Wrapper.Circular

Documentation

newtype Graph i v

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

Fields

• graphVertices :: Map i (Vertex i v)

Instances

(Ord i, Eq v) => Eq (Graph i v)

Methods

(==) :: Graph i v -> Graph i v -> Bool

(/=) :: Graph i v -> Graph i v -> Bool

data Vertex i v

Constructors

Vertex

Fields

• vertexLabel :: v
• vertexNeighbours :: Map i (Vertex i v)

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

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

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

O(n log n + k)