Changeset 764:684964884a2e in lemon for lemon/dfs.h
- Timestamp:
- 09/25/09 09:13:03 (14 years ago)
- Branch:
- default
- Parents:
- 763:f47b6c94577e (diff), 762:ece80147fb08 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Files:
-
- 2 edited
-
lemon/dfs.h (modified) (30 diffs)
-
lemon/dfs.h (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/dfs.h
r760 r764 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> > { … … 670 671 ///@{ 671 672 672 ///The DFS path to anode.673 674 ///Returns the DFS path to a node.673 ///The DFS path to the given node. 674 675 ///Returns the DFS path to the given node from the root(s). 675 676 /// 676 677 ///\warning \c t should be reached from the root(s). … … 680 681 Path path(Node t) const { return Path(*G, *_pred, t); } 681 682 682 ///The distance of anode from the root(s).683 684 ///Returns the distance of anode from the root(s).683 ///The distance of the given node from the root(s). 684 685 ///Returns the distance of the given node from the root(s). 685 686 /// 686 687 ///\warning If node \c v is not reached from the root(s), then … … 691 692 int dist(Node v) const { return (*_dist)[v]; } 692 693 693 ///Returns the 'previous arc' of the %DFS tree for anode.694 ///Returns the 'previous arc' of the %DFS tree for the given node. 694 695 695 696 ///This function returns the 'previous arc' of the %DFS tree for the … … 699 700 /// 700 701 ///The %DFS tree used here is equal to the %DFS tree used in 701 ///\ref predNode() .702 ///\ref predNode() and \ref predMap(). 702 703 /// 703 704 ///\pre Either \ref run(Node) "run()" or \ref init() … … 705 706 Arc predArc(Node v) const { return (*_pred)[v];} 706 707 707 ///Returns the 'previous node' of the %DFS tree .708 ///Returns the 'previous node' of the %DFS tree for the given node. 708 709 709 710 ///This function returns the 'previous node' of the %DFS 710 711 ///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 INVALID712 ///of a %DFS path from a root to \c v. It is \c INVALID 712 713 ///if \c v is not reached from the root(s) or if \c v is a root. 713 714 /// 714 715 ///The %DFS tree used here is equal to the %DFS tree used in 715 ///\ref predArc() .716 ///\ref predArc() and \ref predMap(). 716 717 /// 717 718 ///\pre Either \ref run(Node) "run()" or \ref init() … … 734 735 /// 735 736 ///Returns a const reference to the node map that stores the predecessor 736 ///arcs, which form the DFS tree .737 ///arcs, which form the DFS tree (forest). 737 738 /// 738 739 ///\pre Either \ref run(Node) "run()" or \ref init() … … 740 741 const PredMap &predMap() const { return *_pred;} 741 742 742 ///Checks if anode is reached from the root(s).743 ///Checks if the given node. node is reached from the root(s). 743 744 744 745 ///Returns \c true if \c v is reached from the root(s). … … 766 767 ///The type of the map that stores the predecessor 767 768 ///arcs of the %DFS paths. 768 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.769 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 769 770 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 770 771 ///Instantiates a PredMap. … … 781 782 782 783 ///The type of the map that indicates which nodes are processed. 783 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.784 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 784 785 ///By default it is a NullMap. 785 786 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; … … 801 802 802 803 ///The type of the map that indicates which nodes are reached. 803 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.804 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 804 805 typedef typename Digraph::template NodeMap<bool> ReachedMap; 805 806 ///Instantiates a ReachedMap. … … 816 817 817 818 ///The type of the map that stores the distances of the nodes. 818 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.819 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 819 820 typedef typename Digraph::template NodeMap<int> DistMap; 820 821 ///Instantiates a DistMap. … … 831 832 832 833 ///The type of the DFS paths. 833 ///It must meetthe \ref concepts::Path "Path" concept.834 ///It must conform to the \ref concepts::Path "Path" concept. 834 835 typedef lemon::Path<Digraph> Path; 835 836 }; … … 837 838 /// Default traits class used by DfsWizard 838 839 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. 840 /// Default traits class used by DfsWizard. 841 /// \tparam GR The type of the digraph. 845 842 template<class GR> 846 843 class DfsWizardBase : public DfsWizardDefaultTraits<GR> … … 870 867 /// Constructor. 871 868 872 /// This constructor does not require parameters, thereforeit initiates869 /// This constructor does not require parameters, it initiates 873 870 /// all of the attributes to \c 0. 874 871 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 900 897 typedef TR Base; 901 898 902 ///The type of the digraph the algorithm runs on.903 899 typedef typename TR::Digraph Digraph; 904 900 … … 908 904 typedef typename Digraph::OutArcIt OutArcIt; 909 905 910 ///\brief The type of the map that stores the predecessor911 ///arcs of the DFS paths.912 906 typedef typename TR::PredMap PredMap; 913 ///\brief The type of the map that stores the distances of the nodes.914 907 typedef typename TR::DistMap DistMap; 915 ///\brief The type of the map that indicates which nodes are reached.916 908 typedef typename TR::ReachedMap ReachedMap; 917 ///\brief The type of the map that indicates which nodes are processed.918 909 typedef typename TR::ProcessedMap ProcessedMap; 919 ///The type of the DFS paths920 910 typedef typename TR::Path Path; 921 911 … … 1000 990 SetPredMapBase(const TR &b) : TR(b) {} 1001 991 }; 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. 992 993 ///\brief \ref named-templ-param "Named parameter" for setting 994 ///the predecessor map. 995 /// 996 ///\ref named-templ-param "Named parameter" function for setting 997 ///the map that stores the predecessor arcs of the nodes. 1007 998 template<class T> 1008 999 DfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1018 1009 SetReachedMapBase(const TR &b) : TR(b) {} 1019 1010 }; 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. 1011 1012 ///\brief \ref named-templ-param "Named parameter" for setting 1013 ///the reached map. 1014 /// 1015 ///\ref named-templ-param "Named parameter" function for setting 1016 ///the map that indicates which nodes are reached. 1025 1017 template<class T> 1026 1018 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1036 1028 SetDistMapBase(const TR &b) : TR(b) {} 1037 1029 }; 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. 1030 1031 ///\brief \ref named-templ-param "Named parameter" for setting 1032 ///the distance map. 1033 /// 1034 ///\ref named-templ-param "Named parameter" function for setting 1035 ///the map that stores the distances of the nodes calculated 1036 ///by the algorithm. 1043 1037 template<class T> 1044 1038 DfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1054 1048 SetProcessedMapBase(const TR &b) : TR(b) {} 1055 1049 }; 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. 1050 1051 ///\brief \ref named-func-param "Named parameter" for setting 1052 ///the processed map. 1053 /// 1054 ///\ref named-templ-param "Named parameter" function for setting 1055 ///the map that indicates which nodes are processed. 1061 1056 template<class T> 1062 1057 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1209 1204 /// 1210 1205 /// The type of the map that indicates which nodes are reached. 1211 /// It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.1206 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1212 1207 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1213 1208 … … 1621 1616 ///@{ 1622 1617 1623 /// \brief Checks if anode is reached from the root(s).1618 /// \brief Checks if the given node is reached from the root(s). 1624 1619 /// 1625 1620 /// Returns \c true if \c v is reached from the root(s). -
lemon/dfs.h
r763 r764 413 413 ///The simplest way to execute the DFS algorithm is to use one of the 414 414 ///member functions called \ref run(Node) "run()".\n 415 ///If you need more control on the execution, firstyou have to call416 ///\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() 417 417 ///and perform the actual computation with \ref start(). 418 418 ///This procedure can be repeated if there are nodes that have not … … 1365 1365 /// The simplest way to execute the DFS algorithm is to use one of the 1366 1366 /// member functions called \ref run(Node) "run()".\n 1367 /// If you need more control on the execution, firstyou have to call1368 /// \ref init() , then you can add a source node with \ref addSource()1367 /// If you need better control on the execution, you have to call 1368 /// \ref init() first, then you can add a source node with \ref addSource() 1369 1369 /// and perform the actual computation with \ref start(). 1370 1370 /// This procedure can be repeated if there are nodes that have not
Note: See TracChangeset
for help on using the changeset viewer.
