Re: [Boost-users] Bidirectional Graph and undirected graphs

Subject: Re: [Boost-users] Bidirectional Graph and undirected graphs
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-05-13 20:37:30

> So the answer to what I think Daniel is asking is "it won't work". In
> particular:
>
> Currently our graph uses a pointer to an edge object as an edge descriptor.
> Getting the "source" using such an edge descriptor can't always return v
> since it has no way of knowing where the edge descriptor came from.
>
>
> will cause algorithms like breadth_first_search to break.
>
> I can change the edge descriptor to be a pair of vertices, which would
> solve the problem, but don't want to if not needed.
>
>
> I think it's needed if algorithms like the BGL breadth_first_search are
> going to work. No?
>

Yeah. I'm a little slow today.

That's correct - you need to add a little extra info to the edge descriptor
to make it work for most of the BGL algorithms, despite the fact that edge
(u,v) == (v,u). Basically, you have to be able to pin an edge to a source
vertex in order for any of the algorithms to work.

You could modify your edge descriptor to be pair<edge*,vertex> where the
second element acts as as the source of the edge. That would allow you to
"fix" the source and target of the edge so that they work with BFS/DFS
algorithms. The storage overhead should be negligible.

Using pair<vertex,vertex> may not be as helpful, since it may require a
lookup for the stored edge object.

Hopefully, this is a better answer

Andrew Sutton
andrew.n.sutton_at_[hidden]