Data.Graph.Haggle.Digraph

This graph implementation is a directed (multi-)graph that only tracks successors. This encoding is very compact. It is a multi-graph because it allows parallel edges between vertices. If you require only simple graphs, careful edge insertion is required (or another graph type might be more appropriate).

Limitations:

• Removing nodes and edges is not currently possible.
• Predecessors are not accessible
• Edge existence tests are linear in the number of edges for the source node.

Documentation

data MDigraph m

This is a compact (mutable) directed graph.

Instances

MAddEdge MDigraph

Defined in Data.Graph.Haggle.Digraph

Methods

addEdge :: (PrimMonad m, MonadRef m) => MDigraph m -> Vertex -> Vertex -> m (Maybe Edge)

MAddVertex MDigraph

Defined in Data.Graph.Haggle.Digraph

Methods

addVertex :: (PrimMonad m, MonadRef m) => MDigraph m -> m Vertex

MGraph MDigraph

Defined in Data.Graph.Haggle.Digraph

Associated Types

type ImmutableGraph MDigraph

Methods

getVertices :: (PrimMonad m, MonadRef m) => MDigraph m -> m [Vertex]

getSuccessors :: (PrimMonad m, MonadRef m) => MDigraph m -> Vertex -> m [Vertex]

getOutEdges :: (PrimMonad m, MonadRef m) => MDigraph m -> Vertex -> m [Edge]

countVertices :: (PrimMonad m, MonadRef m) => MDigraph m -> m Int

countEdges :: (PrimMonad m, MonadRef m) => MDigraph m -> m Int

checkEdgeExists :: (PrimMonad m, MonadRef m) => MDigraph m -> Vertex -> Vertex -> m Bool

freeze :: (PrimMonad m, MonadRef m) => MDigraph m -> m (ImmutableGraph MDigraph)

type ImmutableGraph MDigraph

Defined in Data.Graph.Haggle.Digraph

type ImmutableGraph MDigraph = Digraph

data Digraph

Instances

NFData Digraph

The Digraph is always in normal form, as the vectors are all unboxed

Defined in Data.Graph.Haggle.Digraph

Methods

rnf :: Digraph -> ()

Thawable Digraph

Defined in Data.Graph.Haggle.Digraph

Associated Types

type MutableGraph Digraph :: (Type -> Type) -> Type

Methods

thaw :: (PrimMonad m, MonadRef m) => Digraph -> m (MutableGraph Digraph m)

Graph Digraph

Defined in Data.Graph.Haggle.Digraph

Methods

vertices :: Digraph -> [Vertex]

edges :: Digraph -> [Edge]

successors :: Digraph -> Vertex -> [Vertex]

outEdges :: Digraph -> Vertex -> [Edge]

maxVertexId :: Digraph -> Int

isEmpty :: Digraph -> Bool

edgesBetween :: Digraph -> Vertex -> Vertex -> [Edge]

type MutableGraph Digraph

Defined in Data.Graph.Haggle.Digraph

type MutableGraph Digraph = MDigraph

newMDigraph :: (PrimMonad m, MonadRef m) => m (MDigraph m)

Create a new empty mutable graph with a small amount of storage reserved for vertices and edges.

newSizedMDigraph :: (PrimMonad m, MonadRef m) => Int -> Int -> m (MDigraph m)

Create a new empty graph with storage reserved for szVerts vertices and szEdges edges.

g <- newSizedMDigraph szVerts szEdges