| Haskell Hierarchical Libraries (fgl package) | Source code | Contents | Index

Data.Graph.Inductive.Graph

Contents

General Type Defintions
  Node and Edge Types
  Types Supporting Inductive Graph View
Graph Type Classes
Operations
  Graph Folds and Maps
  Graph Projection
  Graph Construction and Destruction
  Graph Inspection
  Context Inspection

Description
Static and Dynamic Inductive Graphs
Synopsis

type Node = Int
type LNode a = (Node, a)
type UNode = LNode ()
type Edge = (Node, Node)
type LEdge b = (Node, Node, b)
type UEdge = LEdge ()
type Adj b = [(b, Node)]
type Context a b = (Adj b, Node, a, Adj b)
type MContext a b = Maybe (Context a b)
type Decomp g a b = (MContext a b, g a b)
type GDecomp g a b = (Context a b, g a b)
type UContext = ([Node], Node, [Node])
type UDecomp g = (Maybe UContext, g)
type Path = [Node]
newtype LPath a = LP [LNode a]
type UPath = [UNode]
class Graph gr where

empty :: gr a b
isEmpty :: gr a b -> Bool
match :: Node -> gr a b -> Decomp gr a b
mkGraph :: [LNode a] -> [LEdge b] -> gr a b
labNodes :: gr a b -> [LNode a]
matchAny :: gr a b -> GDecomp gr a b
noNodes :: gr a b -> Int
nodeRange :: gr a b -> (Node, Node)
labEdges :: gr a b -> [LEdge b]

class Graph gr => DynGraph gr where

(&) :: Context a b -> gr a b -> gr a b

ufold :: Graph gr => (Context a b -> c -> c) -> c -> gr a b -> c
gmap :: DynGraph gr => (Context a b -> Context c d) -> gr a b -> gr c d
nmap :: DynGraph gr => (a -> c) -> gr a b -> gr c b
emap :: DynGraph gr => (b -> c) -> gr a b -> gr a c
nodes :: Graph gr => gr a b -> [Node]
edges :: Graph gr => gr a b -> [Edge]
newNodes :: Graph gr => Int -> gr a b -> [Node]
gelem :: Graph gr => Node -> gr a b -> Bool
insNode :: DynGraph gr => LNode a -> gr a b -> gr a b
insEdge :: DynGraph gr => LEdge b -> gr a b -> gr a b
delNode :: Graph gr => Node -> gr a b -> gr a b
delEdge :: DynGraph gr => Edge -> gr a b -> gr a b
delLEdge :: (DynGraph gr, Eq b) => LEdge b -> gr a b -> gr a b
insNodes :: DynGraph gr => [LNode a] -> gr a b -> gr a b
insEdges :: DynGraph gr => [LEdge b] -> gr a b -> gr a b
delNodes :: Graph gr => [Node] -> gr a b -> gr a b
delEdges :: DynGraph gr => [Edge] -> gr a b -> gr a b
buildGr :: DynGraph gr => [Context a b] -> gr a b
mkUGraph :: Graph gr => [Node] -> [Edge] -> gr () ()
context :: Graph gr => gr a b -> Node -> Context a b
lab :: Graph gr => gr a b -> Node -> Maybe a
neighbors :: Graph gr => gr a b -> Node -> [Node]
suc :: Graph gr => gr a b -> Node -> [Node]
pre :: Graph gr => gr a b -> Node -> [Node]
lsuc :: Graph gr => gr a b -> Node -> [(Node, b)]
lpre :: Graph gr => gr a b -> Node -> [(Node, b)]
out :: Graph gr => gr a b -> Node -> [LEdge b]
inn :: Graph gr => gr a b -> Node -> [LEdge b]
outdeg :: Graph gr => gr a b -> Node -> Int
indeg :: Graph gr => gr a b -> Node -> Int
deg :: Graph gr => gr a b -> Node -> Int
equal :: (Eq a, Eq b, Graph gr) => gr a b -> gr a b -> Bool
node' :: Context a b -> Node
lab' :: Context a b -> a
labNode' :: Context a b -> LNode a
neighbors' :: Context a b -> [Node]
suc' :: Context a b -> [Node]
pre' :: Context a b -> [Node]
lpre' :: Context a b -> [(Node, b)]
lsuc' :: Context a b -> [(Node, b)]
out' :: Context a b -> [LEdge b]
inn' :: Context a b -> [LEdge b]
outdeg' :: Context a b -> Int
indeg' :: Context a b -> Int
deg' :: Context a b -> Int

General Type Defintions
Node and Edge Types
type Node = Int
Unlabeled node
type LNode a = (Node, a)
Labeled node
type UNode = LNode ()
Quasi-unlabeled node
type Edge = (Node, Node)
Unlabeled edge
type LEdge b = (Node, Node, b)
Labeled edge
type UEdge = LEdge ()
Quasi-unlabeled edge
Types Supporting Inductive Graph View
type Adj b = [(b, Node)]
Labeled links to or from a `Node`.
type Context a b = (Adj b, Node, a, Adj b)
Links to the `Node`, the `Node` itself, a label, links from the `Node`.
type MContext a b = Maybe (Context a b)
type Decomp g a b = (MContext a b, g a b)
`Graph` decomposition - the context removed from a `Graph`, and the rest of the `Graph`.
type GDecomp g a b = (Context a b, g a b)
The same as `Decomp`, only more sure of itself.
type UContext = ([Node], Node, [Node])
Unlabeled context.
type UDecomp g = (Maybe UContext, g)
Unlabeled decomposition.
type Path = [Node]
Unlabeled path
newtype LPath a

Labeled path
Constructors

LP [LNode a] |

Instances

Eq a => Eq (LPath a)
Ord a => Ord (LPath a)
Show a => Show (LPath a)

type UPath = [UNode]
Quasi-unlabeled path
Graph Type Classes

We define two graph classes:

Graph: static, decomposable graphs. Static means that a graph itself cannot be changed

DynGraph: dynamic, extensible graphs. Dynamic graphs inherit all operations from static graphs but also offer operations to extend and change graphs.

Each class contains in addition to its essential operations those derived operations that might be overwritten by a more efficient implementation in an instance definition.

Note that labNodes is essentially needed because the default definition for matchAny is based on it: we need some node from the graph to define matchAny in terms of match. Alternatively, we could have made matchAny essential and have labNodes defined in terms of ufold and matchAny. However, in general, labNodes seems to be (at least) as easy to define as matchAny. We have chosen labNodes instead of the function nodes since nodes can be easily derived from labNodes, but not vice versa.

class Graph gr where

Minimum implementation: `empty`, `isEmpty`, `match`, `mkGraph`, `labNodes`
Methods

empty :: gr a b
An empty `Graph`.
isEmpty :: gr a b -> Bool
True if the given `Graph` is empty.
match :: Node -> gr a b -> Decomp gr a b
Decompose a `Graph` into the `MContext` found for the given node and the remaining `Graph`.
mkGraph :: [LNode a] -> [LEdge b] -> gr a b
Create a `Graph` from the list of `LNode`s and `LEdge`s.
labNodes :: gr a b -> [LNode a]
A list of all `LNode`s in the `Graph`.
matchAny :: gr a b -> GDecomp gr a b
Decompose a graph into the `Context` for an arbitrarily-chosen `Node` and the remaining `Graph`.
noNodes :: gr a b -> Int
The number of `Node`s in a `Graph`.
nodeRange :: gr a b -> (Node, Node)
The minimum and maximum `Node` in a `Graph`.
labEdges :: gr a b -> [LEdge b]
A list of all `LEdge`s in the `Graph`.

Instances

Graph Gr

class Graph gr => DynGraph gr where

Methods

(&) :: Context a b -> gr a b -> gr a b
Merge the `Context` into the `DynGraph`.

Instances

DynGraph Gr

Operations
Graph Folds and Maps
ufold :: Graph gr => (Context a b -> c -> c) -> c -> gr a b -> c
Fold a function over the graph.
gmap :: DynGraph gr => (Context a b -> Context c d) -> gr a b -> gr c d
Map a function over the graph.
nmap :: DynGraph gr => (a -> c) -> gr a b -> gr c b
Map a function over the `Node` labels in a graph.
emap :: DynGraph gr => (b -> c) -> gr a b -> gr a c
Map a function over the `Edge` labels in a graph.
Graph Projection
nodes :: Graph gr => gr a b -> [Node]
List all `Node`s in the `Graph`.
edges :: Graph gr => gr a b -> [Edge]
List all `Edge`s in the `Graph`.
newNodes :: Graph gr => Int -> gr a b -> [Node]
List N available `Node`s, i.e. `Node`s that are not used in the `Graph`.
gelem :: Graph gr => Node -> gr a b -> Bool
`True` if the `Node` is present in the `Graph`.
Graph Construction and Destruction
insNode :: DynGraph gr => LNode a -> gr a b -> gr a b
Insert a `LNode` into the `Graph`.
insEdge :: DynGraph gr => LEdge b -> gr a b -> gr a b
Insert a `LEdge` into the `Graph`.
delNode :: Graph gr => Node -> gr a b -> gr a b
Remove a `Node` from the `Graph`.
delEdge :: DynGraph gr => Edge -> gr a b -> gr a b
Remove an `Edge` from the `Graph`.
delLEdge :: (DynGraph gr, Eq b) => LEdge b -> gr a b -> gr a b
Remove an `LEdge` from the `Graph`.
insNodes :: DynGraph gr => [LNode a] -> gr a b -> gr a b
Insert multiple `LNode`s into the `Graph`.
insEdges :: DynGraph gr => [LEdge b] -> gr a b -> gr a b
Insert multiple `LEdge`s into the `Graph`.
delNodes :: Graph gr => [Node] -> gr a b -> gr a b
Remove multiple `Node`s from the `Graph`.
delEdges :: DynGraph gr => [Edge] -> gr a b -> gr a b
Remove multiple `Edge`s from the `Graph`.
buildGr :: DynGraph gr => [Context a b] -> gr a b
Build a `Graph` from a list of `Context`s.
mkUGraph :: Graph gr => [Node] -> [Edge] -> gr () ()
Build a quasi-unlabeled `Graph`.
Graph Inspection
context :: Graph gr => gr a b -> Node -> Context a b
Find the context for the given `Node`. Causes an error if the `Node` is not present in the `Graph`.
lab :: Graph gr => gr a b -> Node -> Maybe a
Find the label for a `Node`.
neighbors :: Graph gr => gr a b -> Node -> [Node]
Find the neighbors for a `Node`.
suc :: Graph gr => gr a b -> Node -> [Node]
Find all `Node`s that have a link from the given `Node`.
pre :: Graph gr => gr a b -> Node -> [Node]
Find all `Node`s that link to to the given `Node`.
lsuc :: Graph gr => gr a b -> Node -> [(Node, b)]
Find all `Node`s that are linked from the given `Node` and the label of each link.
lpre :: Graph gr => gr a b -> Node -> [(Node, b)]
Find all `Node`s that link to the given `Node` and the label of each link.
out :: Graph gr => gr a b -> Node -> [LEdge b]
Find all outward-bound `LEdge`s for the given `Node`.
inn :: Graph gr => gr a b -> Node -> [LEdge b]
Find all inward-bound `LEdge`s for the given `Node`.
outdeg :: Graph gr => gr a b -> Node -> Int
The outward-bound degree of the `Node`.
indeg :: Graph gr => gr a b -> Node -> Int
The inward-bound degree of the `Node`.
deg :: Graph gr => gr a b -> Node -> Int
The degree of the `Node`.
equal :: (Eq a, Eq b, Graph gr) => gr a b -> gr a b -> Bool
Context Inspection
node' :: Context a b -> Node
The `Node` in a `Context`.
lab' :: Context a b -> a
The label in a `Context`.
labNode' :: Context a b -> LNode a
The `LNode` from a `Context`.
neighbors' :: Context a b -> [Node]
All `Node`s linked to or from in a `Context`.
suc' :: Context a b -> [Node]
All `Node`s linked to in a `Context`.
pre' :: Context a b -> [Node]
All `Node`s linked from in a `Context`.
lpre' :: Context a b -> [(Node, b)]
All `Node`s linked from in a `Context`, and the label of the links.
lsuc' :: Context a b -> [(Node, b)]
All `Node`s linked from in a `Context`, and the label of the links.
out' :: Context a b -> [LEdge b]
All outward-directed `LEdge`s in a `Context`.
inn' :: Context a b -> [LEdge b]
All inward-directed `LEdge`s in a `Context`.
outdeg' :: Context a b -> Int
The outward degree of a `Context`.
indeg' :: Context a b -> Int
The inward degree of a `Context`.
deg' :: Context a b -> Int
The degree of a `Context`.
Produced by Haddock version 0.8