equal
deleted
inserted
replaced
571 void start(const EM &em) |
571 void start(const EM &em) |
572 { |
572 { |
573 while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge(); |
573 while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge(); |
574 } |
574 } |
575 |
575 |
|
576 ///Runs %DFS algorithm to visit all nodes in the graph. |
|
577 |
|
578 ///This method runs the %DFS algorithm in order to |
|
579 ///compute the |
|
580 ///%DFS path to each node. The algorithm computes |
|
581 ///- The %DFS tree. |
|
582 ///- The distance of each node from the root in the %DFS tree. |
|
583 /// |
|
584 ///\note d.run() is just a shortcut of the following code. |
|
585 ///\code |
|
586 /// d.init(); |
|
587 /// for (NodeIt it(graph); it != INVALID; ++it) { |
|
588 /// if (!d.reached(it)) { |
|
589 /// d.addSource(it); |
|
590 /// d.start(); |
|
591 /// } |
|
592 /// } |
|
593 ///\endcode |
|
594 void run() { |
|
595 init(); |
|
596 for (NodeIt it(*G); it != INVALID; ++it) { |
|
597 if (!reached(it)) { |
|
598 addSource(it); |
|
599 start(); |
|
600 } |
|
601 } |
|
602 } |
|
603 |
576 ///Runs %DFS algorithm from node \c s. |
604 ///Runs %DFS algorithm from node \c s. |
577 |
605 |
578 ///This method runs the %DFS algorithm from a root node \c s |
606 ///This method runs the %DFS algorithm from a root node \c s |
579 ///in order to |
607 ///in order to |
580 ///compute the |
608 ///compute the |
649 |
677 |
650 ///The distance of a node from the root(s). |
678 ///The distance of a node from the root(s). |
651 |
679 |
652 ///Returns the distance of a node from the root(s). |
680 ///Returns the distance of a node from the root(s). |
653 ///\pre \ref run() must be called before using this function. |
681 ///\pre \ref run() must be called before using this function. |
654 ///\warning If node \c v is unreachable from the root(s) then the return value |
682 ///\warning If node \c v is unreachable from the root(s) then the return |
655 ///of this funcion is undefined. |
683 ///value of this funcion is undefined. |
656 int dist(Node v) const { return (*_dist)[v]; } |
684 int dist(Node v) const { return (*_dist)[v]; } |
657 |
685 |
658 ///Returns the 'previous edge' of the %DFS tree. |
686 ///Returns the 'previous edge' of the %DFS tree. |
659 |
687 |
660 ///For a node \c v it returns the 'previous edge' |
688 ///For a node \c v it returns the 'previous edge' |
1438 template <typename EM> |
1466 template <typename EM> |
1439 void start(const EM &em) { |
1467 void start(const EM &em) { |
1440 while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge(); |
1468 while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge(); |
1441 } |
1469 } |
1442 |
1470 |
1443 /// \brief Runs %DFS algorithm from node \c s. |
1471 /// \brief Runs %DFSVisit algorithm from node \c s. |
1444 /// |
1472 /// |
1445 /// This method runs the %DFS algorithm from a root node \c s. |
1473 /// This method runs the %DFS algorithm from a root node \c s. |
1446 /// \note d.run(s) is just a shortcut of the following code. |
1474 /// \note d.run(s) is just a shortcut of the following code. |
1447 ///\code |
1475 ///\code |
1448 /// d.init(); |
1476 /// d.init(); |
1452 void run(Node s) { |
1480 void run(Node s) { |
1453 init(); |
1481 init(); |
1454 addSource(s); |
1482 addSource(s); |
1455 start(); |
1483 start(); |
1456 } |
1484 } |
|
1485 |
|
1486 /// \brief Runs %DFSVisit algorithm to visit all nodes in the graph. |
|
1487 |
|
1488 /// This method runs the %DFS algorithm in order to |
|
1489 /// compute the %DFS path to each node. The algorithm computes |
|
1490 /// - The %DFS tree. |
|
1491 /// - The distance of each node from the root in the %DFS tree. |
|
1492 /// |
|
1493 ///\note d.run() is just a shortcut of the following code. |
|
1494 ///\code |
|
1495 /// d.init(); |
|
1496 /// for (NodeIt it(graph); it != INVALID; ++it) { |
|
1497 /// if (!d.reached(it)) { |
|
1498 /// d.addSource(it); |
|
1499 /// d.start(); |
|
1500 /// } |
|
1501 /// } |
|
1502 ///\endcode |
|
1503 void run() { |
|
1504 init(); |
|
1505 for (NodeIt it(*_graph); it != INVALID; ++it) { |
|
1506 if (!reached(it)) { |
|
1507 addSource(it); |
|
1508 start(); |
|
1509 } |
|
1510 } |
|
1511 } |
1457 ///@} |
1512 ///@} |
1458 |
1513 |
1459 /// \name Query Functions |
1514 /// \name Query Functions |
1460 /// The result of the %DFS algorithm can be obtained using these |
1515 /// The result of the %DFS algorithm can be obtained using these |
1461 /// functions.\n |
1516 /// functions.\n |