hbgl-0.1.0.0: A Haskell version of the Boost Graph Library

Safe HaskellNone

Data.Graph.Interface

Contents

Synopsis

Documentation

type Vertex = Int

data Edge gr

Constructors

Edge 

Fields

edgeSource :: Vertex
 
edgeTarget :: Vertex
 
edgeLabel :: EdgeLabel gr
 

Instances

Eq (EdgeLabel gr) => Eq (Edge gr) 
(Eq (Edge gr), Ord (EdgeLabel gr)) => Ord (Edge gr) 
Show (EdgeLabel gr) => Show (Edge gr) 
Hashable (EdgeLabel gr) => Hashable (Edge gr) 

class MarksVertices (VertexMarker gr) => Graph gr where

Associated Types

type EdgeLabel gr

type VertexLabel gr

type VertexMarker gr :: * -> *

Methods

isEmpty :: gr -> Bool

empty :: gr

mkGraph :: [(Vertex, VertexLabel gr)] -> [Edge gr] -> gr

maxVertex :: gr -> Vertex

Instances

(MarksVertices (VertexMarker (ImmutableDigraph k n e)), MarksVertices k) => Graph (ImmutableDigraph k n e) 
(MarksVertices (VertexMarker (Gr k n e)), MarksVertices k) => Graph (Gr k n e) 

type Adj gr = [(Vertex, EdgeLabel gr)]

data Context gr

Constructors

Context 

Fields

lpre' :: Adj gr
 
vertex' :: Vertex
 
lab' :: VertexLabel gr
 
lsuc' :: Adj gr
 

Instances

(Eq (VertexLabel gr), Eq (EdgeLabel gr), Ord (VertexLabel gr), Ord (EdgeLabel gr)) => Eq (Context gr) 

class Graph gr => InspectableGraph gr where

Methods

context :: gr -> Vertex -> Maybe (Context gr)

gelem :: Vertex -> gr -> Bool

Test if a node is in the grap. The default implementation can be overridden if desired

lab :: gr -> Vertex -> Maybe (VertexLabel gr)

Instances

(Graph (ImmutableDigraph k n e), MarksVertices k) => InspectableGraph (ImmutableDigraph k n e) 
(Graph (Gr k n e), MarksVertices k) => InspectableGraph (Gr k n e) 

class InspectableGraph gr => DecomposableGraph gr where

An interface for graphs that can *efficiently* be decomposed into a context and the remaining graph. FIXME: Define what should happen to self loops in the matched context. Should they be included or excluded? Including them has the advantage that match and & are dual operations.

Methods

match :: Vertex -> gr -> Maybe (Context gr, gr)

Instances

(InspectableGraph (Gr k n e), MarksVertices k) => DecomposableGraph (Gr k n e) 

class Graph gr => IncidenceGraph gr where

Graphs with efficient access to the outgoing edges for a given node. Minimum required implementation: out

Methods

out :: gr -> Vertex -> [Edge gr]

outDeg :: gr -> Vertex -> Int

Instances

(Graph (ImmutableDigraph k n e), MarksVertices k) => IncidenceGraph (ImmutableDigraph k n e) 
(Graph (Gr k n e), MarksVertices k) => IncidenceGraph (Gr k n e) 

class IncidenceGraph gr => BidirectionalGraph gr where

Graphs with efficient access to incoming edges. Minimum required implementation: inn

Methods

inn :: gr -> Vertex -> [Edge gr]

inDeg :: gr -> Vertex -> Int

degree :: gr -> Vertex -> Int

Instances

(IncidenceGraph (ImmutableDigraph k n e), MarksVertices k) => BidirectionalGraph (ImmutableDigraph k n e) 
(IncidenceGraph (Gr k n e), MarksVertices k) => BidirectionalGraph (Gr k n e) 

class InspectableGraph gr => AdjacencyGraph gr where

Graphs with efficient access to successor nodes. Minimum required implementation: InspectableGraph

Methods

foldSuc :: (Vertex -> EdgeLabel gr -> a -> a) -> a -> gr -> Vertex -> a

suc :: gr -> Vertex -> [Vertex]

lsuc :: gr -> Vertex -> [(Vertex, EdgeLabel gr)]

Suggested complexity: log(N)

Instances

(InspectableGraph (ImmutableDigraph k n e), MarksVertices k) => AdjacencyGraph (ImmutableDigraph k n e) 
(InspectableGraph (Gr k n e), MarksVertices k) => AdjacencyGraph (Gr k n e) 

class AdjacencyGraph gr => BidirectionalAdjacencyGraph gr where

Graphs with efficient access to predecessor nodes. Minimum required implementation: lpre or pre.

Methods

foldPre :: (Vertex -> EdgeLabel gr -> a -> a) -> a -> gr -> Vertex -> a

pre :: gr -> Vertex -> [Vertex]

lpre :: gr -> Vertex -> [(Vertex, EdgeLabel gr)]

neighbors :: gr -> Vertex -> [Vertex]

Instances

(AdjacencyGraph (ImmutableDigraph k n e), MarksVertices k) => BidirectionalAdjacencyGraph (ImmutableDigraph k n e) 
(AdjacencyGraph (Gr k n e), MarksVertices k) => BidirectionalAdjacencyGraph (Gr k n e) 

class Graph gr => AdjacencyMatrix gr where

Graphs with efficient implementations of adjacency tests.

Methods

edgesBetween :: gr -> Vertex -> Vertex -> [EdgeLabel gr]

edgeExists :: gr -> Vertex -> Vertex -> Bool

Instances

(Graph (Gr k n e), MarksVertices k) => AdjacencyMatrix (Gr k n e) 

class Graph gr => VertexListGraph gr where

Graphs with efficient access to all of the nodes in the graph. Minimum required implementation: labNodes.

Methods

labeledVertices :: gr -> [(Vertex, VertexLabel gr)]

Suggested complexity: log(N)

vertices :: gr -> [Vertex]

numVertices :: gr -> Int

Instances

(Graph (ImmutableDigraph k n e), MarksVertices k) => VertexListGraph (ImmutableDigraph k n e) 
(Graph (Gr k n e), MarksVertices k) => VertexListGraph (Gr k n e) 

class Graph gr => EdgeListGraph gr where

Graphs with efficient access to all of the edges in the graph. Minimum required implementation: edges.

Methods

edges :: gr -> [Edge gr]

numEdges :: gr -> Int

Instances

(Graph (ImmutableDigraph k n e), MarksVertices k) => EdgeListGraph (ImmutableDigraph k n e) 
(Graph (Gr k n e), MarksVertices k) => EdgeListGraph (Gr k n e) 

class Graph gr => MutableGraph gr where

The singular variants have default implementations. They are class members so that they can be overridden with more efficient implementations if desired.

Methods

insertEdge :: Vertex -> Vertex -> EdgeLabel gr -> gr -> Maybe gr

Insert an edge into the graph. Edges will be inserted only if both of the endpoints are in the graph. For graphs that do not allow multi-edges, inserting an edge that already exists will overwrite the edge label. For multigraphs, a duplicate edge will be inserted.

insertVertex :: Vertex -> VertexLabel gr -> gr -> gr

Add a vertex to the graph. If the vertex already exists in the graph, its label is overwritten.

removeVertex :: Vertex -> gr -> gr

Delete a node from the graph.

clearVertex :: Vertex -> gr -> gr

Remove all of the incoming and outgoing edges from a node (but leave the node itself in the graph).

removeEdge :: Eq (EdgeLabel gr) => Edge gr -> gr -> gr

Remove the edge referenced by the given descriptor (obtained from insertEdge)

removeEdges :: Vertex -> Vertex -> gr -> gr

Remove all edges with the given endpoints (regardless of label)

Instances

(Graph (Gr k n e), MarksVertices k) => MutableGraph (Gr k n e) 

class MarksVertices k where

Methods

newMarker :: VertexListGraph gr => gr -> ST s (k s)

markVertex :: k s -> Vertex -> ST s ()

isVertexMarked :: k s -> Vertex -> ST s Bool

Instances

Generic mutator

(&) :: MutableGraph gr => Context gr -> gr -> gr

This function is the merge operator from FGL. It has some important invariants that must be obeyed. The vertex whose context is being inserted must not be in the graph. Additionally, the other vertices referred to in the context must exist in the graph.

Graph traversals

ufold

Arguments

:: (VertexListGraph gr, InspectableGraph gr) 
=> (Context gr -> c -> c)

Fold function

-> c

Seed value

-> gr

Graph

-> c 

Fold a function over all of the contexts of the graph

gmap :: (MutableGraph gr2, InspectableGraph gr1, VertexListGraph gr1) => (Context gr1 -> Context gr2) -> gr1 -> gr2

Map a function over a graph. The function can perform arbitrary modifications to each context (which are combined to form a new graph).

nmap :: (EdgeLabel gr1 ~ EdgeLabel gr2, MutableGraph gr2, InspectableGraph gr1, VertexListGraph gr1) => (VertexLabel gr1 -> VertexLabel gr2) -> gr1 -> gr2

Map a function over the node labels of a graph

emap :: (VertexLabel gr1 ~ VertexLabel gr2, MutableGraph gr2, InspectableGraph gr1, VertexListGraph gr1) => (EdgeLabel gr1 -> EdgeLabel gr2) -> gr1 -> gr2

Map a function over the edge labels of a graph

Context inspection

suc' :: Graph gr => Context gr -> [Vertex]

pre' :: BidirectionalGraph gr => Context gr -> [Vertex]

out' :: Graph gr => Context gr -> [Edge gr]

inn' :: BidirectionalGraph gr => Context gr -> [Edge gr]

outdeg' :: Graph gr => Context gr -> Int

indeg' :: BidirectionalGraph gr => Context gr -> Int

neighbors' :: BidirectionalGraph gr => Context gr -> [Vertex]

All nodes linked to or from in the context. This function *may* return duplicates if some node is both a predecessor and a successor.