Graph Data Structure and Basic Graph Algorithms

Sebastian Miele

provides

x-ozlib://smiele/graph/graph.ozf

x-ozlib://smiele/graph/lib/graph.ozf

x-ozlib://smiele/graph/lib/node-array.ozf

x-ozlib://smiele/graph/lib/edge-array.ozf

x-ozlib://smiele/graph/lib/node-matrix.ozf

x-ozlib://smiele/graph/lib/edge-matrix.ozf

Overview

• fully dynamic and mutable labeled graphs
• dynamic and mutable mappings from the nodes or edges of a graph to arbitrary values (node arrays and edge arrays)
• dynamic and mutable node matrices and edge matrices
• basic graph algorithms

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:

• topological sorting
• weakly connected components
• 2-node connected components alias biconnected components
• 2-egde connected components
• strongly connected components
• transitive closure (reachability relation)
• acyclic transitive reduction (redundant edges)
• isolated nodes
• isolated edges

Oz-Library Style versus Object-as-Record Style

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}

   {EnglishToGerman.get hi}

This package provides graphs in the object-as-record style at the URI x-ozlib://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 object-as-record style are also in oject-as-record style. So if you prefer to use the object-as-record style, you will only need this single functor.

Versions in the Oz-library style are available at the URIs x-ozlib://smiele/graph/lib/graph.ozf, x-ozlib://smiele/graph/lib/node-array.ozf and x-ozlib://smiele/graph/lib/edge-array.ozf.

Example

We first show how to use a graph in object-as-record style. Here, the graph G is a record of functions newNode, newEdge, indeg, ... .

   local
      [Graph] = {Link ['x-ozlib://smiele/graph/graph.ozf']}
      [Dict]  = {Link ['x-ozlib://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
      %% 2-edge connected but not 2-node/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

Here is how to do the same using the in the Oz-library style functors. Now a graph G is the first argument expected by the functions in the functor lib/graph.ozf:

   local
      [Graph] = {Link ['x-ozlib://smiele/graph/lib/graph.ozf']}
      [Dict]  = {Link ['x-ozlib://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
      %% 2-edge connected but not 2-node 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

Manual

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:

• Graphs
  • Creation
  • Modification
  • Access
• Node Arrays
• Edge Arrays
• Node Matrices
• Edge Matrices
• Algorithms

Graphs

An edge with source N1 and target N2is 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

• visible in a graph G iff it belongs to G and is visible,
• hidden in a graph G iff it belongs to G and is hidden,
• valid in a graph G iff it belongs to G and is visible or hidden

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

Creation

In Oz-library style you have to link the functor x-ozlib://smiele/graph/lib/graph.ozf under some varible GraphLib. Then you can use G = {GraphLib.new} to create a new and empty graph in Oz-library style and G1 = {GraphLib.clone G} to create a clone of G in G1.

Modification

Access

{G.isVisibleEdge E}

Procedures for hidden nodes and edges:

In order to apply any of the the above procedures to a graph G in Oz-library style, for example outEdges of a node N, use {GraphLib.outEdges G N} (where GraphLib is the module obtained by linking the functor x-ozlib://smiele/graph/lib/graph.ozf).

Node Arrays

In object-as-record 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 Oz-library style you use {NALib.new G InitX} (where NALib is the module obtained by linking x-ozlib://smiele/graph/lib/node-array.ozf).

Node arrays are dynamic. This means that you can

1. create a node array NA that maps the nodes of a graph G to some intial value InitX
2. and then add some new nodes 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:

In order to apply any of the above procedures to a node array NA in Oz-library style, for example inc for some node N, call {NALib.inc NA N} (where NALib is the module obtained by linking x-ozlib://smiele/graph/lib/node-array.ozf).

Edge Arrays

Given a graph G in Oz-library style you get a new edge array EA in Oz-library style with EA = {EALib.new G InitX} (where EALib is the module obtained by linking x-ozlib://smiele/graph/lib/edge-array.ozf).

Node Matrices

In object-as-record 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 Oz-library style you use {NMLib.new G InitX} (where NMLib is the module obtained by linking x-ozlib://smiele/graph/lib/node-matrix.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:

In order to apply any of the above procedures to a node matrix NM in Oz-library 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 x-ozlib://smiele/graph/lib/node-matrix.ozf).

Edge Matrices

Given a graph G in Oz-library style you get a new edge matrix EM in Oz-library style with EM = {EMLib.new G InitX} (where EMLib is the module obtained by linking x-ozlib://smiele/graph/lib/edge-matrix.ozf).

Algorithms

• topological sorting
• weakly connected components
• 2-node connected components alias biconnected components
• 2-egde connected components
• strongly connected components
• transitive closure (reachability relation)
• acyclic transitive reduction (redundant edges)
• isolated nodes
• isolated edges

Topological Sorting

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 after-wards 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|)..

Weakly Connected Components, Strongly Connected Components

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)

For a graph G in object-as-record style you can compute the weakly/strongly connected components R with R = {G.wccs} or R = {G.sccs}. In Oz-library 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|).

2-Node Connected Components alias Biconnected Components

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)

For a graph G in object-as-record style you can compute the biconnected components R with R = {G.bccs}. In Oz-library 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|).

2-Edge Connected Components

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 2-edge connected componets computes the number I of 2-edge 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)

For a graph G in object-as-record style you can compute the 2-edge connected components R with R = {G.beccs}. In Oz-library 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|).

Transitive Closure (Reachability Relation)

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 object-as-record style you can compute the characteristic function F of G's reachablity relation with F = {G.reachability}. In Oz-library 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.

Acyclic Transitive Reduction (Redundant Edges)

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 object-as-record style you can compute the redundant edges Es with Es = {G.redundantEdges}. In Oz-library 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}.

Isolated Nodes

   unit(count : int
        nodes : node list)

To obtain such a record R for a graph G in object-as-record style use R = {G.isolatedNodes}. In Oz-library 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|).

Isolated Edges

   unit(count : int
        edges : node list)

To obtain such a record R for a graph G in object-as-record style use R = {G.isolatedEdges}. In Oz-library 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|).

Installation

In case that you did not already install mogul:/duchier/ozmake on your machine, note that it is also available in the Mogul.