find multiple edges given 2 vertices in BOOST graph

Question

I am using Boost Graph library for some project and i want to find number of times an edge is repeated in a graph. for example,

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Node_Info, Edge_Info > Graph_t;  
//node_info and Edge_info are external node and edge properties (structures)

suppose if i have two nodes, node1 and node2 and there is an edge between them (node1, node2). edge property for each edge contains a timestamp start, end.. and there can be many such edges in the graph with different timestamps. for example.

edge1 = (node1, node2) with start = 100, end = 200.
edge2 = (node1, node2) with start = 250, end = 400.

I know that in a boost graph, given two vertices, we can find whether an edge exists in the graph or not using the following.

std::pair < edge_t, bool > p = boost::edge( node1, node2, myGraph );
if(p.second == 1)  cout << "edge exists!" << endl;
else cout << " does not exist " << endl;

But this could mean that it would only return any one edge even if multiple edges exist with different edge properties --> PROBLEM

can anyone suggest an idea how to get such multiple edges between two given nodes? Thanks!

Mikael Persson Mikael Persson · Accepted Answer · 2014-01-19T07:14:53

There are a couple of ways to do this.

1) Just check the out-edges for all that go to the desired target:

boost::graph_traits<Graph_t>::out_edge_iterator ei, ei_end;
boost::tie(ei, ei_end) = out_edges( node1, myGraph );
int parallel_count = 0;
for( ; ei != ei_end; ++ei) {
  if( target(*ei, myGraph) == node2 ) {
    cout << "Found edge (node1, node2) with property: " << myGraph[*ei] << endl;
    ++parallel_count;
  };
};
cout << "There are a total of " << parallel_count << " parallel edges." << endl;

2) Specify boost::multisetS as the OutEdgeListS template argument to adjacency_list, this will enable an extra function called edge_range which returns a range of iterators for all the "parallel" edges coming out of u and going into v, as the documentation page states:

std::pair<out_edge_iterator, out_edge_iterator>
edge_range(vertex_descriptor u, vertex_descriptor v,
           const adjacency_list& g)
Returns a pair of out-edge iterators that give the range for all the parallel edges from u to v. This function only works when the OutEdgeList for the adjacency_list is a container that sorts the out edges according to target vertex, and allows for parallel edges. The multisetS selector chooses such a container.

The reason why this function is only available for multisetS is because in order to provide (easily) a range of iterators to parallel edges, you need the edges to be grouped together, which is the case for multisetS because they are sorted by vertex-descriptor, and therefore, all parallel out-edges are grouped together. That's the only container choice that will give you this, otherwise, you have to use option (1) (note: creating a filter_iterator (see docs) could come in handy if you really use this a lot).

find multiple edges given 2 vertices in BOOST graph

1 Answers