| 620 | */ |
| 621 | template <class BidirectionalGraph> |
| 622 | static inline PathExtensionResult extendPath( |
| 623 | Path<typename boost::graph_traits<BidirectionalGraph>::vertex_descriptor>& path, |
| 624 | Direction dir, const BidirectionalGraph& g, |
| 625 | unordered_set<typename boost::graph_traits<BidirectionalGraph>::vertex_descriptor>& visited, |
| 626 | const ExtendPathParams& params) |
| 627 | { |
| 628 | typedef BidirectionalGraph G; |
| 629 | typedef boost::graph_traits<G> graph_traits; |
| 630 | typedef typename graph_traits::vertex_descriptor V; |
| 631 | typename graph_traits::out_edge_iterator oei, oei_end; |
| 632 | typename graph_traits::in_edge_iterator iei, iei_end; |
| 633 | |
| 634 | assert(path.size() > 0); |
| 635 | size_t origPathLen = path.size(); |
| 636 | PathExtensionResultCode result = ER_DEAD_END; |
| 637 | bool lookBehind = params.lookBehindStartVertex; |
| 638 | |
| 639 | assert(!path.empty()); |
| 640 | while (path.size() < params.maxLen) |
| 641 | { |
| 642 | result = extendPathBySingleVertex(path, dir, g, |
| 643 | params.trimLen, params.fpTrim, lookBehind); |
| 644 | |
| 645 | if (result != ER_LENGTH_LIMIT) |
| 646 | break; |
| 647 | |
| 648 | const V& head = (dir == FORWARD) ? path.back() : path.front(); |
| 649 | bool inserted; |
| 650 | boost::tie(boost::tuples::ignore, inserted) = visited.insert(head); |
| 651 | if (!inserted) { |
| 652 | result = ER_CYCLE; |
| 653 | if (dir == FORWARD) |
| 654 | path.pop_back(); |
| 655 | else |
| 656 | path.pop_front(); |
| 657 | break; |
| 658 | } |
| 659 | |
| 660 | /* override `lookBehindStartVertex` after first extension */ |
| 661 | lookBehind = params.lookBehind; |
| 662 | } |
| 663 | |
| 664 | if (params.maxLen != NO_LIMIT && path.size() == params.maxLen) |
| 665 | result = ER_LENGTH_LIMIT; |
| 666 | |
| 667 | assert(path.size() >= origPathLen); |
| 668 | unsigned extension = path.size() - origPathLen; |
| 669 | |
| 670 | /* |
| 671 | * Sanity check: If no length limit was imposed, we must have stopped |
| 672 | * the extension for some other reason (e.g. dead end) |
| 673 | */ |
| 674 | assert(params.maxLen != NO_LIMIT || result != ER_LENGTH_LIMIT); |
| 675 | |
| 676 | return std::make_pair(extension, result); |
| 677 | } |
| 678 | |
| 679 | /** |