[Boost-users] Bidirectional Graph and undirected graphs

[Daniel Russel]

I'm trying to add the needed functions to make one of our graphs work as a boost graph and ran into a contradiction in the docs:
The introduction to bidirectional graph says

"For undirected graphs this [need for extra information] is not an issue, since the in_edges() and out_edges() functions are the same, they both return the edges incident to the vertex."

however the function docs for in_edges say:
"For both directed and undirected graphs, the target of an out-edge is required to be vertex v and the source is required to be a vertex that is adjacent to v."

The latter implies that undirected graphs have to have two copies of each edge, one pointed each direction.

Which is correct? The former, I hope :-) Thanks.

[Andrew Sutton]

The latter implies that undirected graphs have to have two copies of each edge, one pointed each direction.

Which is correct? The former, I hope :-) Thanks.

Undirected graphs store only one set of edges. The implementation of the just makes it seem like two different copies :)

Andrew Sutton
andrew....@gmail.com

[Daniel Russel]

On Wed, May 13, 2009 at 1:38 PM, Andrew Sutton <andrew....@gmail.com> wrote:

The latter implies that undirected graphs have to have two copies of each edge, one pointed each direction.

Which is correct? The former, I hope :-) Thanks.

Undirected graphs store only one set of edges. The implementation of the just makes it seem like two different copies :)

I'm not sure I understand your response. I was being sloppy and using edge and edge descriptor interchangeably (since there is no separate concept of an edge).

If the returned edge_descriptor (by out_edges) must have v at its source, then there must be at least two edge descriptors per undirected edge. 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. 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. Thanks.

 --Daniel

[Andrew Sutton]

Undirected graphs store only one set of edges. The implementation of the just makes it seem like two different copies :)

I'm not sure I understand your response. I was being sloppy and using edge and edge descriptor interchangeably (since there is no separate concept of an edge).

Edge, edge descriptor. Close enough. In an adjacency list (at least), an edge descriptor is actually based on a pair. This means that the out and in edge iterators can construct an edge descriptor such that source and target return reasonable answers without having to duplicate data.

Andrew Sutton
andrew....@gmail.com

[Michael Olea]

Right, but I believe that Daniel is asking what his code has to do so that his implementation of an undirected graph "works as a boost graph", which in this context I think means is a valid model of the incidence graph concept:

http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/IncidenceGraph.html

The note for out_edges(u, g):

Returns an iterator-range providing access to the out-edges (for directed graphs) or incident edges (for undirected graphs) of vertex u in graph g. The source vertex of an edge obtained via an out edge iterator is guaranteed (for both directed and undirected graphs) to be the vertex u used in the call to out_edges(u, g) and the target vertex must the a vertex adjacent to u.[1] 

Return type: std::pair<out_edge_iterator, out_edge_iterator>

And the footnote:

[1] For undirected graphs, the edge (u,v) is the same as edge (v,u), so without some extra guarantee an implementation would be free use any ordering for the pair of vertices in an out-edge. For example, if you call out_edges(u, g), and v is one of the vertices adjacent to u, then the implementation would be free to return (v,u) as an out-edge which would be non-intuitive and cause trouble for algorithms. Therefore, the extra requirement is added that the out-edge connecting u and v must be given as (u,v) and not (v,u).

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?

-- Michael

[Andrew Sutton]

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....@gmail.com