PAKCS
Exported names: Imported modules:

Module GraphInductive

Library for inductive graphs (port of a Haskell library by Martin Erwig).

In this library, graphs are composed and decomposed in an inductive way.

The key idea is as follows:

A graph is either empty or it consists of node context and a graph g' which are put together by a constructor (:&).

This constructor (:&), however, is not a constructor in the sense of abstract data type, but more basically a defined constructing funtion.

A context is a node together withe the edges to and from this node into the nodes in the graph g'.

For examples of how to use this library, cf. the module GraphAlgorithms.

Author: Bernd Brassel

Version: May 2005

Summary of exported operations:

(:&) :: ([(a,Int)],Int,b,[(a,Int)]) -> Graph b a -> Graph b a   
(:&) takes a node-context and a Graph and yields a new graph.
matchAny :: Graph a b -> (([(b,Int)],Int,a,[(b,Int)]),Graph a b)   
decompose a graph into the Context for an arbitrarily-chosen Node and the remaining Graph.
empty :: Graph a b   
An empty Graph.
mkGraph :: [(Int,a)] -> [(Int,Int,b)] -> Graph a b   
Create a Graph from the list of LNodes and LEdges.
buildGr :: [([(a,Int)],Int,b,[(a,Int)])] -> Graph b a   
Build a Graph from a list of Contexts.
mkUGraph :: [Int] -> [(Int,Int)] -> Graph () ()   
Build a quasi-unlabeled Graph from the list of Nodes and Edges.
insNode :: (Int,a) -> Graph a b -> Graph a b   
Insert a LNode into the Graph.
insEdge :: (Int,Int,a) -> Graph b a -> Graph b a   
Insert a LEdge into the Graph.
delNode :: Int -> Graph a b -> Graph a b   
Remove a Node from the Graph.
delEdge :: (Int,Int) -> Graph a b -> Graph a b   
Remove an Edge from the Graph.
insNodes :: [(Int,a)] -> Graph a b -> Graph a b   
Insert multiple LNodes into the Graph.
insEdges :: [(Int,Int,a)] -> Graph b a -> Graph b a   
Insert multiple LEdges into the Graph.
delNodes :: [Int] -> Graph a b -> Graph a b   
Remove multiple Nodes from the Graph.
delEdges :: [(Int,Int)] -> Graph a b -> Graph a b   
Remove multiple Edges from the Graph.
isEmpty :: Graph a b -> Bool   
test if the given Graph is empty.
match :: Int -> Graph a b -> (Maybe ([(b,Int)],Int,a,[(b,Int)]),Graph a b)   
match is the complement side of (:&), decomposing a Graph into the MContext found for the given node and the remaining Graph.
noNodes :: Graph a b -> Int   
The number of Nodes in a Graph.
nodeRange :: Graph a b -> (Int,Int)   
The minimum and maximum Node in a Graph.
context :: Graph a b -> Int -> ([(b,Int)],Int,a,[(b,Int)])   
Find the context for the given Node.
lab :: Graph a b -> Int -> Maybe a   
Find the label for a Node.
neighbors :: Graph a b -> Int -> [Int]   
Find the neighbors for a Node.
suc :: Graph a b -> Int -> [Int]   
Find all Nodes that have a link from the given Node.
pre :: Graph a b -> Int -> [Int]   
Find all Nodes that link to to the given Node.
lsuc :: Graph a b -> Int -> [(Int,b)]   
Find all Nodes and their labels, which are linked from the given Node.
lpre :: Graph a b -> Int -> [(Int,b)]   
Find all Nodes that link to the given Node and the label of each link.
out :: Graph a b -> Int -> [(Int,Int,b)]   
Find all outward-bound LEdges for the given Node.
inn :: Graph a b -> Int -> [(Int,Int,b)]   
Find all inward-bound LEdges for the given Node.
outdeg :: Graph a b -> Int -> Int   
The outward-bound degree of the Node.
indeg :: Graph a b -> Int -> Int   
The inward-bound degree of the Node.
deg :: Graph a b -> Int -> Int   
The degree of the Node.
gelem :: Int -> Graph a b -> Bool   
True if the Node is present in the Graph.
equal :: Graph a b -> Graph a b -> Bool   
graph equality
node' :: ([(a,Int)],Int,b,[(a,Int)]) -> Int   
The Node in a Context.
lab' :: ([(a,Int)],Int,b,[(a,Int)]) -> b   
The label in a Context.
labNode' :: ([(a,Int)],Int,b,[(a,Int)]) -> (Int,b)   
The LNode from a Context.
neighbors' :: ([(a,Int)],Int,b,[(a,Int)]) -> [Int]   
All Nodes linked to or from in a Context.
suc' :: ([(a,Int)],Int,b,[(a,Int)]) -> [Int]   
All Nodes linked to in a Context.
pre' :: ([(a,Int)],Int,b,[(a,Int)]) -> [Int]   
All Nodes linked from in a Context.
lpre' :: ([(a,Int)],Int,b,[(a,Int)]) -> [(Int,a)]   
All Nodes linked from in a Context, and the label of the links.
lsuc' :: ([(a,Int)],Int,b,[(a,Int)]) -> [(Int,a)]   
All Nodes linked from in a Context, and the label of the links.
out' :: ([(a,Int)],Int,b,[(a,Int)]) -> [(Int,Int,a)]   
All outward-directed LEdges in a Context.
inn' :: ([(a,Int)],Int,b,[(a,Int)]) -> [(Int,Int,a)]   
All inward-directed LEdges in a Context.
outdeg' :: ([(a,Int)],Int,b,[(a,Int)]) -> Int   
The outward degree of a Context.
indeg' :: ([(a,Int)],Int,b,[(a,Int)]) -> Int   
The inward degree of a Context.
deg' :: ([(a,Int)],Int,b,[(a,Int)]) -> Int   
The degree of a Context.
labNodes :: Graph a b -> [(Int,a)]   
A list of all LNodes in the Graph.
labEdges :: Graph a b -> [(Int,Int,b)]   
A list of all LEdges in the Graph.
nodes :: Graph a b -> [Int]   
List all Nodes in the Graph.
edges :: Graph a b -> [(Int,Int)]   
List all Edges in the Graph.
newNodes :: Int -> Graph a b -> [Int]   
List N available Nodes, ie Nodes that are not used in the Graph.
ufold :: (([(a,Int)],Int,b,[(a,Int)]) -> c -> c) -> c -> Graph b a -> c   
Fold a function over the graph.
gmap :: (([(a,Int)],Int,b,[(a,Int)]) -> ([(c,Int)],Int,d,[(c,Int)])) -> Graph b a -> Graph d c   
Map a function over the graph.
nmap :: (a -> b) -> Graph a c -> Graph b c   
Map a function over the Node labels in a graph.
emap :: (a -> b) -> Graph c a -> Graph c b   
Map a function over the Edge labels in a graph.
labUEdges :: [(a,b)] -> [(a,b,())]   
add label () to list of edges (node,node)
labUNodes :: [a] -> [(a,())]   
add label () to list of nodes
showGraph :: Graph a b -> String   
Represent Graph as String

Exported datatypes:

Graph

The type variables of Graph are nodeLabel and edgeLabel. The internal representation of Graph is hidden.

Constructors:

Node

Nodes and edges themselves (in contrast to their labels) are coded as integers.

For both of them, there are variants as labeled, unlabelwd and quasi unlabeled (labeled with ()).

Unlabeled node

Type synonym: Node = Int

LNode

Labeled node

Type synonym: LNode a = (Node,a)

UNode

Quasi-unlabeled node

Type synonym: UNode = LNode ()

Edge

Unlabeled edge

Type synonym: Edge = (Node,Node)

LEdge

Labeled edge

Type synonym: LEdge a = (Node,Node,a)

UEdge

Quasi-unlabeled edge

Type synonym: UEdge = LEdge ()

Context

The context of a node is the node itself (along with label) and its adjacent nodes. Thus, a context is a quadrupel, for node n it is of the form (edges to n,node n,n's label,edges from n)

Type synonym: Context a b = (Adj b,Node,a,Adj b)

MContext

maybe context

Type synonym: MContext a b = Maybe (Context a b)

Context'

context with edges and node label only, without the node identifier itself

Type synonym: Context' a b = (Adj b,a,Adj b)

UContext

Unlabeled context.

Type synonym: UContext = ([Node],Node,[Node])

GDecomp

A graph decompostion is a context for a node n and the remaining graph without that node.

Type synonym: GDecomp a b = (Context a b,Graph a b)

Decomp

a decomposition with a maybe context

Type synonym: Decomp a b = (MContext a b,Graph a b)

UDecomp

Unlabeled decomposition.

Type synonym: UDecomp a = (Maybe UContext,a)

Path

Unlabeled path

Type synonym: Path = [Node]

LPath

Labeled path

Type synonym: LPath a = [LNode a]

UPath

Quasi-unlabeled path

Type synonym: UPath = [UNode]

UGr

a graph without any labels

Type synonym: UGr = Graph () ()

Exported operations:

(:&) :: ([(a,Int)],Int,b,[(a,Int)]) -> Graph b a -> Graph b a   

(:&) takes a node-context and a Graph and yields a new graph.

The according key idea is detailed at the beginning.

nl is the type of the node labels and el the edge labels.

Note that it is an error to induce a context for a node already contained in the graph.

Further infos:
  • defined as right-associative infix operator with precedence 5

matchAny :: Graph a b -> (([(b,Int)],Int,a,[(b,Int)]),Graph a b)   

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

In order to use graphs as abstract data structures, we also need means to decompose a graph. This decompostion should work as much like pattern matching as possible. The normal matching is done by the function matchAny, which takes a graph and yields a graph decompostion.

According to the main idea, matchAny . (:&) should be an identity.

Further infos:
  • partially defined

empty :: Graph a b   

An empty Graph.

mkGraph :: [(Int,a)] -> [(Int,Int,b)] -> Graph a b   

Create a Graph from the list of LNodes and LEdges.

buildGr :: [([(a,Int)],Int,b,[(a,Int)])] -> Graph b a   

Build a Graph from a list of Contexts.

mkUGraph :: [Int] -> [(Int,Int)] -> Graph () ()   

Build a quasi-unlabeled Graph from the list of Nodes and Edges.

insNode :: (Int,a) -> Graph a b -> Graph a b   

Insert a LNode into the Graph.

insEdge :: (Int,Int,a) -> Graph b a -> Graph b a   

Insert a LEdge into the Graph.

delNode :: Int -> Graph a b -> Graph a b   

Remove a Node from the Graph.

delEdge :: (Int,Int) -> Graph a b -> Graph a b   

Remove an Edge from the Graph.

insNodes :: [(Int,a)] -> Graph a b -> Graph a b   

Insert multiple LNodes into the Graph.

insEdges :: [(Int,Int,a)] -> Graph b a -> Graph b a   

Insert multiple LEdges into the Graph.

delNodes :: [Int] -> Graph a b -> Graph a b   

Remove multiple Nodes from the Graph.

delEdges :: [(Int,Int)] -> Graph a b -> Graph a b   

Remove multiple Edges from the Graph.

isEmpty :: Graph a b -> Bool   

test if the given Graph is empty.

match :: Int -> Graph a b -> (Maybe ([(b,Int)],Int,a,[(b,Int)]),Graph a b)   

match is the complement side of (:&), decomposing a Graph into the MContext found for the given node and the remaining Graph.

noNodes :: Graph a b -> Int   

The number of Nodes in a Graph.

Further infos:
  • solution complete, i.e., able to compute all solutions

nodeRange :: Graph a b -> (Int,Int)   

The minimum and maximum Node in a Graph.

context :: Graph a b -> Int -> ([(b,Int)],Int,a,[(b,Int)])   

Find the context for the given Node. In contrast to "match", "context" causes an error if the Node is not present in the Graph.

lab :: Graph a b -> Int -> Maybe a   

Find the label for a Node.

neighbors :: Graph a b -> Int -> [Int]   

Find the neighbors for a Node.

suc :: Graph a b -> Int -> [Int]   

Find all Nodes that have a link from the given Node.

pre :: Graph a b -> Int -> [Int]   

Find all Nodes that link to to the given Node.

lsuc :: Graph a b -> Int -> [(Int,b)]   

Find all Nodes and their labels, which are linked from the given Node.

lpre :: Graph a b -> Int -> [(Int,b)]   

Find all Nodes that link to the given Node and the label of each link.

out :: Graph a b -> Int -> [(Int,Int,b)]   

Find all outward-bound LEdges for the given Node.

inn :: Graph a b -> Int -> [(Int,Int,b)]   

Find all inward-bound LEdges for the given Node.

outdeg :: Graph a b -> Int -> Int   

The outward-bound degree of the Node.

indeg :: Graph a b -> Int -> Int   

The inward-bound degree of the Node.

deg :: Graph a b -> Int -> Int   

The degree of the Node.

gelem :: Int -> Graph a b -> Bool   

True if the Node is present in the Graph.

equal :: Graph a b -> Graph a b -> Bool   

graph equality

node' :: ([(a,Int)],Int,b,[(a,Int)]) -> Int   

The Node in a Context.

Further infos:
  • solution complete, i.e., able to compute all solutions

lab' :: ([(a,Int)],Int,b,[(a,Int)]) -> b   

The label in a Context.

Further infos:
  • solution complete, i.e., able to compute all solutions

labNode' :: ([(a,Int)],Int,b,[(a,Int)]) -> (Int,b)   

The LNode from a Context.

Further infos:
  • solution complete, i.e., able to compute all solutions

neighbors' :: ([(a,Int)],Int,b,[(a,Int)]) -> [Int]   

All Nodes linked to or from in a Context.

suc' :: ([(a,Int)],Int,b,[(a,Int)]) -> [Int]   

All Nodes linked to in a Context.

pre' :: ([(a,Int)],Int,b,[(a,Int)]) -> [Int]   

All Nodes linked from in a Context.

lpre' :: ([(a,Int)],Int,b,[(a,Int)]) -> [(Int,a)]   

All Nodes linked from in a Context, and the label of the links.

lsuc' :: ([(a,Int)],Int,b,[(a,Int)]) -> [(Int,a)]   

All Nodes linked from in a Context, and the label of the links.

out' :: ([(a,Int)],Int,b,[(a,Int)]) -> [(Int,Int,a)]   

All outward-directed LEdges in a Context.

inn' :: ([(a,Int)],Int,b,[(a,Int)]) -> [(Int,Int,a)]   

All inward-directed LEdges in a Context.

outdeg' :: ([(a,Int)],Int,b,[(a,Int)]) -> Int   

The outward degree of a Context.

indeg' :: ([(a,Int)],Int,b,[(a,Int)]) -> Int   

The inward degree of a Context.

deg' :: ([(a,Int)],Int,b,[(a,Int)]) -> Int   

The degree of a Context.

labNodes :: Graph a b -> [(Int,a)]   

A list of all LNodes in the Graph.

labEdges :: Graph a b -> [(Int,Int,b)]   

A list of all LEdges in the Graph.

nodes :: Graph a b -> [Int]   

List all Nodes in the Graph.

edges :: Graph a b -> [(Int,Int)]   

List all Edges in the Graph.

newNodes :: Int -> Graph a b -> [Int]   

List N available Nodes, ie Nodes that are not used in the Graph.

ufold :: (([(a,Int)],Int,b,[(a,Int)]) -> c -> c) -> c -> Graph b a -> c   

Fold a function over the graph.

gmap :: (([(a,Int)],Int,b,[(a,Int)]) -> ([(c,Int)],Int,d,[(c,Int)])) -> Graph b a -> Graph d c   

Map a function over the graph.

nmap :: (a -> b) -> Graph a c -> Graph b c   

Map a function over the Node labels in a graph.

emap :: (a -> b) -> Graph c a -> Graph c b   

Map a function over the Edge labels in a graph.

labUEdges :: [(a,b)] -> [(a,b,())]   

add label () to list of edges (node,node)

labUNodes :: [a] -> [(a,())]   

add label () to list of nodes

showGraph :: Graph a b -> String   

Represent Graph as String