Changeset 1159:7fdaa05a69a1 in lemon for lemon/dfs.h
- Timestamp:
- 09/13/12 11:56:19 (12 years ago)
- Branch:
- default
- Children:
- 1160:00f8d9f9920d, 1401:cd72eae05bdf
- Parents:
- 1153:4bb9e72e1a41 (diff), 1157:761fe0846f49 (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) (1 diff)
-
lemon/dfs.h (modified) (39 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/dfs.h
r1107 r1159 1194 1194 } 1195 1195 _Visitor& visitor; 1196 Constraints() {} 1196 1197 }; 1197 1198 }; -
lemon/dfs.h
r1125 r1159 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 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 meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 ///It must conform to 86 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 87 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 88 ///Instantiates a \c ReachedMap. … … 97 99 98 100 ///The type of the map that stores the distances of the nodes. 99 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.101 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 100 102 typedef typename Digraph::template NodeMap<int> DistMap; 101 103 ///Instantiates a \c DistMap. … … 121 123 ///\tparam GR The type of the digraph the algorithm runs on. 122 124 ///The default type is \ref ListDigraph. 125 ///\tparam TR The traits class that defines various types used by the 126 ///algorithm. By default, it is \ref DfsDefaultTraits 127 ///"DfsDefaultTraits<GR>". 128 ///In most cases, this parameter should not be set directly, 129 ///consider to use the named template parameters instead. 123 130 #ifdef DOXYGEN 124 131 template <typename GR, … … 225 232 ///\ref named-templ-param "Named parameter" for setting 226 233 ///\c PredMap type. 227 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.234 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 228 235 template <class T> 229 236 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > { … … 245 252 ///\ref named-templ-param "Named parameter" for setting 246 253 ///\c DistMap type. 247 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.254 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 248 255 template <class T> 249 256 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > { … … 265 272 ///\ref named-templ-param "Named parameter" for setting 266 273 ///\c ReachedMap type. 267 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 274 ///It must conform to 275 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 268 276 template <class T> 269 277 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { … … 285 293 ///\ref named-templ-param "Named parameter" for setting 286 294 ///\c ProcessedMap type. 287 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.295 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 288 296 template <class T> 289 297 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { … … 412 420 ///The simplest way to execute the DFS algorithm is to use one of the 413 421 ///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()422 ///If you need better control on the execution, you have to call 423 ///\ref init() first, then you can add a source node with \ref addSource() 416 424 ///and perform the actual computation with \ref start(). 417 425 ///This procedure can be repeated if there are nodes that have not … … 633 641 ///Runs the algorithm to visit all nodes in the digraph. 634 642 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. 643 ///This method runs the %DFS algorithm in order to visit all nodes 644 ///in the digraph. 641 645 /// 642 646 ///\note <tt>d.run()</tt> is just a shortcut of the following code. … … 670 674 ///@{ 671 675 672 ///The DFS path to anode.673 674 ///Returns the DFS path to a node.676 ///The DFS path to the given node. 677 678 ///Returns the DFS path to the given node from the root(s). 675 679 /// 676 680 ///\warning \c t should be reached from the root(s). … … 680 684 Path path(Node t) const { return Path(*G, *_pred, t); } 681 685 682 ///The distance of anode from the root(s).683 684 ///Returns the distance of anode from the root(s).686 ///The distance of the given node from the root(s). 687 688 ///Returns the distance of the given node from the root(s). 685 689 /// 686 690 ///\warning If node \c v is not reached from the root(s), then … … 691 695 int dist(Node v) const { return (*_dist)[v]; } 692 696 693 ///Returns the 'previous arc' of the %DFS tree for anode.697 ///Returns the 'previous arc' of the %DFS tree for the given node. 694 698 695 699 ///This function returns the 'previous arc' of the %DFS tree for the … … 699 703 /// 700 704 ///The %DFS tree used here is equal to the %DFS tree used in 701 ///\ref predNode() .705 ///\ref predNode() and \ref predMap(). 702 706 /// 703 707 ///\pre Either \ref run(Node) "run()" or \ref init() … … 705 709 Arc predArc(Node v) const { return (*_pred)[v];} 706 710 707 ///Returns the 'previous node' of the %DFS tree .711 ///Returns the 'previous node' of the %DFS tree for the given node. 708 712 709 713 ///This function returns the 'previous node' of the %DFS 710 714 ///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 INVALID715 ///of a %DFS path from a root to \c v. It is \c INVALID 712 716 ///if \c v is not reached from the root(s) or if \c v is a root. 713 717 /// 714 718 ///The %DFS tree used here is equal to the %DFS tree used in 715 ///\ref predArc() .719 ///\ref predArc() and \ref predMap(). 716 720 /// 717 721 ///\pre Either \ref run(Node) "run()" or \ref init() … … 734 738 /// 735 739 ///Returns a const reference to the node map that stores the predecessor 736 ///arcs, which form the DFS tree .740 ///arcs, which form the DFS tree (forest). 737 741 /// 738 742 ///\pre Either \ref run(Node) "run()" or \ref init() … … 740 744 const PredMap &predMap() const { return *_pred;} 741 745 742 ///Checks if anode is reached from the root(s).746 ///Checks if the given node. node is reached from the root(s). 743 747 744 748 ///Returns \c true if \c v is reached from the root(s). … … 766 770 ///The type of the map that stores the predecessor 767 771 ///arcs of the %DFS paths. 768 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.772 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 769 773 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 770 774 ///Instantiates a PredMap. … … 781 785 782 786 ///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.787 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 788 ///By default, it is a NullMap. 785 789 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 786 790 ///Instantiates a ProcessedMap. … … 801 805 802 806 ///The type of the map that indicates which nodes are reached. 803 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 807 ///It must conform to 808 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 804 809 typedef typename Digraph::template NodeMap<bool> ReachedMap; 805 810 ///Instantiates a ReachedMap. … … 816 821 817 822 ///The type of the map that stores the distances of the nodes. 818 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.823 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 819 824 typedef typename Digraph::template NodeMap<int> DistMap; 820 825 ///Instantiates a DistMap. … … 831 836 832 837 ///The type of the DFS paths. 833 ///It must meetthe \ref concepts::Path "Path" concept.838 ///It must conform to the \ref concepts::Path "Path" concept. 834 839 typedef lemon::Path<Digraph> Path; 835 840 }; … … 837 842 /// Default traits class used by DfsWizard 838 843 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. 844 /// Default traits class used by DfsWizard. 845 /// \tparam GR The type of the digraph. 845 846 template<class GR> 846 847 class DfsWizardBase : public DfsWizardDefaultTraits<GR> … … 870 871 /// Constructor. 871 872 872 /// This constructor does not require parameters, thereforeit initiates873 /// This constructor does not require parameters, it initiates 873 874 /// all of the attributes to \c 0. 874 875 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 895 896 /// This class should only be used through the \ref dfs() function, 896 897 /// which makes it easier to use the algorithm. 898 /// 899 /// \tparam TR The traits class that defines various types used by the 900 /// algorithm. 897 901 template<class TR> 898 902 class DfsWizard : public TR … … 900 904 typedef TR Base; 901 905 902 ///The type of the digraph the algorithm runs on.903 906 typedef typename TR::Digraph Digraph; 904 907 … … 908 911 typedef typename Digraph::OutArcIt OutArcIt; 909 912 910 ///\brief The type of the map that stores the predecessor911 ///arcs of the DFS paths.912 913 typedef typename TR::PredMap PredMap; 913 ///\brief The type of the map that stores the distances of the nodes.914 914 typedef typename TR::DistMap DistMap; 915 ///\brief The type of the map that indicates which nodes are reached.916 915 typedef typename TR::ReachedMap ReachedMap; 917 ///\brief The type of the map that indicates which nodes are processed.918 916 typedef typename TR::ProcessedMap ProcessedMap; 919 ///The type of the DFS paths920 917 typedef typename TR::Path Path; 921 918 … … 987 984 ///Runs DFS algorithm to visit all nodes in the digraph. 988 985 989 ///This method runs DFS algorithm in order to compute990 /// the DFS path to each node.986 ///This method runs DFS algorithm in order to visit all nodes 987 ///in the digraph. 991 988 void run() 992 989 { … … 1000 997 SetPredMapBase(const TR &b) : TR(b) {} 1001 998 }; 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. 999 1000 ///\brief \ref named-templ-param "Named parameter" for setting 1001 ///the predecessor map. 1002 /// 1003 ///\ref named-templ-param "Named parameter" function for setting 1004 ///the map that stores the predecessor arcs of the nodes. 1007 1005 template<class T> 1008 1006 DfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1018 1016 SetReachedMapBase(const TR &b) : TR(b) {} 1019 1017 }; 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. 1018 1019 ///\brief \ref named-templ-param "Named parameter" for setting 1020 ///the reached map. 1021 /// 1022 ///\ref named-templ-param "Named parameter" function for setting 1023 ///the map that indicates which nodes are reached. 1025 1024 template<class T> 1026 1025 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1036 1035 SetDistMapBase(const TR &b) : TR(b) {} 1037 1036 }; 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. 1037 1038 ///\brief \ref named-templ-param "Named parameter" for setting 1039 ///the distance map. 1040 /// 1041 ///\ref named-templ-param "Named parameter" function for setting 1042 ///the map that stores the distances of the nodes calculated 1043 ///by the algorithm. 1043 1044 template<class T> 1044 1045 DfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1054 1055 SetProcessedMapBase(const TR &b) : TR(b) {} 1055 1056 }; 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. 1057 1058 ///\brief \ref named-func-param "Named parameter" for setting 1059 ///the processed map. 1060 /// 1061 ///\ref named-templ-param "Named parameter" function for setting 1062 ///the map that indicates which nodes are processed. 1061 1063 template<class T> 1062 1064 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1210 1212 /// 1211 1213 /// The type of the map that indicates which nodes are reached. 1212 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1214 /// It must conform to the 1215 /// \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1213 1216 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1214 1217 … … 1248 1251 /// does not observe the DFS events. If you want to observe the DFS 1249 1252 /// events, you should implement your own visitor class. 1250 /// \tparam TR T raits class to set various datatypes used by the1251 /// algorithm. The default traits class is1252 /// \ref DfsVisitDefaultTraits"DfsVisitDefaultTraits<GR>".1253 /// See \ref DfsVisitDefaultTraits for the documentation of1254 /// a DFS visit traits class.1253 /// \tparam TR The traits class that defines various types used by the 1254 /// algorithm. By default, it is \ref DfsVisitDefaultTraits 1255 /// "DfsVisitDefaultTraits<GR>". 1256 /// In most cases, this parameter should not be set directly, 1257 /// consider to use the named template parameters instead. 1255 1258 #ifdef DOXYGEN 1256 1259 template <typename GR, typename VS, typename TR> … … 1371 1374 /// The simplest way to execute the DFS algorithm is to use one of the 1372 1375 /// member functions called \ref run(Node) "run()".\n 1373 /// If you need more control on the execution, firstyou have to call1374 /// \ref init() , then you can add a source node with \ref addSource()1376 /// If you need better control on the execution, you have to call 1377 /// \ref init() first, then you can add a source node with \ref addSource() 1375 1378 /// and perform the actual computation with \ref start(). 1376 1379 /// This procedure can be repeated if there are nodes that have not … … 1585 1588 /// \brief Runs the algorithm to visit all nodes in the digraph. 1586 1589 1587 /// This method runs the %DFS algorithm in order to 1588 /// compute the %DFS path to each node. 1589 /// 1590 /// The algorithm computes 1591 /// - the %DFS tree (forest), 1592 /// - the distance of each node from the root(s) in the %DFS tree. 1590 /// This method runs the %DFS algorithm in order to visit all nodes 1591 /// in the digraph. 1593 1592 /// 1594 1593 /// \note <tt>d.run()</tt> is just a shortcut of the following code. … … 1622 1621 ///@{ 1623 1622 1624 /// \brief Checks if anode is reached from the root(s).1623 /// \brief Checks if the given node is reached from the root(s). 1625 1624 /// 1626 1625 /// Returns \c true if \c v is reached from the root(s).
Note: See TracChangeset
for help on using the changeset viewer.
