| 470 | */ |
| 471 | template <typename Graph> |
| 472 | static inline size_t depth( |
| 473 | typename boost::graph_traits<Graph>::vertex_descriptor root, |
| 474 | Direction dir, const Graph& g) |
| 475 | { |
| 476 | typedef typename boost::graph_traits<Graph>::vertex_descriptor V; |
| 477 | typedef typename boost::graph_traits<Graph>::out_edge_iterator OutEdgeIter; |
| 478 | typedef typename boost::graph_traits<Graph>::in_edge_iterator InEdgeIter; |
| 479 | |
| 480 | OutEdgeIter oei, oei_end; |
| 481 | InEdgeIter iei, iei_end; |
| 482 | |
| 483 | unordered_set<V, hash<V> > visited; |
| 484 | typedef unordered_map<V, size_t> DepthMap; |
| 485 | DepthMap depthMap; |
| 486 | std::deque<V> q; |
| 487 | |
| 488 | q.push_back(root); |
| 489 | |
| 490 | visited.insert(root); |
| 491 | std::pair<typename DepthMap::iterator, bool> inserted = |
| 492 | depthMap.insert(std::make_pair(root, 0)); |
| 493 | assert(inserted.second); |
| 494 | |
| 495 | size_t maxDepth = 0; |
| 496 | while (!q.empty()) { |
| 497 | V& u = q.front(); |
| 498 | visited.insert(u); |
| 499 | typename DepthMap::const_iterator it = depthMap.find(u); |
| 500 | assert(it != depthMap.end()); |
| 501 | size_t depth = it->second; |
| 502 | if (depth > maxDepth) |
| 503 | maxDepth = depth; |
| 504 | if (dir == FORWARD) { |
| 505 | for (boost::tie(oei, oei_end) = out_edges(u, g); |
| 506 | oei != oei_end; ++oei) { |
| 507 | V v = target(*oei, g); |
| 508 | if (visited.find(v) == visited.end()) { |
| 509 | visited.insert(v); |
| 510 | std::pair<typename DepthMap::iterator, bool> inserted = |
| 511 | depthMap.insert(std::make_pair(v, depth+1)); |
| 512 | assert(inserted.second); |
| 513 | q.push_back(v); |
| 514 | } |
| 515 | } |
| 516 | } else { |
| 517 | assert(dir == REVERSE); |
| 518 | for (boost::tie(iei, iei_end) = in_edges(u, g); |
| 519 | iei != iei_end; ++iei) { |
| 520 | V v = source(*iei, g); |
| 521 | if (visited.find(v) == visited.end()) { |
| 522 | visited.insert(v); |
| 523 | std::pair<typename DepthMap::iterator, bool> inserted = |
| 524 | depthMap.insert(std::make_pair(v, depth+1)); |
| 525 | assert(inserted.second); |
| 526 | q.push_back(v); |
| 527 | } |
| 528 | } |
| 529 | } |