(this file is automatically generated from Java source)
Back to book index.

Graph Tutorial

This tutorial explains basics of the Graph API, which is found in jdd.util.graph.*

Introduction

Graph API contains a simple set of data structures and algorithms for graph based operations. This API is provided since graph algorithms are often used in conjunction with BDDs et. al. in, for example, model checking.

The Graph API is very simple. To represent a Graph G =(V,E), you create a Graph object and either add Node and Edge objects to it, or use the GraphIO class to to read a graph file.

A sequence for creating an undirected graphs may look like this:

Once more, visualization is done via DOT:

Notice that removing n11 also removed the two edges attached to it.

Here is a directed graph:






Traversing graphs

Nodes and edges are stored in java Vectors:

In each node, incoming and outgoing arcs are stored as two linked lists:






Extra elements

The Node and Edge object have some extra member variables for storing your intermediate data during execution of algorithms. These members are called extran and maybe overwritten by other algorithms (your or JDD's internal algorithms), so be carefull. There are also other usefull members such as flags, weight and id. See also the AttributeExplorer class

The following implementation of a well-known algorithm demonstrates the correct use of these members:

Here, instead of

we could have used Notice also how we avoid using a hashtable/map by using Node.extra1 in this algorithm!




Simple graph algorithms

SimpleAlgorithms contains a set of basic graph operations, such as

Some other simple operations are found in GraphOperation. Currently we support:

Approximative algorithms

ApproximationAlgorithms contains a set of graph algorithms that are fast but not optimal.Following algorithms is currently present:

Shortest-path algorithms

ShortestPath contains the following shortest-path algorithms

Minimum spanning tree algorithms

MinimumSpanningTree contains the following minimum spanning-tree algorithms:

Maximum-flow algorithms

MaximumFlow will contain max-flow algorithms in near future

Strongly connected component

StronglyConnectedComponent implements the SCC algorithms of Tarjan and (soon) Nuutila.

Weak topological ordering

WeakTopologicalOrdering implements the WTO algorithm of Bourdoncle.
It is very similar to the SCO algorithm of Tarjan

GraphIO

The class GraphIO contains function to load/save graphs to disk. Three formats are supported:

Here is a example of a sequence that uses all three formats:

Graph Factory

The class Factory is used to create a set of 'interesting' graphs:

A complete graph K5 is created by Factory.complete(5):

A directed tree is created by Factory.tree():

A permutation tree is created by Factory.permutation():

Here is a path of length 5, created by Factory.path(5):

Here is a circle of length 5, created by Factory.circle(5):

A finally, the complete bipartie graph K2,3 , created by the call Factory.complete_bipartie(2,3):