From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2000-09-11 08:22:32
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
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
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
With more complex algorithms even for solving identical problems (eg.
Path vs. Preflow/Push to solve the Maximum Flow problem) there is no
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
some local changes to the underlying network in algorithms building on
top of the
more fundamental algorithms). Other features of algorithm objects
- 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
requires additional visitors.
- Multiple algorithms can be run pseudo-parallel. Before someone starts
it: No, using threads is *not* the same! For example, running shortest
from start and destination node similtaneously can greatly increase
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
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
an area where people are solving NP complete problems taking days to
... 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
machine (eg. restart a promising branch on multiple machines with
to a random generator or to move the solution to machine with more
the algorithms state does no longer fit into the machine with lower
The implementation of the algorithms is actually not much different than
- 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
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
executation of the algorithm is passed to the user. That is, instead
of calling the
visitor the function uses something like
if (mask & state)
where 'mask' represents a combination of the states where the
algorithm is to
be interupted and 'state' represents a possible event moving the
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
algorithm until it is done can be used.
I really prefer this approach. ... and an algorithm implemented that way
used easily to follow the visitor style.
Do You Yahoo!?
Talk to your friends online with Yahoo! Messenger.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk