fgl-5.4.2.4: Martin Erwig's Functional Graph Library

Safe Haskell | None

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 Source

Unlabeled node

type LNode a = (Node, a)Source

Labeled node

type UNode = LNode ()Source

Quasi-unlabeled node

type Edge = (Node, Node)Source

Unlabeled edge

type LEdge b = (Node, Node, b)Source

Labeled edge

type UEdge = LEdge ()Source

Quasi-unlabeled edge

## Types Supporting Inductive Graph View

type Adj b = [(b, Node)]Source

Labeled links to or from a `Node`.

type Context a b = (Adj b, Node, a, Adj b)Source

Links to the `Node`, the `Node` itself, a label, links from the `Node`.

type MContext a b = Maybe (Context a b)Source

type Decomp g a b = (MContext a b, g a b)Source

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

The same as `Decomp`, only more sure of itself.

type UContext = ([Node], Node, [Node])Source

Unlabeled context.

type UDecomp g = (Maybe UContext, g)Source

Unlabeled decomposition.

type Path = [Node]Source

Unlabeled path

newtype LPath a Source

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]Source

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 Source

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

Methods

empty :: gr a bSource

An empty `Graph`.

isEmpty :: gr a b -> Bool Source

True if the given `Graph` is empty.

match :: Node -> gr a b -> Decomp gr a bSource

Decompose a `Graph` into the `MContext` found for the given node and the remaining `Graph`.

mkGraph :: [LNode a] -> [LEdge b] -> gr a bSource

Create a `Graph` from the list of `LNode`s and `LEdge`s.

labNodes :: gr a b -> [LNode a]Source

A list of all `LNode`s in the `Graph`.

matchAny :: gr a b -> GDecomp gr a bSource

Decompose a graph into the `Context` for an arbitrarily-chosen `Node` and the remaining `Graph`.

noNodes :: gr a b -> Int Source

The number of `Node`s in a `Graph`.

nodeRange :: gr a b -> (Node, Node)Source

The minimum and maximum `Node` in a `Graph`.

labEdges :: gr a b -> [LEdge b]Source

A list of all `LEdge`s in the `Graph`.

Instances

Graph Gr |
Graph Gr |

class Graph gr => DynGraph gr where Source

Methods

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

Merge the `Context` into the `DynGraph`.

Instances

DynGraph Gr |
DynGraph Gr |

# Operations

## Graph Folds and Maps

ufold :: Graph gr => (Context a b -> c -> c) -> c -> gr a b -> cSource

Fold a function over the graph.

gmap :: DynGraph gr => (Context a b -> Context c d) -> gr a b -> gr c dSource

Map a function over the graph.

nmap :: DynGraph gr => (a -> c) -> gr a b -> gr c bSource

Map a function over the `Node` labels in a graph.

emap :: DynGraph gr => (b -> c) -> gr a b -> gr a cSource

Map a function over the `Edge` labels in a graph.

## Graph Projection

nodes :: Graph gr => gr a b -> [Node]Source

List all `Node`s in the `Graph`.

edges :: Graph gr => gr a b -> [Edge]Source

List all `Edge`s in the `Graph`.

newNodes :: Graph gr => Int -> gr a b -> [Node]Source

List N available `Node`s, i.e. `Node`s that are not used in the `Graph`.

gelem :: Graph gr => Node -> gr a b -> Bool Source

`True` if the `Node` is present in the `Graph`.

## Graph Construction and Destruction

insNode :: DynGraph gr => LNode a -> gr a b -> gr a bSource

Insert a `LNode` into the `Graph`.

insEdge :: DynGraph gr => LEdge b -> gr a b -> gr a bSource

Insert a `LEdge` into the `Graph`.

delNode :: Graph gr => Node -> gr a b -> gr a bSource

Remove a `Node` from the `Graph`.

delEdge :: DynGraph gr => Edge -> gr a b -> gr a bSource

Remove an `Edge` from the `Graph`.

delLEdge :: (DynGraph gr, Eq b) => LEdge b -> gr a b -> gr a bSource

Remove an `LEdge` from the `Graph`.

insNodes :: DynGraph gr => [LNode a] -> gr a b -> gr a bSource

Insert multiple `LNode`s into the `Graph`.

insEdges :: DynGraph gr => [LEdge b] -> gr a b -> gr a bSource

Insert multiple `LEdge`s into the `Graph`.

delNodes :: Graph gr => [Node] -> gr a b -> gr a bSource

Remove multiple `Node`s from the `Graph`.

delEdges :: DynGraph gr => [Edge] -> gr a b -> gr a bSource

Remove multiple `Edge`s from the `Graph`.

buildGr :: DynGraph gr => [Context a b] -> gr a bSource

Build a `Graph` from a list of `Context`s.

mkUGraph :: Graph gr => [Node] -> [Edge] -> gr () ()Source

Build a quasi-unlabeled `Graph`.

## Graph Inspection

context :: Graph gr => gr a b -> Node -> Context a bSource

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 aSource

Find the label for a `Node`.

neighbors :: Graph gr => gr a b -> Node -> [Node]Source

Find the neighbors for a `Node`.

suc :: Graph gr => gr a b -> Node -> [Node]Source

Find all `Node`s that have a link from the given `Node`.

pre :: Graph gr => gr a b -> Node -> [Node]Source

Find all `Node`s that link to to the given `Node`.

lsuc :: Graph gr => gr a b -> Node -> [(Node, b)]Source

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

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]Source

Find all outward-bound `LEdge`s for the given `Node`.

inn :: Graph gr => gr a b -> Node -> [LEdge b]Source

Find all inward-bound `LEdge`s for the given `Node`.

outdeg :: Graph gr => gr a b -> Node -> Int Source

The outward-bound degree of the `Node`.

indeg :: Graph gr => gr a b -> Node -> Int Source

The inward-bound degree of the `Node`.

deg :: Graph gr => gr a b -> Node -> Int Source

The degree of the `Node`.

equal :: (Eq a, Eq b, Graph gr) => gr a b -> gr a b -> Bool Source

## Context Inspection

node' :: Context a b -> Node Source

The `Node` in a `Context`.

lab' :: Context a b -> aSource

The label in a `Context`.

labNode' :: Context a b -> LNode aSource

The `LNode` from a `Context`.

neighbors' :: Context a b -> [Node]Source

All `Node`s linked to or from in a `Context`.

suc' :: Context a b -> [Node]Source

All `Node`s linked to in a `Context`.

pre' :: Context a b -> [Node]Source

All `Node`s linked from in a `Context`.

lpre' :: Context a b -> [(Node, b)]Source

All `Node`s linked from in a `Context`, and the label of the links.

lsuc' :: Context a b -> [(Node, b)]Source

All `Node`s linked from in a `Context`, and the label of the links.

out' :: Context a b -> [LEdge b]Source

All outward-directed `LEdge`s in a `Context`.

inn' :: Context a b -> [LEdge b]Source

All inward-directed `LEdge`s in a `Context`.

outdeg' :: Context a b -> Int Source

The outward degree of a `Context`.

indeg' :: Context a b -> Int Source

The inward degree of a `Context`.

deg' :: Context a b -> Int Source

The degree of a `Context`.