| 545 | */ |
| 546 | template <typename Graph> |
| 547 | inline static |
| 548 | std::pair<typename boost::graph_traits<Graph>::vertex_descriptor, bool> |
| 549 | longestBranch(const typename boost::graph_traits<Graph>::vertex_descriptor& u, |
| 550 | Direction dir, const Graph& g) |
| 551 | { |
| 552 | typedef typename boost::graph_traits<Graph>::vertex_descriptor V; |
| 553 | typedef typename boost::graph_traits<Graph>::out_edge_iterator OutEdgeIter; |
| 554 | typedef typename boost::graph_traits<Graph>::in_edge_iterator InEdgeIter; |
| 555 | |
| 556 | OutEdgeIter oei, oei_end; |
| 557 | InEdgeIter iei, iei_end; |
| 558 | size_t maxDepth = 0; |
| 559 | unsigned degree = 0; |
| 560 | bool tie = false; |
| 561 | /* note: had to initialize to prevent compiler warnings */ |
| 562 | V longestBranch = u; |
| 563 | if (dir == FORWARD) { |
| 564 | for (boost::tie(oei, oei_end) = out_edges(u, g); |
| 565 | oei != oei_end; ++oei) { |
| 566 | degree++; |
| 567 | const V& v = target(*oei, g); |
| 568 | size_t d = depth(v, dir, g) + 1; |
| 569 | if (d > maxDepth) { |
| 570 | maxDepth = d; |
| 571 | longestBranch = v; |
| 572 | tie = false; |
| 573 | } else if (d == maxDepth && v < longestBranch) { |
| 574 | /* |
| 575 | * make an arbitrary choice among branches |
| 576 | * of equal length using the vertex comparison |
| 577 | * operator (operator<). |
| 578 | */ |
| 579 | longestBranch = v; |
| 580 | tie = true; |
| 581 | } |
| 582 | } |
| 583 | } else { |
| 584 | assert(dir == REVERSE); |
| 585 | for (boost::tie(iei, iei_end) = in_edges(u, g); |
| 586 | iei != iei_end; ++iei) { |
| 587 | degree++; |
| 588 | const V& v = source(*iei, g); |
| 589 | size_t d = depth(v, dir, g) + 1; |
| 590 | if (d > maxDepth) { |
| 591 | maxDepth = d; |
| 592 | longestBranch = v; |
| 593 | tie = false; |
| 594 | } else if (d == maxDepth && v < longestBranch) { |
| 595 | /* |
| 596 | * make an arbitrary choice among branches |
| 597 | * of equal length using the vertex comparison |
| 598 | * operator (operator<). |
| 599 | */ |
| 600 | longestBranch = v; |
| 601 | tie = true; |
| 602 | } |
| 603 | } |
| 604 | } |