Bidirectional Graph and undirected graphs
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.
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.n.sutton@gmail.com
On Wed, May 13, 2009 at 1:38 PM, 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 :)
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
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.n.sutton@gmail.com
On May 13, 2009, at 3:04 PM, Andrew Sutton wrote:
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.
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
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
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
participants (3)
-
Andrew Sutton -
Daniel Russel -
Michael Olea