Re: [boost] BGL experience report and question

From: Lie-Quan Lee (llee_at_[hidden])
Date: 2002-01-10 22:32:10

On Thu, 2002-01-10 at 21:41, David Abrahams wrote:
> Hi Rich, thanks for your reply...
> 

> > I am thinking about to change the way about color in breadth_frist_visit
> > so that generalized color can be used without hack.
> 
> Sorry, what do you mean by that? Are you referring to my generational
> coloring scheme?

I am the scheme we talked about in the phone. In fact, I have used
generalized color in minimum degree algorithm where I borrowed from
Fortran implementation.  The idea is to have amortized constant time to
reset color of all vertices. One implementation could be:
To have an integer as base color in the class,  white means the value is
less than that base integer. Grey means it is equal to that integer.
Black means the value is equal to that integer plus one. Then, reset all
vertex color is to increment that integer by 2.  

> > As to stopping
> > breadth-first-search as soon as some conditions satisfies, currently we
> > did not have a good solution yet. -- Your idea about flushing queue is
> > interesting, but there are several unknown issues such as who does the
> > flushing and where the flushing happened.
> 
> Jeremy emailed me the idea of modifying the property map so every node is
> reported to be black. I don't know whether that's effective or not.

Right, that means all the remaining vertices will still get travesed and
touched.

>
> >
> > I think dijkstra's algorithm can do something like uniform cost search.
> 
> I'm not sure that is related to best-first, is it?
> Best-first has very different qualities from dijkstra. For example, the cost
> of the path to date is irrelevant; you only care about the estimate of the
> length to the goal (which, BTW, is not something I see a provision for in
> any of the BGL algorithms). It's really a heuristic search.
> 
> > You can construct your search with mutable_queue
> 
> Where is mutable_queue documented?
 
That is why you should buy the book :-) Last a couple months we were
mostly focusing on our book. We have not had time to update/add some
html docs yet.

-- 
Lie-Quan Lee (AKA: Rich Lee)
Research Associate                   
Open Systems Laboratory        Phone:    [phone]
Computer Science Department    Email:    llee_at_[hidden]
Indiana University             Homepage: http://www.osl.iu.edu/~llee