Re: [boost] [Graphs] visitors

From: jsiek_at_[hidden]
Date: 2000-09-11 10:40:05

Hi Dietmar,

I'd like to experiment with algorithm objects. Do you have some
example code, or perhaps the interface for an algorithm object...
perhaps graph search?

Cheers,

Jeremy

Dietmar Kuehl writes:
 > 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
 > 
 > 
 > 
 >