| 402 | */ |
| 403 | template <class Graph> |
| 404 | static inline PathExtensionResultCode |
| 405 | extendPathBySingleVertex( |
| 406 | Path<typename boost::graph_traits<Graph>::vertex_descriptor>& path, |
| 407 | Direction dir, const Graph& g, unsigned trim, unsigned fpTrim, |
| 408 | bool lookBehind) |
| 409 | { |
| 410 | assert(!path.empty()); |
| 411 | |
| 412 | typedef typename boost::graph_traits<Graph>::vertex_descriptor V; |
| 413 | |
| 414 | V t, v; |
| 415 | PathExtensionResultCode result; |
| 416 | |
| 417 | const V& head = (dir == FORWARD) ? path.back() : path.front(); |
| 418 | |
| 419 | if (lookBehind) { |
| 420 | |
| 421 | Direction otherDir = (dir == FORWARD) ? REVERSE : FORWARD; |
| 422 | boost::tie(t, result) = successor(head, otherDir, g, trim, fpTrim); |
| 423 | |
| 424 | if (result == ER_AMBI_OUT) |
| 425 | return ER_AMBI_IN; |
| 426 | |
| 427 | /* |
| 428 | * Tricky: If our path was seeded on a tip, we want to stop the |
| 429 | * extension when we reconnect to the graph. We can detect that |
| 430 | * we are on tip if we reach a branching point where the predecessor |
| 431 | * vertex in the path does not match the expected predecessor `t`. |
| 432 | */ |
| 433 | if (path.size() > 1) { |
| 434 | if (result == ER_DEAD_END) { |
| 435 | /* no predecessors or all predecessors were tips */ |
| 436 | return ER_AMBI_IN; |
| 437 | } else { |
| 438 | /* check if we are on a tip */ |
| 439 | assert(result == ER_LENGTH_LIMIT); |
| 440 | const V& prev = (dir == FORWARD) ? |
| 441 | *(path.rbegin() + 1) : *(path.begin() + 1); |
| 442 | if (prev != t) |
| 443 | return ER_AMBI_IN; |
| 444 | } |
| 445 | } |
| 446 | |
| 447 | } |
| 448 | |
| 449 | boost::tie(v, result) = successor(head, dir, g, trim, fpTrim); |
| 450 | if (result != ER_LENGTH_LIMIT) |
| 451 | return result; |
| 452 | |
| 453 | if (dir == FORWARD) |
| 454 | path.push_back(v); |
| 455 | else |
| 456 | path.push_front(v); |
| 457 | |
| 458 | return ER_LENGTH_LIMIT; |
| 459 | } |
| 460 | |
| 461 | /** |