Graphs are implemented using doubly linked lists over the nodes and the ingoing and outgoing edges of nodes. This provides constant time adding, removing, hiding and restoring of nodes and edges. Apart from that a graph instance can be efficiently viewed as both, directed and undirected. In the directed version you always consider only outgoing edges of a node. In the undirected version you consider ingoing and outgoing edges, incident edges for short. Similary you can view a graph instance simultanously as its transpose simply by considering the inedges of nodes instead of their outedges.
The package comes with a nice user interface that is similar to the interface of LEDA graphs.
Until now the following graph algorithms are available:
The Oz library style is the same style as used in the Oz base
environment. The idea is that the functions for all instances of a
certain data structure are provided by a comon module. For example,
the functionalities for all dictionaries are collected in the module
Dictionary
. If we want to apply such a function to a
concrete dictionary like EnglishToGerman
then we have to
access that function from the module and pass the concrete dictionary
as an argument. For instance:
{Dictionary.get EnglishToGerman hi}
In the objectasrecord style, each instance is modelled as a record
of functions. In other words, each instance of a data structure
carries its own functions. The above example becomes:
{EnglishToGerman.get hi}
This package provides graphs in the objectasrecord style at the URI xozlib://smiele/graph/graph.ozf. Procedures implementing graph algorithms always show up as features in the instace's record. Node arrays and edge arrays returns by graphs in objectasrecord style are also in ojectasrecord style. So if you prefer to use the objectasrecord style, you will only need this single functor.
Versions in the Ozlibrary style are available at the URIs xozlib://smiele/graph/lib/graph.ozf, xozlib://smiele/graph/lib/nodearray.ozf and xozlib://smiele/graph/lib/edgearray.ozf.
We first show how to use a graph in objectasrecord style. Here,
the graph G
is a record of functions
newNode
, newEdge
, indeg
, ... .
local
[Graph] = {Link ['xozlib://smiele/graph/graph.ozf']}
[Dict] = {Link ['xozlib://base/dictionary.ozf']}
G = {Graph.new}
LitToNode = {Dict.new}
in
{ForAll [n1 n2 n3 n4 n5]
proc{$ X}
%% create a new node in G with the label X and store
%% a mapping from X to the node in LitToNode
{LitToNode.put X {G.newNode X}}
end}
%% add edges so that we get the smallest graph that is
%% 2edge connected but not 2node/bi connected
{ForAll [n1#n2 n2#n3 n3#n1 n3#n4 n4#n5 n5#n3]
proc{$ E}
{G.newEdge {LitToNode.get E.1} {LitToNode.get E.2} unit _}
end}
%% inspect the labels of the cut nodes in G (i.e. [n3])
{Inspect {Map {G.bccs}.cutNodes G.nodeLabel}}
%% inspect the number of the bridges in G (i.e. 0)
{Inspect {Length {G.beccs}.bridges}}
end
Note: the functor xozlib://base/dictionary.ozf provides
objectasrecord style dictionaries and is provided by the mogul:/niehre/base package.
Here is how to do the same using the in the Ozlibrary style
functors. Now a graph G
is the first argument expected
by the functions in the functor lib/graph.ozf:
local
[Graph] = {Link ['xozlib://smiele/graph/lib/graph.ozf']}
[Dict] = {Link ['xozlib://base/dictionary.ozf']}
G = {Graph.new}
LitToNode = {Dict.new}
in
{ForAll [n1 n2 n3 n4 n5]
proc{$ X}
%% create a new node in G with the label X and store
%% a mapping from X to the node in LitToNode
{LitToNode.put X {Graph.newNode G X}}
end}
%% add edges so that we get the smallest graph that is
%% 2edge connected but not 2node connected
{ForAll [n1#n2 n2#n3 n3#n1 n3#n4 n4#n5 n5#n3]
proc{$ E}
{Graph.newEdge G {LitToNode.get E.1} {LitToNode.get E.2} unit _}
end}
%% inspect the labels of the cut nodes in G (i.e. [n3])
{Inspect {Map {Graph.bccs G}.cutNodes
fun{$ N} {Graph.nodeLabel G N} end}}
%% inspect the number of the bridges in G (i.e. 0)
{Inspect {Length {Graph.beccs G}.bridges}}
end
G , G1 , ...  for graphs (in object as record style) 
N , N1 , ...  for nodes 
E , E1 , ...  for edges 
NA , NA1 , ...  for node arrays (in objectasrecord style) 
EA , EA1 , ...  for edge arrays (in objectasrecord style) 
NM , NM1 , ...  for node matrices (in objectasrecord style) 
EM , EM1 , ...  for edge matrices (in objectasrecord style) 
I , I1 , ...  for integers 
B , B1 , ...  for boolean values 
R , R1 , ...  for records 
X , X1 , ...  for arbitrary values 
For lists over elements of a certain type we will simply append an
s
to the characteristic variable name of the element
type. For example we will write Es
for a list of edges.
Many procedures have preconditions. These preconditions are checked preconditions, i.e. if a call to a procedure does not satisfy a precondition then an exception is raised.
The structure of the manual is as follows:
We will use the objectasrecord style variants for explanation because procedure types are smaller and therefore more concise. At end of each section the use the corresponding Ozlibrary style procedures is explained briefly.G
basically consists of a set Ns
of
nodes and a set Es
of edges. An edge E
basically consists of a source node N1
and a
target node N2
, where N1
and
N2
must be members of Ns
. Every node and
every edge also has a label. Different graphs G1
and G2
have disjoint sets of nodes and edges. So every
node and every edge has exactly one graph it belongs to.
An edge with source N1
and target N2
is an
outgoing edge of N1
and an ingoing edge of
N2
. An edge E
is incident to a node
N
iff N
is E
's source or
target.
A node or edge can be either visible, hidden or deleted. We say that
a node N
is
G
iff it belongs to
G
and is visible,G
iff it belongs to
G
and is hidden,G
iff it belongs to
G
and is visible or hiddenNodes and edges of a graph have unique representations in Oz.
Using ==
you can test two nodes or edges for token
equality. Two nodes/edges are token equal iff they belong to the same
graph and are the same node/edge in that graph.
Graph
be the module linked from xozlib://smiele/graph/graph.ozf.
G  =  {Graph.new} 
creates a new and empty graph instance G 
G1  =  {G.clone} 
creates a clone G1 of G 
In Ozlibrary style you have to link the functor xozlib://smiele/graph/lib/graph.ozf under some
varible GraphLib
. Then you can use G =
{GraphLib.new}
to create a new and empty graph in Ozlibrary
style and G1 = {GraphLib.clone G}
to create a clone of
G
in G1
.
N  =

{G.newNode X}

adds a new node N to G and sets its
label to X



{G.delNode N}

removes the node N from G Precondition: N is valid in G



{G.hideNode N}

hides the node N and all visible edges incident to
N Precondition: N is visible in G



{G.restoreNode N}

restores a hidden node N , e.g. makes it visible; note
that this operation does not restore the edges that have been hidden
by {G.hideNode N} Precondition: N is hidden in G



{G.setNodeLabel N X}

sets the label of node N to X Precondition: N is valid in G

E  =

{G.newEdge N1 N2 X}

adds a new edge E with source N1 and
target N2 to G and sets its label to
X



{G.delEdge E}

removes the edge E from G Precondition: E is valid in G



{G.hideEdge E}

hides the edge E Precondition: E is visible in G



{G.restoreEdge E}

restores a hidden edge E , e.g. makes it visiblePrecondition: E is hidden in G



{G.setEdgeLabel E X}

sets the label of edge E to X Precondition: E is valid in G

Ns  =

{G.nodes}

returns a list of all visible nodes in G

I  =

{G.nodeCount}

returns the number of all visible edges in G

X  =

{G.nodeLabel N}

returns the label of the node N Precondition: N is valid in G

Es  =

{G.inEdges N}

returns a list of all ingoing edges of N Precondition: N is visible in G

Es  =

{G.outEdges N}

returns a list of all outgoing edges of N Precondition: N is visible in G

Es  =

{G.incEdges N}

returns the list of all edges incident to N Precondition: N is visible in G

I  =

{G.indeg N}

returns the number of all ingoing edges of N Precondition: N is visible in G

I  =

{G.outdeg N}

returns the number of all outgoing edges of N Precondition: N is visible in G

I  =

{G.degree N}

returns the number of all edges incident to N Precondition: N is visible in G

B  =

{G.isVisibleNode N}

tests whether N is visible in G Precondition: N is valid in G

B  =

{G.isHiddenNode N}

tests whether N is hidden in G Precondition: N is valid in G

B  =

{G.isValidNode N}

tests whether N is valid in G ,
e.g. whether it belongs to G and is not deleted.

Es  =

{G.edges}

returns a list of all edges in G

I  =

{G.edgeCount}

returns the number of all edges in G

N  =

{G.source E}

returns the source node N of E ,
i.e. the node for which E is an outgoing edgePrecondition: E is valid in G

N  =

{G.target E}

returns the target node of E , i.e. the node
for which E is an ingoing edgePrecondition: E is valid in G

N1  =

{G.opposite N E}

returns the target of E if N is the
source of E ; otherwise E 's source is
returnedPrecondition: E is valid in G

B  =

{G.edgeLabel E}

returns the label of E Precondition: E is valid in G

B  =


tests whether E is visible in G Precondition: E is valid in G

B  =

{G.isHiddenEdge E}

tests whether E is hidden in G Precondition: E is valid in G

I  =

{G.isValidEdge E}

tests whether E is valid in G ,
e.g. whether it belongs to G and is not deleted.

Procedures for hidden nodes and edges:
Ns  =

{G.hiddenNodes}

returns a list of all hidden nodes in G

I  =

{G.hiddenNodeCount}

returns the number of all hidden nodes in G

Es  =

{G.hiddenEdges}

returns a list of all hidden edges in G

I  =

{G.hiddenEdgeCount}

returns the number of all hidden edges in G

Es  =

{G.hiddenInEdges N}

returns a list of all ingoing edges of N that are
hiddenPrecondition: N is valid in G

Es  =

{G.hiddenOutEdges N}

returns a list of all outgoing edges of N that are
hiddenPrecondition: N is valid in G

Es  =

{G.hiddenIncEdges N}

returns a list of all hidden edges that are incident to N Precondition: N is valid in G

I  =

{G.hiddenIndeg N}

returns the number of all hidden ingoing edges of N Precondition: N is valid in G

I  =

{G.hiddenOutdeg N}

returns the number of all hidden outgoing edges of N Precondition: N is valid in G

I  =

{G.hiddenDegree N}

returns the number of all hidden edges incident to N Precondition: N is valid in G

In order to apply any of the the above procedures to a graph
G
in Ozlibrary style, for example outEdges
of a node N
, use {GraphLib.outEdges G N}
(where GraphLib
is the module obtained by linking the
functor xozlib://smiele/graph/lib/graph.ozf).
In objectasrecord style you can create a new node array
NA
that maps each node of a graph G
to some
initial value InitX
with NA = {G.newNodeArray
InitX}
. In Ozlibrary style you use {NALib.new G
InitX}
(where NALib
is the module obtained by
linking xozlib://smiele/graph/lib/nodearray.ozf).
Node arrays are dynamic. This means that you can
NA
that maps the nodes of a graph
G
to some intial value InitX
N1
, ... to the graph.
After that the node array automatically maps the new nodes
N1
, ..., too. E.g. the underlying vector becomes resized
to fit the new demands. But you cannot be sure to which values the
new nodes are mapped. It could be the initial value
InitX
or the value of some node that has been deleted
previously. This is because the graph data structure internally uses
a numbering of nodes and edges. Numbers of deleted nodes or edges are
reused when new nodes or edges are added to the graph. Node arrays
simply use these numbers and nothing else. So they cannot distinguish
between a node that has been deleted and a new node that got the
number of the deleted node.
The following procedures are available for node arrays:
NA1  =

{NA.clone}

returns a clone of NA in NA1 .



{NA.put N X}

sets the value of NA under the node N
to X

X  =

{NA.get N}

returns the value of NA under the node
N



{NA.collect N X}

is semantically equal to {NA.put N X{NA.get N}}



{NA.inc N}

is semantically equal to {NA.put N 1+{NA.get N}} Precondition: {NA.get N} is an integer

In order to apply any of the above procedures to a node array
NA
in Ozlibrary style, for example inc
for
some node N
, call {NALib.inc NA N}
(where
NALib
is the module obtained by linking xozlib://smiele/graph/lib/nodearray.ozf).
G
in objectasrecord style
and an initial value InitX
you can create a new edge
array EA
with EA = {G.newEdgeArray InitX}
.
Given a graph G
in Ozlibrary style you get a new edge
array EA
in Ozlibrary style with EA = {EALib.new G
InitX}
(where EALib
is the module obtained by
linking xozlib://smiele/graph/lib/edgearray.ozf).
In objectasrecord style you can create a new node matrix
NM
that maps each pair of nodes of a graph G
to some initial value InitX
with NM =
{G.newNodeMatrix InitX}
. In Ozlibrary style you use
{NMLib.new G InitX}
(where NMLib
is the
module obtained by linking xozlib://smiele/graph/lib/nodematrix.ozf).
Node matrices, like node arrays, are dynamic, but a similar restriction concerning the initial value applies. When you create a new node matrix from a graph and then add a new node you cannot rely on the node matrix to contain the initial value at node pairs that contain the new node. Instead the node matrix may contain the value of some previously deleted node.
The following procedures are available for node matrices:
NM1  =

{NM.clone}

returns a clone of NM in NM1 .



{NM.put N1 N2 X}

sets the value of NM under (N1,N2)
to X

X  =

{NM.get N1 N2}

returns the value of NM under (N1,N2)



{NM.collect N1 N2 X}

is semantically equal to {NM.put N1 N2 X{NM.get N1 N2}}



{NM.inc N1 N2}

is semantically equal to {NM.put N1 N2 1+{NM.get N1 N2}} Precondition: {NM.get N1 N2} is an integer

In order to apply any of the above procedures to a node matrix
NM
in Ozlibrary style, for example inc
for
some pair of nodes (N1,N2)
, call {NMLib.inc NM N1
N2}
(where NMLib
is the module obtained by linking
xozlib://smiele/graph/lib/nodematrix.ozf).
G
in objectasrecord style
and an initial value InitX
you can create a new edge
matrix EM
with EM = {G.newEdgeMatrix InitX}
.
Given a graph G
in Ozlibrary style you get a new edge
matrix EM
in Ozlibrary style with EM = {EMLib.new
G InitX}
(where EMLib
is the module obtained by
linking xozlib://smiele/graph/lib/edgematrix.ozf).
G
is a
function Ord : {G.nodes} > [1..{G.nodeCount}]
so that
for every edge with source N1
and target N2
{Ord N1}<{Ord N2}
holds.
This package provides two functions for topological sorting.
Ord = {G.topologicalSort}
returns a function as described
above or the atom 'cyclic'
if G
is cyclic.
B = {G.makeTopologicallySorted}
returns a boolean
value indicating whether G
is cyclic. As a side effect
G
's nodes and each node's outedges are sorted
topologically. This means that afterwards the list Ns =
{G.nodes}
is sortet and for every node N
of
G
the list {G.outEdges N}
is sorted based on
the targets of the edges.
The running time of both functions on a graph G
with
nodes Ns
and edges Es
is in
O(Ns+Es)
..
G
is a
maximal subgraph of G
that is weakly/strongly connected.
The weakly/strongly connected components of a graph G
provide a proper partition of G
's nodes.
This package's implementation of weakly/strongly connected
components computes the number I
of components and a
function that maps each node to the number of its component. The
components are numbered from 1
to I
. The
value returned is a record of the follwing type:
unit(count : int
num : node > int)
The item under count
is the total number of components
I
and the item under num
is the function
that returns the component number of a given node.
For a graph G
in objectasrecord style you can
compute the weakly/strongly connected components R
with
R = {G.wccs}
or R = {G.sccs}
. In
Ozlibrary style use R = {GraphLib.wccs G}
or R =
{GraphLib.wccs G}
.
The running times of the algorithms on a graph G
with
nodes Ns
and edges Es
are in
O(Ns+Es)
.
G
is a maximal subgraph of G
that is
biconnected. Biconnected components of a graph G
with no
selfloop edges (edges that have equal source and target) provide a
proper partition of G
's edges.
A cut node of G
is a node that, iff removed, separates
a weakly connected subgraph of G
in at least two disjoint
weakly connected subgraphs.
This packages's implementation of biconnected componets computes
the number I
of biconnected components and numbers the
components from 1
to I
. Apart from that a
list of all cut nodes is computed. The value returned is a record of
the following type:
unit(count : int
num : edge > int
cutNodes : node list)
The item under count
is the number I
of
components. The item under num
is a function that, given
a nonselfloop edge, returns the number of the component the edge
belongs to. If the function is feeded with a selfloop edge then it
returns 0
(which is not in the range 1..I
of
componet numbers). If the graph has J
isolated nodes
(nodes that have no incident edges), then numbers returned by
num
are always smaller than or equal to IJ
.
The item under cutNodes
is a list of all cut nodes.
For a graph G
in objectasrecord style you can
compute the biconnected components R
with R =
{G.bccs}
. In Ozlibrary style use R = {GraphLib.bccs
G}
.
The running time of the algorithm on a graph G
with nodes
Ns
and edges Es
is in
O(Ns+Es)
.
G
is a maximal subgraph of G
that is 2edge
connected. 2edge connected components of a graph G
provide a proper partition of G
's nodes.
A bridge in G
is an edge that, iff removed, separates
a weakly connected subgraph of G
in at least two disjoint
weakly connected subgraphs.
This packages's implementation of 2edge connected componets
computes the number I
of 2edge connected components and
numbers the components from 1
to I
. Apart
from that a list of all bridges is computed. The value returned is a
record of the following type:
unit(count : int
num : node > int
bridges : node list)
The item under count
is the number I
of
components. The item under num
is a function that, given
an node N
, returns the number of the component
N
belongs to. The item under cutNodes
is a
list of all cut nodes.
For a graph G
in objectasrecord style you can
compute the 2edge connected components R
with R =
{G.beccs}
. In Ozlibrary style use R = {GraphLib.beccs
G}
.
The running time of the algorithm on a graph G
with
nodes Ns
and edges Es
is in
O(Ns+Es)
.
Reach
of a directed graph
G
is a binary relation on the set of G
's
nodes. (N1,N2)
is in Reach
iff there
exists a directed path from N1
to N2
in
G
.
This package's implementation of reflexive, transitive closure
computes the characteristic function F : node x node >
bool
of Reach
, i.e. it computes a function that
takes two nodes N1
and N2
and returns true
iff G
contains a path from N1
to
N2
. Additionally, if G
is acyclic then
G
is sorted
topologically.
For a graph G
in objectasrecord style you can
compute the characteristic function F
of G
's
reachablity relation with F = {G.reachability}
. In
Ozlibrary style use F = {GraphLib.reachability G}
.
The running time of the algorithm on a graph G
with
nodes Ns
and edges Es
is in
O(Ns^3)
. More precisely, the running time on an
acyclic graph with irredundant edges Es'
is in
O(Ns+Es+Es'*Ns)
(the irredundant edges of an
acyclic graph G
are the edges of G
's
transitive reduction, see below). On a cyclic graph the running time
is in O(Ns^2+k^3)
where k
is the number of
G
's strongly connected components.
G'
of a directed acyclic graph
G
(that does not contain two edges with equal source and
target) is the minimal subgraph of G
that has the same
reflexive, transitive closure. I.e. G'
equals
G
except that it does not contain G
's
redundant edges (an edge E
from N1
to
N2
is redundant iff there already is a path with length
at least 2
from N1
to N2
that
does not use E
).
This package's implementation of transitive reduction computes a
list of a graph's redundant edges. As a side effect G
is
sorted topologically.
Important: If for two nodes N1
and N2
the graph contains several edges with source N1
and
target N2
all but one (random choice) of these edges
are considered redundant.
For a directed acyclic graph G
in objectasrecord
style you can compute the redundant edges Es
with
Es = {G.redundantEdges}
. In Ozlibrary style use
Es = {GraphLib.redundantEdges G}
. If G
is
cyclic then {G.redundantEdges}
returns the atom
'cyclic'
.
The running time of the algorithm on a directed acyclic graph
G
with nodes Ns
and edges Es
is
in O(Ns^3)
. More precisely, the running time is in
O(Ns+Es+Es'*Ns)
, where Es'
are the
irredundant edges of G
, i.e. Es' = Es 
{G.redundantEdges}
.
G
is a node that has no
incident edges. This package provides a procedure that computes a
record of the following type:
unit(count : int
nodes : node list)
The item under count
is the total number of isolated
nodes. The item under nodes
is a list of all isolated
nodes.
To obtain such a record R
for a graph G
in objectasrecord style use R = {G.isolatedNodes}
. In
Ozlibrary style use R = {GraphLib.isolatedNodes G}
.
The running time of the algorithm on a graph G
with
nodes Ns
and edges Es
is in
O(Ns+Es)
.
E
with source N1
and target
N2
is an edge such that N1
and
N2
have no incident edges other than E
.
This package provides a procedure that computes a record of the
following type:
unit(count : int
edges : node list)
The item under count
is the total number of isolated
edges. The item under edges
is a list of all isolated
edges.
To obtain such a record R
for a graph G
in objectasrecord style use R = {G.isolatedEdges}
. In
Ozlibrary style use R = {GraphLib.isolatedEdges G}
.
The running time of the algorithm on a graph G
with nodes
Ns
and edges Es
is in
O(Ns+Es)
.
smielegraph.pkg
from the Mogul. Then execute
ozmake freshen package=smielegraph.pkg
In case that you did not already install mogul:/duchier/ozmake on your machine, note that it is also available in the Mogul.