Re: [boost] BGL: dijkstra questions

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-01-15 22:21:51

On Tue, 15 Jan 2002, David Abrahams wrote:

> What about BFS? It looks to me as though a three-state color map is totally
> unneeded there. The way the algorithm is written out, it checks for gray
> vertices, but there's nothing in the if/else clauses. Am I confused again?

We wanted to use BFS as the building block for other algorithms such as
Dijkstra's, so we needed those if/else clauses for visitor event points
which get used by these other algorithms.

>
> ----- Original Message -----
> From: "David Abrahams" <david.abrahams_at_[hidden]>
> To: <boost_at_[hidden]>
> Sent: Tuesday, January 15, 2002 8:32 PM
> Subject: Re: [boost] BGL: dijkstra questions
>
>
> >
> > ----- Original Message -----
> > From: "Jeremy Siek" <jsiek_at_[hidden]>
> > >
> > > Yes, the coloring tells you whether the vertex is
> > >
> > > undiscovered, and not yet in the queue -> white
> > > discovered, and in the queue -> gray
> > > discovered, and out of the queue -> black
> > >
> > > so you know when to either insert into the queue or update a vertex
> > > already in the queue.
> > >
> > > david.> Hmm, note that the queue must be made |E| big in my case. Still,
> > you need a
> > >
> > > Right, so this would change the complexity of the algorithm from
> > >
> > > O((V + E) log V) to O((V + E) log E)
> >
> > Okay, I can see that I was missing at least a few things: you want to know
> > if the vertex is gray, if you're going to avoid duplicate vertices in the
> > Queue, since E can potentially be much larger than V in interesting
> graphs.
> >
> > Anyway, since the user has to supply you with an IndexMap so that you can
> > translate vertices to queue positions, you don't need a ternary color map.
> > In fact, you don't need a separate color map at all. Just reserve two
> values
> > (say, -1 and 0) in the IndexMap to indicate the white and black nodes.
> >
> > Reducing the size of the queue just makes the case stronger for keeping
> > distances and predecessors in the queue, at least if the user doesn't want
> > to make a record of them.
> >
> > DIJKSTRA(G, s, w)
> >   for each vertex u in V
> >     d[u] := infinity
> >     p[u] := u
> >   end for
> >   INSERT(Q, (s,s,0))
> >   while (Q != Ø)
> >     t,u,x := EXTRACT-MIN(Q)
> >     if u not in S
> >       d[u] = x         // optional! d not needed for algorithm
> >       p[u] = t         // also optional
> >       S := S U { u }
> >       for each vertex v in Adj[u]
> >         if v not in S // optimization - first path to v is always shortest
> >           if v in Q   // optimization - save space in Q if possible
> >              RELAX(Q, (u, v, x + w(u,v)))  // replace path if shorter
> >           else
> >              INSERT(Q, (u, v, x + w(u,v))) // insert unconditionally
> >       end for
> >   end while
> >
> > This approach has all the same benefits I mentioned before, I think, and
> it
> > seems as efficient as what you currently do. I note that the distance and
> > predecessor maps are only written once for each node. Putting them in the
> > priority queue takes the place of that, but I would assume that frequent
> > modifications all together in the priority queue improves locality.
> > I might still be missing something, though.
> >
> > -Dave
> >
> >
> >
> > Info: http://www.boost.org  Send unsubscribe requests to:
> <mailto:boost-unsubscribe_at_[hidden]>
> >
> > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
> >
> >
>
>
> Info: http://www.boost.org  Send unsubscribe requests to: <mailto:boost-unsubscribe_at_[hidden]>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

----------------------------------------------------------------------
 Jeremy Siek                          http://www.osl.iu.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------