Module "GraphInductive.curry"

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

Datatypes:
Context | Context' | Decomp | Edge | GDecomp | Graph | LEdge | LNode | LPath | MContext | Node | Path | UContext | UDecomp | UEdge | UGr | UNode | UPath

Functions:
:& | buildGr | context | deg | deg' | delEdge | delEdges | delNode | delNodes | edges | emap | empty | equal | gelem | gmap | indeg | indeg' | inn | inn' | insEdge | insEdges | insNode | insNodes | isEmpty | lab | lab' | labEdges | labNode' | labNodes | labUEdges | labUNodes | lpre | lpre' | lsuc | lsuc' | match | matchAny | mkGraph | mkUGraph | neighbors | neighbors' | newNodes | nmap | node' | nodeRange | nodes | noNodes | out | out' | outdeg | outdeg' | pre | pre' | showGraph | suc | suc' | ufold

(:&)  :: ([(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 'LNode's and 'LEdge's.

buildGr  :: [([(a,Int)],Int,b,[(a,Int)])] -> Graph b a              Build a 'Graph' from a list of 'Context's.

mkUGraph  :: [Int] -> [(Int,Int)] -> Graph () ()              Build a quasi-unlabeled 'Graph' from the list of 'Node's and 'Edge's.

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 'LNode's into the 'Graph'.

insEdges  :: [(Int,Int,a)] -> Graph b a -> Graph b a              Insert multiple 'LEdge's into the 'Graph'.

delNodes  :: [Int] -> Graph a b -> Graph a b              Remove multiple 'Node's from the 'Graph'.

delEdges  :: [(Int,Int)] -> Graph a b -> Graph a b              Remove multiple 'Edge's 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 'Node's 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 'Node's that have a link from the given 'Node'.

pre  :: Graph a b -> Int -> [Int]              Find all 'Node's 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 'Node's that link to the given 'Node' and the label of each link.

out  :: Graph a b -> Int -> [(Int,Int,b)]              Find all outward-bound 'LEdge's for the given 'Node'.

inn  :: Graph a b -> Int -> [(Int,Int,b)]              Find all inward-bound 'LEdge's 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 'Node's linked to or from in a 'Context'.

suc'  :: ([(a,Int)],Int,b,[(a,Int)]) -> [Int]              All 'Node's linked to in a 'Context'.

pre'  :: ([(a,Int)],Int,b,[(a,Int)]) -> [Int]              All 'Node's linked from in a 'Context'.

lpre'  :: ([(a,Int)],Int,b,[(a,Int)]) -> [(Int,a)]              All 'Node's linked from in a 'Context', and the label of the links.

lsuc'  :: ([(a,Int)],Int,b,[(a,Int)]) -> [(Int,a)]              All 'Node's linked from in a 'Context', and the label of the links.

out'  :: ([(a,Int)],Int,b,[(a,Int)]) -> [(Int,Int,a)]              All outward-directed 'LEdge's in a 'Context'.

inn'  :: ([(a,Int)],Int,b,[(a,Int)]) -> [(Int,Int,a)]              All inward-directed 'LEdge's 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 'LNode's in the 'Graph'.

labEdges  :: Graph a b -> [(Int,Int,b)]              A list of all 'LEdge's in the 'Graph'.

nodes  :: Graph a b -> [Int]              List all 'Node's in the 'Graph'.

edges  :: Graph a b -> [(Int,Int)]              List all 'Edge's in the 'Graph'.

newNodes  :: Int -> Graph a b -> [Int]              List N available 'Node's, ie 'Node's 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

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 = (Int,a)

UNode

Quasi-unlabeled node

Type synonym: UNode = (Int,())

Edge

Unlabeled edge

Type synonym: Edge = (Int,Int)

LEdge

Labeled edge

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

UEdge

Quasi-unlabeled edge

Type synonym: UEdge = (Int,Int,())

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 = ([(b,Int)],Int,a,[(b,Int)])

MContext

maybe context

Type synonym: MContext a b = Maybe ([(b,Int)],Int,a,[(b,Int)])

Context'

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

Type synonym: Context' a b = ([(b,Int)],a,[(b,Int)])

UContext

Unlabeled context.

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

GDecomp

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

Type synonym: GDecomp a b = (([(b,Int)],Int,a,[(b,Int)]),Graph a b)

Decomp

a decomposition with a maybe context

Type synonym: Decomp a b = (Maybe ([(b,Int)],Int,a,[(b,Int)]),Graph a b)

UDecomp

Unlabeled decomposition.

Type synonym: UDecomp a = (Maybe ([Int],Int,[Int]),a)

Path

Unlabeled path

Type synonym: Path = [Int]

LPath

Labeled path

Type synonym: LPath a = [(Int,a)]

UPath

Quasi-unlabeled path

Type synonym: UPath = [(Int,())]

UGr

a graph without any labels

Type synonym: UGr = Graph () ()

Graph

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

Constructors:

---

---

Exported functions:

---

(:&) :: ([(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:

• incompletely defined

---

empty :: Graph a b   

An empty 'Graph'.

---

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

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

---

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

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

---

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

Build a quasi-unlabeled 'Graph' from the list of 'Node's and 'Edge's.

---

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'.

Further infos:

• incompletely defined

---

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

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

---

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

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

---

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

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

---

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

Remove multiple 'Edge's 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 'Node's 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'.

Further infos:

• incompletely defined

---

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 'Node's that have a link from the given 'Node'.

---

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

Find all 'Node's 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 'Node's that link to the given 'Node' and the label of each link.

---

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

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

---

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

Find all inward-bound 'LEdge's 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 'Node's linked to or from in a 'Context'.

---

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

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

---

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

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

---

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

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

---

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

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

---

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

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

---

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

All inward-directed 'LEdge's 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 'LNode's in the 'Graph'.

---

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

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

---

nodes :: Graph a b -> [Int]   

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

---

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

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

---

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

List N available 'Node's, ie 'Node's 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

---

---

Generated by CurryDoc (Version 0.4.1 of June 7, 2007) at Jun 16 17:10:09 2009