Prev Up Next
Go backward to Wrapping Computer Algebra Components with Java and CORBA
Wolfgang Küchlin and Andreas Weber

Go up to Applications
Go forward to A Generic Programming Environment for
High-Performance Mathematical Libraries
Wolfgang Schreiner


Generic Graph Algorithms
Dietmar Kühl

Implementing (non-trivial) graph algorithms is generally a difficult enterprise due to the complexity of the algorithms. Thus, it is desirable that an implementation of graph algorithms is widely applicable. That means in an ideal world it is possible to apply the implementation of a graph algorithm to an arbitrary graph data structure (as long as it is suited to the requirements of the algorithms: it makes no sense to apply an algorithm for planar graphs to a general graph). Since graph algorithms often extend more basic algorithms, injecting additional computation into an algorithm would also be desirable. Both goals can be achieved, at least to a certain degree. The applicability to an arbitrary graph data structure can be provided by implementing algorithms independent from a graph data structure and using only some kind of minimal abstraction. A workable abstraction consists of the following parts:

These abstractions are sufficient for a large class of algorithms. Additionally, auxiliary modifications of graphs can easily be made by adapters providing a different view of the graph. To also provide additional operations during the execution of an algorithm, the easiest approach is to use algorithm objects which behave similarly to iterators. After initialization the algorithm object is used advanced stepwise until the user of the algorithm wants to execute additional code. The algorithm object iterates through the states of the algorithm with the user having full control over the execution of the algorithm.

Iterators

There is nothing special about the iterators accessing the set of nodes and edges; these are just iterators for sequences like, for example, the STL iterators. The only thing to be noted is that the data associated with an object identified by an iterator is not directly accessed via the iterator but rather through a data accessor (see below). Special to graphs are adjacency iterators which are used to explore the local structure of a graph. An adjacency iterator iterates over the nodes adjacent to a fixed node. A possible set of methods (in addition to general functions like constructors, assignment, and destructors) for an adjacency iterator could be (ait1 and ait2 are adjacency iterators):
ait1.valid()
Return true if there still is an adjacent node
ait1.next()
Advance the iterator to the next adjacent node
ait1.cur_adj()
Return an adjacency iterator for the current adjacent node
ait1.same_node(ait2)
Return true if both iterators are positioned on the node (independent from the current node)
ait1.same_edge(ait2)
Return true if both iterators are positioned on the same current edge
Like the iterators for the set of nodes and edges, data for the objects identified by an iterator is accessed through data accessors.

Data Accessors

Graph algorithms normally access data associated with the nodes and edges of the graph which is often interpreted as weight, length, cost, or flow, depending on the context of the algorithm. Because graph algorithms often use other algorithms as subalgorithms, the interpretation of the associated data may change, for example, from "length" to "cost." In addition, the algorithms need to store auxiliary data with the nodes and/or edges, for example to indicate a temporary flow value or that a node was already visited. In general, there are many ways to represent the data used by the algorithms. For example, the data may be stored in the node or edge data structure or in some container indexed by node or edge numbers, or the data may be calculated from other fields. Algorithms should not depend on a specific approach for the representation but rather allow the user of the algorithm to select an appropriate representation. Thus, data associated with objects identified by iterators are not directly accessed but rather through some abstraction called data accessor with a simple interface such as (da is a data accessor, it is some iterator, and val is an object of the type of the associated data):
get(da, it)
Retrieve the data identified by da which is associated with the object identified by it
set(da, it, val)
Set the data identified by da which is associated with the object identified by it to the value val
In some sense the data associated with a node or an edge can be seen as a table where the rows are identified by an iterator and the columns are identified by data accessors. However, the organization of this table can be very different from a normal table: some columns may be made up from one or more tables while other columns are stored with the corresponding objects directly or are calculated.

Algorithm Objects

Graph algorithms are often slightly modified to suit specific needs. For example, during the execution of an algorithm certain intermediate data may be recorded (a typical example is the DFS number during the execution of a DFS) or some data is collected to provide a "certificate" justifying the correctness of a result. Although the additional computations are essential in some situations, they are completely useless in others. To provide the possibility to modify an algorithm, non-trivial algorithms should be implemented as algorithm objects which behave much like iterators. The major difference between normal iterators and algorithm objects is that the latter iterate over a set of intermediate states during an algorithm instead of iterating over a collection of objects. Together with appropriate access functions to the current state of the algorithm, this can be used for example to record intermediate data, inject additional computations, modify the behavior of the algorithm, terminate the algorithm prematurely after the desired result is computed, or to provide recovery points to avoid loss of computed results during time consuming computations. This approach is, of course, not specific to graph algorithms. However, it is not yet widely applied (e.g., the STL algorithms are all monolithic blocks).
 

Prev Up Next