Graphiterator Algorithms

Several basic graph algorithms were re-implemented to use only graph iterators and data accessors. Moreover they share three design decisions:

1.

algorithms are instances of classes

2.

algorithm instances have the ability to ``advance''

3.

algorithm instances provide access to their internal states

An example for an algorithm that supports the first two decisions is:

    class Algorithm {
      int state, endstate;
    public:
      Algorithm(int max) : endstate(max), state(0) { }
      void next() { state++; }
      bool finished() { return state>=endstate; } 
    };

With this class Algorithm we can easily instantiate an algorithm object:

    Algorithm alg(5); 
    while (!alg.finished()) alg.next();

This small piece of code creates an algorithm object and invokes ``next()'' until it has reached an end state.

An advantage of this design is that we can write basic algorithms, which can be used in a standardized way and if needed, inspection of internal states and variables can be provided without writing complex code. Additionally, it makes it possible to write persistent algorithms, if the member variables are persistent.

Actually, those algorithms are quite more flexible than ordinary written algorithm functions:

    template<class Alg>
    class OutputAlg {
      Alg alg;
    public:
      OutputAlg(int m) : alg(m) {
        cout << "max state: " << m << endl; }
      void next() {
        cout << "old state: " << alg.state;
        alg.next(); 
        cout << " new state: " << alg.state << endl; }
      bool finished() { return alg.finished(); }
    };

This wrapper algorithm can be used like this:

    OutputAlg<Algorithm> alg(5);
    while (!alg.finished()) alg.next();

In addition to the algorithm mentioned earlier this wrapper writes the internal states to the standard output.

This is as efficient as rewriting the ``Algorithm''-class with an output mechanism, but provides more flexibility.