| 172 | */ |
| 173 | template <class Graph> |
| 174 | static inline bool trueBranch( |
| 175 | const typename boost::graph_traits<Graph>::edge_descriptor& e, |
| 176 | unsigned depth, Direction dir, const Graph& g, unsigned trim, |
| 177 | unsigned fpTrim, unordered_set<typename boost::graph_traits<Graph>::vertex_descriptor>& visited) |
| 178 | { |
| 179 | typedef typename boost::graph_traits<Graph>::vertex_descriptor V; |
| 180 | |
| 181 | typename boost::graph_traits<Graph>::out_edge_iterator oei, oei_end; |
| 182 | typename boost::graph_traits<Graph>::in_edge_iterator iei, iei_end; |
| 183 | |
| 184 | const V& u = (dir == FORWARD) ? source(e, g) : target(e, g); |
| 185 | const V& v = (dir == FORWARD) ? target(e, g) : source(e, g); |
| 186 | |
| 187 | /* branches with bubbles/cycles are considered true branches */ |
| 188 | if (visited.find(v) != visited.end()) |
| 189 | return true; |
| 190 | |
| 191 | if (depth >= trim) |
| 192 | return true; |
| 193 | |
| 194 | visited.insert(v); |
| 195 | |
| 196 | if (dir == FORWARD) { |
| 197 | for (boost::tie(oei, oei_end) = out_edges(v, g); |
| 198 | oei != oei_end; ++oei) { |
| 199 | if (trueBranch(*oei, depth+1, FORWARD, g, trim, fpTrim, visited)) |
| 200 | return true; |
| 201 | } |
| 202 | /* |
| 203 | * Note: The test for depth/lookAhead >= fpTrim before changing |
| 204 | * traversal direction is needed to deal with an X-shaped |
| 205 | * graph pattern that is frequently created by Bloom false positives. |
| 206 | * See the test for `trueBranch` in `ExtendPathTest.h` for an example. |
| 207 | */ |
| 208 | if (depth >= fpTrim || lookAhead(v, FORWARD, fpTrim, g)) { |
| 209 | for (boost::tie(iei, iei_end) = in_edges(v, g); |
| 210 | iei != iei_end; ++iei) { |
| 211 | if (source(*iei, g) == u) |
| 212 | continue; |
| 213 | if (trueBranch(*iei, 0, REVERSE, g, trim, fpTrim, visited)) |
| 214 | return true; |
| 215 | } |
| 216 | } |
| 217 | } else { |
| 218 | assert(dir == REVERSE); |
| 219 | for (boost::tie(iei, iei_end) = in_edges(v, g); |
| 220 | iei != iei_end; ++iei) { |
| 221 | if (trueBranch(*iei, depth+1, REVERSE, g, trim, fpTrim, visited)) |
| 222 | return true; |
| 223 | } |
| 224 | /* |
| 225 | * Note: The test for depth/lookAhead >= fpTrim before changing |
| 226 | * traversal direction is needed to deal with an X-shaped |
| 227 | * graph pattern that is frequently created by Bloom false positives. |
| 228 | * See the test for `trueBranch` in `ExtendPathTest.h` for an example. |
| 229 | */ |
| 230 | if (depth >= fpTrim || lookAhead(v, REVERSE, fpTrim, g)) { |
| 231 | for (boost::tie(oei, oei_end) = out_edges(v, g); |