Re: [boost] BGL experience report and question

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-10 22:51:08

----- Original Message -----
From: "Lie-Quan Lee" <llee_at_[hidden]>

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

That was exactly the generational coloring I was talking about.
However, you said "generalized", which I don't think is an appropriate term
in this case.

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

Not so great :(