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:
- STL-like iterators to access the set of nodes and edges
- adjacency iterators to access the edges incident to a node
- data accessors to access data associated with an object
identified by an iterator
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.
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.
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.
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).