Changes in lemon/dfs.h [584:33c6b6e755cd:788:c92296660262] in lemon-1.2
- File:
-
- 1 edited
-
lemon/dfs.h (modified) (35 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/dfs.h
r584 r788 48 48 ///The type of the map that stores the predecessor 49 49 ///arcs of the %DFS paths. 50 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.50 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 51 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 52 ///Instantiates a \c PredMap. … … 63 63 64 64 ///The type of the map that indicates which nodes are processed. 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 65 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 66 ///By default, it is a NullMap. 66 67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 68 ///Instantiates a \c ProcessedMap. … … 82 83 83 84 ///The type of the map that indicates which nodes are reached. 84 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.85 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 86 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 87 ///Instantiates a \c ReachedMap. … … 97 98 98 99 ///The type of the map that stores the distances of the nodes. 99 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.100 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 100 101 typedef typename Digraph::template NodeMap<int> DistMap; 101 102 ///Instantiates a \c DistMap. … … 225 226 ///\ref named-templ-param "Named parameter" for setting 226 227 ///\c PredMap type. 227 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.228 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 228 229 template <class T> 229 230 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > { … … 245 246 ///\ref named-templ-param "Named parameter" for setting 246 247 ///\c DistMap type. 247 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.248 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 248 249 template <class T> 249 250 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > { … … 265 266 ///\ref named-templ-param "Named parameter" for setting 266 267 ///\c ReachedMap type. 267 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.268 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 268 269 template <class T> 269 270 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { … … 285 286 ///\ref named-templ-param "Named parameter" for setting 286 287 ///\c ProcessedMap type. 287 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.288 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 288 289 template <class T> 289 290 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { … … 412 413 ///The simplest way to execute the DFS algorithm is to use one of the 413 414 ///member functions called \ref run(Node) "run()".\n 414 ///If you need more control on the execution, firstyou have to call415 ///\ref init() , then you can add a source node with \ref addSource()415 ///If you need better control on the execution, you have to call 416 ///\ref init() first, then you can add a source node with \ref addSource() 416 417 ///and perform the actual computation with \ref start(). 417 418 ///This procedure can be repeated if there are nodes that have not … … 633 634 ///Runs the algorithm to visit all nodes in the digraph. 634 635 635 ///This method runs the %DFS algorithm in order to compute the 636 ///%DFS path to each node. 637 /// 638 ///The algorithm computes 639 ///- the %DFS tree (forest), 640 ///- the distance of each node from the root(s) in the %DFS tree. 636 ///This method runs the %DFS algorithm in order to visit all nodes 637 ///in the digraph. 641 638 /// 642 639 ///\note <tt>d.run()</tt> is just a shortcut of the following code. … … 670 667 ///@{ 671 668 672 ///The DFS path to anode.673 674 ///Returns the DFS path to a node.669 ///The DFS path to the given node. 670 671 ///Returns the DFS path to the given node from the root(s). 675 672 /// 676 673 ///\warning \c t should be reached from the root(s). … … 680 677 Path path(Node t) const { return Path(*G, *_pred, t); } 681 678 682 ///The distance of anode from the root(s).683 684 ///Returns the distance of anode from the root(s).679 ///The distance of the given node from the root(s). 680 681 ///Returns the distance of the given node from the root(s). 685 682 /// 686 683 ///\warning If node \c v is not reached from the root(s), then … … 691 688 int dist(Node v) const { return (*_dist)[v]; } 692 689 693 ///Returns the 'previous arc' of the %DFS tree for anode.690 ///Returns the 'previous arc' of the %DFS tree for the given node. 694 691 695 692 ///This function returns the 'previous arc' of the %DFS tree for the … … 699 696 /// 700 697 ///The %DFS tree used here is equal to the %DFS tree used in 701 ///\ref predNode() .698 ///\ref predNode() and \ref predMap(). 702 699 /// 703 700 ///\pre Either \ref run(Node) "run()" or \ref init() … … 705 702 Arc predArc(Node v) const { return (*_pred)[v];} 706 703 707 ///Returns the 'previous node' of the %DFS tree .704 ///Returns the 'previous node' of the %DFS tree for the given node. 708 705 709 706 ///This function returns the 'previous node' of the %DFS 710 707 ///tree for the node \c v, i.e. it returns the last but one node 711 /// froma %DFS path from a root to \c v. It is \c INVALID708 ///of a %DFS path from a root to \c v. It is \c INVALID 712 709 ///if \c v is not reached from the root(s) or if \c v is a root. 713 710 /// 714 711 ///The %DFS tree used here is equal to the %DFS tree used in 715 ///\ref predArc() .712 ///\ref predArc() and \ref predMap(). 716 713 /// 717 714 ///\pre Either \ref run(Node) "run()" or \ref init() … … 734 731 /// 735 732 ///Returns a const reference to the node map that stores the predecessor 736 ///arcs, which form the DFS tree .733 ///arcs, which form the DFS tree (forest). 737 734 /// 738 735 ///\pre Either \ref run(Node) "run()" or \ref init() … … 740 737 const PredMap &predMap() const { return *_pred;} 741 738 742 ///Checks if anode is reached from the root(s).739 ///Checks if the given node. node is reached from the root(s). 743 740 744 741 ///Returns \c true if \c v is reached from the root(s). … … 766 763 ///The type of the map that stores the predecessor 767 764 ///arcs of the %DFS paths. 768 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.765 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 769 766 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 770 767 ///Instantiates a PredMap. … … 781 778 782 779 ///The type of the map that indicates which nodes are processed. 783 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.784 ///By default it is a NullMap.780 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 781 ///By default, it is a NullMap. 785 782 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 786 783 ///Instantiates a ProcessedMap. … … 801 798 802 799 ///The type of the map that indicates which nodes are reached. 803 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.800 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 804 801 typedef typename Digraph::template NodeMap<bool> ReachedMap; 805 802 ///Instantiates a ReachedMap. … … 816 813 817 814 ///The type of the map that stores the distances of the nodes. 818 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.815 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 819 816 typedef typename Digraph::template NodeMap<int> DistMap; 820 817 ///Instantiates a DistMap. … … 831 828 832 829 ///The type of the DFS paths. 833 ///It must meetthe \ref concepts::Path "Path" concept.830 ///It must conform to the \ref concepts::Path "Path" concept. 834 831 typedef lemon::Path<Digraph> Path; 835 832 }; … … 837 834 /// Default traits class used by DfsWizard 838 835 839 /// To make it easier to use Dfs algorithm 840 /// we have created a wizard class. 841 /// This \ref DfsWizard class needs default traits, 842 /// as well as the \ref Dfs class. 843 /// The \ref DfsWizardBase is a class to be the default traits of the 844 /// \ref DfsWizard class. 836 /// Default traits class used by DfsWizard. 837 /// \tparam GR The type of the digraph. 845 838 template<class GR> 846 839 class DfsWizardBase : public DfsWizardDefaultTraits<GR> … … 870 863 /// Constructor. 871 864 872 /// This constructor does not require parameters, thereforeit initiates865 /// This constructor does not require parameters, it initiates 873 866 /// all of the attributes to \c 0. 874 867 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 900 893 typedef TR Base; 901 894 902 ///The type of the digraph the algorithm runs on.903 895 typedef typename TR::Digraph Digraph; 904 896 … … 908 900 typedef typename Digraph::OutArcIt OutArcIt; 909 901 910 ///\brief The type of the map that stores the predecessor911 ///arcs of the DFS paths.912 902 typedef typename TR::PredMap PredMap; 913 ///\brief The type of the map that stores the distances of the nodes.914 903 typedef typename TR::DistMap DistMap; 915 ///\brief The type of the map that indicates which nodes are reached.916 904 typedef typename TR::ReachedMap ReachedMap; 917 ///\brief The type of the map that indicates which nodes are processed.918 905 typedef typename TR::ProcessedMap ProcessedMap; 919 ///The type of the DFS paths920 906 typedef typename TR::Path Path; 921 907 … … 987 973 ///Runs DFS algorithm to visit all nodes in the digraph. 988 974 989 ///This method runs DFS algorithm in order to compute990 /// the DFS path to each node.975 ///This method runs DFS algorithm in order to visit all nodes 976 ///in the digraph. 991 977 void run() 992 978 { … … 1000 986 SetPredMapBase(const TR &b) : TR(b) {} 1001 987 }; 1002 ///\brief \ref named-func-param "Named parameter" 1003 ///for setting PredMap object. 1004 /// 1005 ///\ref named-func-param "Named parameter" 1006 ///for setting PredMap object. 988 989 ///\brief \ref named-templ-param "Named parameter" for setting 990 ///the predecessor map. 991 /// 992 ///\ref named-templ-param "Named parameter" function for setting 993 ///the map that stores the predecessor arcs of the nodes. 1007 994 template<class T> 1008 995 DfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1018 1005 SetReachedMapBase(const TR &b) : TR(b) {} 1019 1006 }; 1020 ///\brief \ref named-func-param "Named parameter" 1021 ///for setting ReachedMap object. 1022 /// 1023 /// \ref named-func-param "Named parameter" 1024 ///for setting ReachedMap object. 1007 1008 ///\brief \ref named-templ-param "Named parameter" for setting 1009 ///the reached map. 1010 /// 1011 ///\ref named-templ-param "Named parameter" function for setting 1012 ///the map that indicates which nodes are reached. 1025 1013 template<class T> 1026 1014 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1036 1024 SetDistMapBase(const TR &b) : TR(b) {} 1037 1025 }; 1038 ///\brief \ref named-func-param "Named parameter" 1039 ///for setting DistMap object. 1040 /// 1041 /// \ref named-func-param "Named parameter" 1042 ///for setting DistMap object. 1026 1027 ///\brief \ref named-templ-param "Named parameter" for setting 1028 ///the distance map. 1029 /// 1030 ///\ref named-templ-param "Named parameter" function for setting 1031 ///the map that stores the distances of the nodes calculated 1032 ///by the algorithm. 1043 1033 template<class T> 1044 1034 DfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1054 1044 SetProcessedMapBase(const TR &b) : TR(b) {} 1055 1045 }; 1056 ///\brief \ref named-func-param "Named parameter" 1057 ///for setting ProcessedMap object. 1058 /// 1059 /// \ref named-func-param "Named parameter" 1060 ///for setting ProcessedMap object. 1046 1047 ///\brief \ref named-func-param "Named parameter" for setting 1048 ///the processed map. 1049 /// 1050 ///\ref named-templ-param "Named parameter" function for setting 1051 ///the map that indicates which nodes are processed. 1061 1052 template<class T> 1062 1053 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1209 1200 /// 1210 1201 /// The type of the map that indicates which nodes are reached. 1211 /// It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.1202 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1212 1203 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1213 1204 … … 1370 1361 /// The simplest way to execute the DFS algorithm is to use one of the 1371 1362 /// member functions called \ref run(Node) "run()".\n 1372 /// If you need more control on the execution, firstyou have to call1373 /// \ref init() , then you can add a source node with \ref addSource()1363 /// If you need better control on the execution, you have to call 1364 /// \ref init() first, then you can add a source node with \ref addSource() 1374 1365 /// and perform the actual computation with \ref start(). 1375 1366 /// This procedure can be repeated if there are nodes that have not … … 1584 1575 /// \brief Runs the algorithm to visit all nodes in the digraph. 1585 1576 1586 /// This method runs the %DFS algorithm in order to 1587 /// compute the %DFS path to each node. 1588 /// 1589 /// The algorithm computes 1590 /// - the %DFS tree (forest), 1591 /// - the distance of each node from the root(s) in the %DFS tree. 1577 /// This method runs the %DFS algorithm in order to visit all nodes 1578 /// in the digraph. 1592 1579 /// 1593 1580 /// \note <tt>d.run()</tt> is just a shortcut of the following code. … … 1621 1608 ///@{ 1622 1609 1623 /// \brief Checks if anode is reached from the root(s).1610 /// \brief Checks if the given node is reached from the root(s). 1624 1611 /// 1625 1612 /// Returns \c true if \c v is reached from the root(s).
Note: See TracChangeset
for help on using the changeset viewer.
