Boost logo

Boost :

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
>
>
>
>


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk