
Boost : 
From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 20000911 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 nontree edge, ie. an edge to an already
visited not, are
interesting, eg. for an "open ear decomposition", while in general the
nontree 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
nontree 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 pseudoparallel. 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 readonly.
 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk