Re: [boost] [Graphs] visitors

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2000-09-11 08:22:32

Hi,
jsiek_at_[hidden] wrote:

> Opinions?

I figure that you already guessed my opinion: Algorithm objects is the
way to go :-)
For equally structured algorithms like the search algorithms, the idea
of visitors seems
to be natural (and can in fact easily be implemented if you have an
algorithm object)
but actually it even breaks apart in this rather basic setting: There
are much more
interesting events for depth first search than there are for general
searches. For DFS
events like inspection of a non-tree edge, ie. an edge to an already
visited not, are
interesting, eg. for an "open ear decomposition", while in general the
non-tree edges
are of no interest or are not inspected by the algorithm at all (eg.
with a best first search
the edges are investigated before it is known whether they will become
non-tree edes
are not).

With more complex algorithms even for solving identical problems (eg.
Augmenting
Path vs. Preflow/Push to solve the Maximum Flow problem) there is no
similarity at
all. On the other hand it is interesting to resume execution of an
algorithm later on
(eg. for the Maximum Flow algorithms it is often useful to resume
executation after
some local changes to the underlying network in algorithms building on
top of the
more fundamental algorithms). Other features of algorithm objects
include

- It is obvious how to prematurally terminate an algorithm. Of course
this can be
  done with visitors, too. However, it is more to be done by the
visitors and/or
  requires additional visitors.

- Multiple algorithms can be run pseudo-parallel. Before someone starts
mentioning
  it: No, using threads is *not* the same! For example, running shortest
path algorithms
  from start and destination node similtaneously can greatly increase
performance of
  finding shortest path between two nodes ("What is the fastest way to
get from A to
  B?"). This is something I can't see how to do it with visitors at all!

- The state of algorithms is exposed (well, this of course depends on
the interface of
  the algorithm object and a corresponding object can be passed to the
visitors, too)
  and can be modified (again, depending on the interface). In fact, it
could be possible
  to skip certain parts of the algorithm.

- The state of algorithms can be made persistant. What's that for? I'm
coming from
  an area where people are solving NP complete problems taking days to
be solved.
  ... and this are only the experimentation problems! Real applications
might take much
  longer. It can be rather benefitial to store and later resume
algorithms, eg. to protect
  against whatever cause of failures or to move solution of a problem to
a different
  machine (eg. restart a promising branch on multiple machines with
different seeds
  to a random generator or to move the solution to machine with more
memory once
  the algorithms state does no longer fit into the machine with lower
memory).

The implementation of the algorithms is actually not much different than
using visitors:

- Instead of using local variable, all variables are declared as members
of a class.
  These can very well be public members to grant arbitrary access to the
algorithm's
  state. On the other hand, to guarantee certain termination conditions,
it might as well
  be that some state information is kept read-only.

- The main loop (yes, there is only *one* main loop! This is the
granularity of the
  algorithms) is basically part of a switch statement to resume
executation at the
  right place (applying Duff's Device).

- An optional optimization is the use of bitmasks to determine positions
where
  executation of the algorithm is passed to the user. That is, instead
of calling the
  visitor the function uses something like

    if (mask & state)
      return state;

  where 'mask' represents a combination of the states where the
algorithm is to
  be interupted and 'state' represents a possible event moving the
algorithm into
  a certain state (eg. for a  search algorithm this can be something
like "label node").

What really differs is the use of the algorithm: Instead of defining
sets of functions
basically a conditional statement is used. Of course, if no
customization is needed,
a simple call can be made sufficient or an auxiliary function just
restarting the
algorithm until it is done can be used.

I really prefer this approach. ... and an algorithm implemented that way
can be
used easily to follow the visitor style.

Regards,
  Dietmar


__________________________________________________
Do You Yahoo!?
Talk to your friends online with Yahoo! Messenger.
http://im.yahoo.com