Changeset 954:be7dd3a8d6a3 in lemon-1.2 for lemon/bfs.h
- Timestamp:
- 01/20/12 19:20:02 (12 years ago)
- Branch:
- 1.2
- Parents:
- 952:0976225b5cae (diff), 953:b873350e6258 (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/bfs.h (modified) (1 diff)
-
lemon/bfs.h (modified) (39 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r877 r954 1252 1252 } 1253 1253 _Visitor& visitor; 1254 Constraints() {} 1254 1255 }; 1255 1256 }; -
lemon/bfs.h
r953 r954 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 shortest 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 BfsDefaultTraits 127 ///"BfsDefaultTraits<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, … … 226 233 ///\ref named-templ-param "Named parameter" for setting 227 234 ///\c PredMap type. 228 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.235 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 229 236 template <class T> 230 237 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 246 253 ///\ref named-templ-param "Named parameter" for setting 247 254 ///\c DistMap type. 248 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.255 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 249 256 template <class T> 250 257 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 266 273 ///\ref named-templ-param "Named parameter" for setting 267 274 ///\c ReachedMap type. 268 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 275 ///It must conform to 276 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 269 277 template <class T> 270 278 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 286 294 ///\ref named-templ-param "Named parameter" for setting 287 295 ///\c ProcessedMap type. 288 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.296 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 289 297 template <class T> 290 298 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 414 422 ///The simplest way to execute the BFS algorithm is to use one of the 415 423 ///member functions called \ref run(Node) "run()".\n 416 ///If you need more control on the execution, firstyou have to call417 ///\ref init() , then you can add several source nodes with424 ///If you need better control on the execution, you have to call 425 ///\ref init() first, then you can add several source nodes with 418 426 ///\ref addSource(). Finally the actual path computation can be 419 427 ///performed with one of the \ref start() functions. … … 701 709 ///Runs the algorithm to visit all nodes in the digraph. 702 710 703 ///This method runs the %BFS algorithm in order to 704 ///compute the shortest path to each node. 705 /// 706 ///The algorithm computes 707 ///- the shortest path tree (forest), 708 ///- the distance of each node from the root(s). 711 ///This method runs the %BFS algorithm in order to visit all nodes 712 ///in the digraph. 709 713 /// 710 714 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 738 742 ///@{ 739 743 740 ///The shortest path to anode.741 742 ///Returns the shortest path to a node.744 ///The shortest path to the given node. 745 746 ///Returns the shortest path to the given node from the root(s). 743 747 /// 744 748 ///\warning \c t should be reached from the root(s). … … 748 752 Path path(Node t) const { return Path(*G, *_pred, t); } 749 753 750 ///The distance of anode from the root(s).751 752 ///Returns the distance of anode from the root(s).754 ///The distance of the given node from the root(s). 755 756 ///Returns the distance of the given node from the root(s). 753 757 /// 754 758 ///\warning If node \c v is not reached from the root(s), then … … 759 763 int dist(Node v) const { return (*_dist)[v]; } 760 764 761 ///Returns the 'previous arc' of the shortest path tree for a node. 762 765 ///\brief Returns the 'previous arc' of the shortest path tree for 766 ///the given node. 767 /// 763 768 ///This function returns the 'previous arc' of the shortest path 764 769 ///tree for the node \c v, i.e. it returns the last arc of a … … 767 772 /// 768 773 ///The shortest path tree used here is equal to the shortest path 769 ///tree used in \ref predNode() .774 ///tree used in \ref predNode() and \ref predMap(). 770 775 /// 771 776 ///\pre Either \ref run(Node) "run()" or \ref init() … … 773 778 Arc predArc(Node v) const { return (*_pred)[v];} 774 779 775 ///Returns the 'previous node' of the shortest path tree for a node. 776 780 ///\brief Returns the 'previous node' of the shortest path tree for 781 ///the given node. 782 /// 777 783 ///This function returns the 'previous node' of the shortest path 778 784 ///tree for the node \c v, i.e. it returns the last but one node 779 /// froma shortest path from a root to \c v. It is \c INVALID785 ///of a shortest path from a root to \c v. It is \c INVALID 780 786 ///if \c v is not reached from the root(s) or if \c v is a root. 781 787 /// 782 788 ///The shortest path tree used here is equal to the shortest path 783 ///tree used in \ref predArc() .789 ///tree used in \ref predArc() and \ref predMap(). 784 790 /// 785 791 ///\pre Either \ref run(Node) "run()" or \ref init() … … 802 808 /// 803 809 ///Returns a const reference to the node map that stores the predecessor 804 ///arcs, which form the shortest path tree .810 ///arcs, which form the shortest path tree (forest). 805 811 /// 806 812 ///\pre Either \ref run(Node) "run()" or \ref init() … … 808 814 const PredMap &predMap() const { return *_pred;} 809 815 810 ///Checks if anode is reached from the root(s).816 ///Checks if the given node is reached from the root(s). 811 817 812 818 ///Returns \c true if \c v is reached from the root(s). … … 834 840 ///The type of the map that stores the predecessor 835 841 ///arcs of the shortest paths. 836 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.842 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 837 843 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 838 844 ///Instantiates a PredMap. … … 849 855 850 856 ///The type of the map that indicates which nodes are processed. 851 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.852 ///By default it is a NullMap.857 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 858 ///By default, it is a NullMap. 853 859 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 854 860 ///Instantiates a ProcessedMap. … … 869 875 870 876 ///The type of the map that indicates which nodes are reached. 871 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 877 ///It must conform to 878 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 872 879 typedef typename Digraph::template NodeMap<bool> ReachedMap; 873 880 ///Instantiates a ReachedMap. … … 884 891 885 892 ///The type of the map that stores the distances of the nodes. 886 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.893 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 887 894 typedef typename Digraph::template NodeMap<int> DistMap; 888 895 ///Instantiates a DistMap. … … 899 906 900 907 ///The type of the shortest paths. 901 ///It must meetthe \ref concepts::Path "Path" concept.908 ///It must conform to the \ref concepts::Path "Path" concept. 902 909 typedef lemon::Path<Digraph> Path; 903 910 }; … … 905 912 /// Default traits class used by BfsWizard 906 913 907 /// To make it easier to use Bfs algorithm 908 /// we have created a wizard class. 909 /// This \ref BfsWizard class needs default traits, 910 /// as well as the \ref Bfs class. 911 /// The \ref BfsWizardBase is a class to be the default traits of the 912 /// \ref BfsWizard class. 914 /// Default traits class used by BfsWizard. 915 /// \tparam GR The type of the digraph. 913 916 template<class GR> 914 917 class BfsWizardBase : public BfsWizardDefaultTraits<GR> … … 938 941 /// Constructor. 939 942 940 /// This constructor does not require parameters, thereforeit initiates943 /// This constructor does not require parameters, it initiates 941 944 /// all of the attributes to \c 0. 942 945 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 963 966 /// This class should only be used through the \ref bfs() function, 964 967 /// which makes it easier to use the algorithm. 968 /// 969 /// \tparam TR The traits class that defines various types used by the 970 /// algorithm. 965 971 template<class TR> 966 972 class BfsWizard : public TR … … 968 974 typedef TR Base; 969 975 970 ///The type of the digraph the algorithm runs on.971 976 typedef typename TR::Digraph Digraph; 972 977 … … 976 981 typedef typename Digraph::OutArcIt OutArcIt; 977 982 978 ///\brief The type of the map that stores the predecessor979 ///arcs of the shortest paths.980 983 typedef typename TR::PredMap PredMap; 981 ///\brief The type of the map that stores the distances of the nodes.982 984 typedef typename TR::DistMap DistMap; 983 ///\brief The type of the map that indicates which nodes are reached.984 985 typedef typename TR::ReachedMap ReachedMap; 985 ///\brief The type of the map that indicates which nodes are processed.986 986 typedef typename TR::ProcessedMap ProcessedMap; 987 ///The type of the shortest paths988 987 typedef typename TR::Path Path; 989 988 … … 1055 1054 ///Runs BFS algorithm to visit all nodes in the digraph. 1056 1055 1057 ///This method runs BFS algorithm in order to compute1058 /// the shortest path to each node.1056 ///This method runs BFS algorithm in order to visit all nodes 1057 ///in the digraph. 1059 1058 void run() 1060 1059 { … … 1068 1067 SetPredMapBase(const TR &b) : TR(b) {} 1069 1068 }; 1070 ///\brief \ref named-func-param "Named parameter" 1071 ///for setting PredMap object. 1072 /// 1073 ///\ref named-func-param "Named parameter" 1074 ///for setting PredMap object. 1069 1070 ///\brief \ref named-templ-param "Named parameter" for setting 1071 ///the predecessor map. 1072 /// 1073 ///\ref named-templ-param "Named parameter" function for setting 1074 ///the map that stores the predecessor arcs of the nodes. 1075 1075 template<class T> 1076 1076 BfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1086 1086 SetReachedMapBase(const TR &b) : TR(b) {} 1087 1087 }; 1088 ///\brief \ref named-func-param "Named parameter" 1089 ///for setting ReachedMap object. 1090 /// 1091 /// \ref named-func-param "Named parameter" 1092 ///for setting ReachedMap object. 1088 1089 ///\brief \ref named-templ-param "Named parameter" for setting 1090 ///the reached map. 1091 /// 1092 ///\ref named-templ-param "Named parameter" function for setting 1093 ///the map that indicates which nodes are reached. 1093 1094 template<class T> 1094 1095 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1104 1105 SetDistMapBase(const TR &b) : TR(b) {} 1105 1106 }; 1106 ///\brief \ref named-func-param "Named parameter" 1107 ///for setting DistMap object. 1108 /// 1109 /// \ref named-func-param "Named parameter" 1110 ///for setting DistMap object. 1107 1108 ///\brief \ref named-templ-param "Named parameter" for setting 1109 ///the distance map. 1110 /// 1111 ///\ref named-templ-param "Named parameter" function for setting 1112 ///the map that stores the distances of the nodes calculated 1113 ///by the algorithm. 1111 1114 template<class T> 1112 1115 BfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1122 1125 SetProcessedMapBase(const TR &b) : TR(b) {} 1123 1126 }; 1124 ///\brief \ref named-func-param "Named parameter" 1125 ///for setting ProcessedMap object. 1126 /// 1127 /// \ref named-func-param "Named parameter" 1128 ///for setting ProcessedMap object. 1127 1128 ///\brief \ref named-func-param "Named parameter" for setting 1129 ///the processed map. 1130 /// 1131 ///\ref named-templ-param "Named parameter" function for setting 1132 ///the map that indicates which nodes are processed. 1129 1133 template<class T> 1130 1134 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1266 1270 /// 1267 1271 /// The type of the map that indicates which nodes are reached. 1268 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1272 /// It must conform to 1273 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1269 1274 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1270 1275 … … 1304 1309 /// does not observe the BFS events. If you want to observe the BFS 1305 1310 /// events, you should implement your own visitor class. 1306 /// \tparam TR T raits class to set various datatypes used by the1307 /// algorithm. The default traits class is1308 /// \ref BfsVisitDefaultTraits"BfsVisitDefaultTraits<GR>".1309 /// See \ref BfsVisitDefaultTraits for the documentation of1310 /// a BFS visit traits class.1311 /// \tparam TR The traits class that defines various types used by the 1312 /// algorithm. By default, it is \ref BfsVisitDefaultTraits 1313 /// "BfsVisitDefaultTraits<GR>". 1314 /// In most cases, this parameter should not be set directly, 1315 /// consider to use the named template parameters instead. 1311 1316 #ifdef DOXYGEN 1312 1317 template <typename GR, typename VS, typename TR> … … 1427 1432 /// The simplest way to execute the BFS algorithm is to use one of the 1428 1433 /// member functions called \ref run(Node) "run()".\n 1429 /// If you need more control on the execution, firstyou have to call1430 /// \ref init() , then you can add several source nodes with1434 /// If you need better control on the execution, you have to call 1435 /// \ref init() first, then you can add several source nodes with 1431 1436 /// \ref addSource(). Finally the actual path computation can be 1432 1437 /// performed with one of the \ref start() functions. … … 1700 1705 /// \brief Runs the algorithm to visit all nodes in the digraph. 1701 1706 /// 1702 /// This method runs the %BFS algorithm in order to 1703 /// compute the shortest path to each node. 1704 /// 1705 /// The algorithm computes 1706 /// - the shortest path tree (forest), 1707 /// - the distance of each node from the root(s). 1707 /// This method runs the %BFS algorithm in order to visit all nodes 1708 /// in the digraph. 1708 1709 /// 1709 1710 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 1737 1738 ///@{ 1738 1739 1739 /// \brief Checks if anode is reached from the root(s).1740 /// \brief Checks if the given node is reached from the root(s). 1740 1741 /// 1741 1742 /// Returns \c true if \c v is reached from the root(s).
Note: See TracChangeset
for help on using the changeset viewer.
