In the context of BGL, I need to iterate the in_edges and out_edges but I want to exclude those that are part of the reverse edges i.e. exclude those that are part of the reverse edges property_map. The code below shows what I would like to do but of course the property_map doesn't have find and end methods.
UPDATE:
A possible solution is to maintain a separate structure like a map containing the reverse edges while building the graph. This will work if I had control of the graph building but I don't because I use the function read_dimacs_max_flow to read a graph file in DIMACS format. So I can only rely on BGL's accessibility methods to figure out what is what.
Graph definition:
typedef adjacency_list_traits<vecS, vecS, bidirectionalS> ttraits;
typedef adjacency_list<vecS, vecS, bidirectionalS,
// vertex properties
property<vertex_index_t, int,
property<vertex_color_t, default_color_type> >,
// edge properties
property<edge_capacity_t, int,
property<edge_residual_capacity_t, int,
property<edge_reverse_t, ttraits::edge_descriptor> > >, no_property, vecS> tbgl_adjlist_bidir;
typedef graph_traits<tbgl_adjlist_bidir>::vertex_descriptor tvertex;
typedef graph_traits<tbgl_adjlist_bidir>::edge_descriptor tedge;
typedef property_map<tbgl_adjlist_bidir, edge_capacity_t>::type tedge_capacity_map;
typedef property_map<tbgl_adjlist_bidir, edge_reverse_t>::type treverse_edge_map;
typedef property_map<tbgl_adjlist_bidir, vertex_color_t>::type tvertex_color_map;
typedef property_map<tbgl_adjlist_bidir, vertex_index_t>::type tvertex_index_map;
typedef graph_traits<tbgl_adjlist_bidir>::vertex_iterator tvertex_iterator;
typedef graph_traits<tbgl_adjlist_bidir>::edge_iterator tedge_iterator;
typedef graph_traits<tbgl_adjlist_bidir>::out_edge_iterator tout_edge_iterator;
typedef graph_traits<tbgl_adjlist_bidir>::in_edge_iterator tin_edge_iterator;
and the example snippet of what I would like to do (but doesn't compile with the error below):
tvertex_index_map indices = get(vertex_index, bgl_adjlist_bidir);
tedge_capacity_map capacities = get(edge_capacity, bgl_adjlist_bidir);
treverse_edge_map rev_edges = get(edge_reverse, bgl_adjlist_bidir);
// iterate all vertices in the right order
for (int current = 0; current < m_num_vertices; ++current) {
printf("processing vertex=%d\n", current);
tin_edge_iterator ei1, ei1_end;
for (tie(ei1, ei1_end) = in_edges(tvertex(current), bgl_adjlist_bidir); ei1 != ei1_end; ++ei1) {
// exclude reverse edges <<<<<<<======= HOW DO I DO THIS??
if (rev_edges.find(*ei1) != rev_edges.end()) {
continue;
}
int in = indices[boost::source(*ei1, bgl_adjlist_bidir)];
printf("in edge: %d <- %d \n", current, in);
}
}
and the compiler error:
/Users/bravegag/code/fastcode_project/build_debug$ make 2> out ; grep -i "error" ./out
[ 2%] Building CXX object CMakeFiles/submodularity.dir/src/graph/hp_adjlist_bidir.cc.o
/Users/bravegag/code/fastcode_project/code/src/api/hp_adjlist_bidir.h:146:18: error: 'treverse_edge_map' has no member named 'find'
/Users/bravegag/code/fastcode_project/code/src/api/hp_adjlist_bidir.h:146:42: error: 'treverse_edge_map' has no member named 'end'
make[2]: *** [CMakeFiles/submodularity.dir/src/graph/hp_adjlist_bidir.cc.o] Error 1
make[1]: *** [CMakeFiles/submodularity.dir/all] Error 2
make: *** [all] Error 2
Your edge_reverse property-map will associate an edge descriptor to each edge of the graph. So, a "find" function wouldn't make any sense since all edges will have a corresponding entry in that property-map (remember, such property-maps are not necessarily implemented as a std::map object, in fact, they are not in the case of internal properties).
One thing you can and should do is set the value of the reverse-edge property for each edge such that it is either the edge-descriptor of the reverse-edge or an invalid edge-descriptor (for non-reverse edges). Then, the check (instead of "find") is merely one of checking if the reverse-edge property is a valid edge-descriptor or not.
Unfortunately, the BGL does not provide a null_edge() static function (like it does with null_vertex()). This was probably an omission by the developers (I developed a few of my own graph structures, and I included a null_edge() function, but not in Boost). This means that it could be hard to come up with a good and portable "null-edge" descriptor value to use. One option is to use a specific bit pattern, like this:
ttraits::edge_descriptor my_null_edge;
memset((char*)&my_null_edge, 0xFF, sizeof(ttraits::edge_descriptor));
And then, you make sure all reverse-edge properties for non-reverse edges are set to my_null_edge and then implement your loop with this comparison:
for (tie(ei1, ei1_end) = in_edges(tvertex(current), bgl_adjlist_bidir); ei1 != ei1_end; ++ei1) {
// exclude reverse edges
if (rev_edges[*ei1] != my_null_edge) {
continue;
}
int in = indices[boost::source(*ei1, bgl_adjlist_bidir)];
printf("in edge: %d <- %d \n", current, in);
}
If your reverse-edge properties are very sparse, you might want to have an external property-map using a map class like std::map (or std::unordered_map). The things you specify as EdgeProperty or VertexProperty in the adjacency-list class template are stored by value (kind-of) for each vertex or edge of the graph. If you want std::map behavior (only stores the subset with an assigned property), then you can simply do this externally to the adjacency-list graph, the nice thing with property-maps is that they don't have to correspond to internal properties, which can be useful too. So, you can do this:
typedef std::map< tedge, tedge > treverse_edge_map;
treverse_edge_map rev_edges;
And if you need to use rev_edges as a BGL property-map, then you can use:
typedef boost::associative_property_map< treverse_edge_map > tbgl_reverse_edge_map;
tbgl_reverse_edge_map bgl_rev_edges = boost::make_assoc_property_map(rev_edges);
But then, of course, once it is a BGL-style property-map, you can no longer use the "find" mechanism to figure out if the property is set or not for a given edge.