Safe Haskell	None
Language	Haskell2010

Data.Graph.Haggle.Digraph

Description

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.

Synopsis

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

Documentation

data MDigraph m Source #

This is a compact (mutable) directed graph.

Instances

Instances details

MAddEdge MDigraph Source #
Instance details Defined in Data.Graph.Haggle.Digraph Methods addEdge :: (PrimMonad m, MonadRef m) => MDigraph m -> Vertex -> Vertex -> m (Maybe Edge) Source #
MAddVertex MDigraph Source #
Instance details Defined in Data.Graph.Haggle.Digraph Methods addVertex :: (PrimMonad m, MonadRef m) => MDigraph m -> m Vertex Source #
MGraph MDigraph Source #
Instance details Defined in Data.Graph.Haggle.Digraph Associated Types type ImmutableGraph MDigraph Source # Methods getVertices :: (PrimMonad m, MonadRef m) => MDigraph m -> m [Vertex] Source # getSuccessors :: (PrimMonad m, MonadRef m) => MDigraph m -> Vertex -> m [Vertex] Source # getOutEdges :: (PrimMonad m, MonadRef m) => MDigraph m -> Vertex -> m [Edge] Source # countVertices :: (PrimMonad m, MonadRef m) => MDigraph m -> m Int Source # countEdges :: (PrimMonad m, MonadRef m) => MDigraph m -> m Int Source # checkEdgeExists :: (PrimMonad m, MonadRef m) => MDigraph m -> Vertex -> Vertex -> m Bool Source # freeze :: (PrimMonad m, MonadRef m) => MDigraph m -> m (ImmutableGraph MDigraph) Source #
type ImmutableGraph MDigraph Source #
Instance details Defined in Data.Graph.Haggle.Digraph type ImmutableGraph MDigraph = Digraph

data Digraph Source #

Instances

Instances details

NFData Digraph Source #	The `Digraph` is always in normal form, as the vectors are all unboxed
Instance details Defined in Data.Graph.Haggle.Digraph Methods rnf :: Digraph -> () #
Thawable Digraph Source #
Instance details Defined in Data.Graph.Haggle.Digraph Associated Types type MutableGraph Digraph :: (Type -> Type) -> Type Source # Methods thaw :: (PrimMonad m, MonadRef m) => Digraph -> m (MutableGraph Digraph m) Source #
Graph Digraph Source #
Instance details Defined in Data.Graph.Haggle.Digraph Methods vertices :: Digraph -> [Vertex] Source # edges :: Digraph -> [Edge] Source # successors :: Digraph -> Vertex -> [Vertex] Source # outEdges :: Digraph -> Vertex -> [Edge] Source # maxVertexId :: Digraph -> Int Source # isEmpty :: Digraph -> Bool Source # edgesBetween :: Digraph -> Vertex -> Vertex -> [Edge] Source #
type MutableGraph Digraph Source #
Instance details Defined in Data.Graph.Haggle.Digraph type MutableGraph Digraph = MDigraph

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

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) Source #

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

g <- newSizedMDigraph szVerts szEdges