CODEWITHSUNDEEP
c++boostiteratorboost-graphfilter-iterator
Pogo
Pogo

Reputation: 495

out_edges() implementation in BOOST filtered_graph without edge_predicate

I have a boost::filtered_graph< Graph_t, boost::keep_all, vertex_predicate >

Say FG is my filtered graph. and v1 is any node for which i want to find all out edges using out_edge_iterators

edge_predicate here is " keep_all " vertex predicate is some predicate which is used to modify node properties of graph.

In the documentation, it is given:

graph_traits<filtered_graph>::out_edge_iterator 
//The type for the iterators returned by out_edges(), which is:
filter_iterator<EdgePredicate, graph_traits<Graph>::out_edge_iterator>
The iterator is a model of MultiPassInputIterator.

now, when i define out_edge_iterators: 

out_edge_iterator begin, end;
boost::tie( begin, end) = out_edges ( v1, FG )

What I expect, is the following: 1. It should take into account the edge_predicate provided and filter the edges according to that. basically the begin and end iterators should be filter_iterators based on edge predicate. 2. I dont think vertex_predicate should be called on other node of the edges. for example, suppose v1 has 3 out edges ( v1, v2 ), (v1, v4), (v1, v6).

My observation is : In the process of finding out_edges of v1, the vertex_predicate is being called on the very first opposite node of v1. In above case, 

suppose begin --> points to edge (v1, v2), then, 
out_edges(v1, G) ---> calls vertex_predicate on **v2**

Why is this the case? Is it because of implementation of out_edges() function which would involve finding adjacent nodes and return the first node found ?

The same case I observe when adjacent_vertices() is called. documentation says it models as out_edge_iterator < edge_predicate , ... > .

I am getting my expected results. but I want to know whether my guess is correct or not ? I am not providing any edge_predicate to filtered-graph as such.

Please suggest.

Upvotes: 0

Views: 614

Answers (1)

Michael Simbirsky
Michael Simbirsky

Reputation: 3103

When filtered graph excludes some vertex, it also excludes all edges associated with it. It means some edges are filtered out even though you specify keep_all.

Internally, filtered_graph has a special edge predicate (combined from edge predicate and vertex predicate) which is used to filter out edges. When you ask for out-edges of a given vertex, BGL returns you a pair of filter iterators.

The "End" iterator is trivially based on the "end" of function out_edges for underlying graph. The "Begin" iterator starts from "begin" of function out_edges and checks whether "target" of the edge is part of the graph. If it is not, the iterator skips it until it finds a good vertex (or hit "end").

Therefore iterator has constantly check for "target" vertex and call the vertex predicate.

Upvotes: 1

Related Questions