BGL Undirected Graph Out-Edge Iterator Source/Target

user_19635267 0
Viewed 27

I have the following undirected BGL graph description:

typedef boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, VProp, EProp> Graph;

And in my code I'm using the following loop to access the out-edges of a given node v:

  OutEdgeIter out_i;
  OutEdgeIter out_end;

  for (boost::tie(out_i, out_end) = out_edges(v, g);  out_i != out_end; ++out_i)
  {
    Edge curEdge = *out_i;
    Vertex curNeighbor = boost::target(curEdge, g);

    // Other stuff here.
  }

I'm noticing that any node v I get the out-edges of in this way has a peculiar property: the target of that node will always be the neighbor of v, and the source will always be v itself. This of course makes sense in the case of a directed graph, but my graph is undirected as mentioned previously. It's unclear (just from a definition perspective) what the source of target of an undirected edge is.

Is the above a documented, guaranteed property of BGL? I've written a few unit tests that depend on this property and they all pass, but it bugs me that I can't find this in the BGL docs (or perhaps I am just very bad at reading them).

(As an aside, it also appears that the "direction" of the edge does not matter when setting edge properties. Setting the weight of (u, v) to five causes the weight of boost::edge(v, u, g) to also return five: it still appears that there is only one underlying edge object.)

boost-graph c++
1 Answers

Is the above a documented, guaranteed property of BGL

Yes. I’m not quite sure it would be documented, but I’ve seen the code swapping the order of the arguments to add_edge to be in that order.

Note, it makes some sense conceptually: If you remember that an adjacency list is … a list of adjacencies, and they’re stored per source vertex, it makes a lot of sense that when iterating adjacencies from a vertex v you will get a list of adjacent vertices (targets) and when iterating out_edges it makes sense to alway synthesize the edge as (source, target) for each of the adjacent targets.

This is the most relevant piece of documentation I know:

The interface that the BGL provides for accessing and manipulating an undirected graph is the same as the interface for directed graphs described in the following sections, however there are some differences in the behaviour and semantics. For example, in a directed graph we can talk about out-edges and in-edges of a vertex. In an undirected graph there is no in'' and out'', there are just edges incident to a vertex. Nevertheless, in the BGL we still use the out_edges() function (or in_edges()) to access the incident edges in an undirected graph. Similarly, an undirected edge has no source'' and target'' but merely an unordered pair of vertices, but in the BGL we still use source() and target() to access these vertices. The reason the BGL does not provide a separate interface for undirected graphs is that many algorithms on directed graphs also work on undirected graphs, and it would be inconvenient to have to duplicate the algorithms just because of an interface difference. When using undirected graphs just mentally disregard the directionality in the function names. The example below demonstrates using the out_edges(), source(), and target() with an undirected graph. The source code for this example and the following one can be found in example/undirected_adjacency_list.cpp.

user_853710
Related