Changes in lemon/bfs.h [764:684964884a2e:463:88ed40ad0d4f] in lemon
- File:
-
- 1 edited
-
lemon/bfs.h (modified) (39 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r764 r463 48 48 ///The type of the map that stores the predecessor 49 49 ///arcs of the shortest paths. 50 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 51 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 ///Instantiates a \cPredMap.53 54 ///This function instantiates a \refPredMap.52 ///Instantiates a PredMap. 53 54 ///This function instantiates a PredMap. 55 55 ///\param g is the digraph, to which we would like to define the 56 /// \refPredMap.56 ///PredMap. 57 57 static PredMap *createPredMap(const Digraph &g) 58 58 { … … 63 63 64 64 ///The type of the map that indicates which nodes are processed. 65 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 66 ///By default it is a NullMap. 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 67 66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 68 ///Instantiates a \cProcessedMap.69 70 ///This function instantiates a \refProcessedMap.67 ///Instantiates a ProcessedMap. 68 69 ///This function instantiates a ProcessedMap. 71 70 ///\param g is the digraph, to which 72 ///we would like to define the \refProcessedMap71 ///we would like to define the ProcessedMap 73 72 #ifdef DOXYGEN 74 73 static ProcessedMap *createProcessedMap(const Digraph &g) … … 83 82 84 83 ///The type of the map that indicates which nodes are reached. 85 ///It must conform tothe \ref concepts::ReadWriteMap "ReadWriteMap" concept.84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 86 85 typedef typename Digraph::template NodeMap<bool> ReachedMap; 87 ///Instantiates a \cReachedMap.88 89 ///This function instantiates a \refReachedMap.86 ///Instantiates a ReachedMap. 87 88 ///This function instantiates a ReachedMap. 90 89 ///\param g is the digraph, to which 91 ///we would like to define the \refReachedMap.90 ///we would like to define the ReachedMap. 92 91 static ReachedMap *createReachedMap(const Digraph &g) 93 92 { … … 98 97 99 98 ///The type of the map that stores the distances of the nodes. 100 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.99 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 101 100 typedef typename Digraph::template NodeMap<int> DistMap; 102 ///Instantiates a \cDistMap.103 104 ///This function instantiates a \refDistMap.101 ///Instantiates a DistMap. 102 103 ///This function instantiates a DistMap. 105 104 ///\param g is the digraph, to which we would like to define the 106 /// \refDistMap.105 ///DistMap. 107 106 static DistMap *createDistMap(const Digraph &g) 108 107 { … … 223 222 }; 224 223 ///\brief \ref named-templ-param "Named parameter" for setting 225 /// \cPredMap type.224 ///PredMap type. 226 225 /// 227 226 ///\ref named-templ-param "Named parameter" for setting 228 /// \cPredMap type.229 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.227 ///PredMap type. 228 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 230 229 template <class T> 231 230 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 243 242 }; 244 243 ///\brief \ref named-templ-param "Named parameter" for setting 245 /// \cDistMap type.244 ///DistMap type. 246 245 /// 247 246 ///\ref named-templ-param "Named parameter" for setting 248 /// \cDistMap type.249 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.247 ///DistMap type. 248 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 250 249 template <class T> 251 250 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 263 262 }; 264 263 ///\brief \ref named-templ-param "Named parameter" for setting 265 /// \cReachedMap type.264 ///ReachedMap type. 266 265 /// 267 266 ///\ref named-templ-param "Named parameter" for setting 268 /// \cReachedMap type.269 ///It must conform tothe \ref concepts::ReadWriteMap "ReadWriteMap" concept.267 ///ReachedMap type. 268 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 270 269 template <class T> 271 270 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 283 282 }; 284 283 ///\brief \ref named-templ-param "Named parameter" for setting 285 /// \cProcessedMap type.284 ///ProcessedMap type. 286 285 /// 287 286 ///\ref named-templ-param "Named parameter" for setting 288 /// \cProcessedMap type.289 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.287 ///ProcessedMap type. 288 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 290 289 template <class T> 291 290 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 302 301 }; 303 302 ///\brief \ref named-templ-param "Named parameter" for setting 304 /// \cProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.303 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 305 304 /// 306 305 ///\ref named-templ-param "Named parameter" for setting 307 /// \cProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.306 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 308 307 ///If you don't set it explicitly, it will be automatically allocated. 309 308 struct SetStandardProcessedMap : … … 415 414 ///The simplest way to execute the BFS algorithm is to use one of the 416 415 ///member functions called \ref run(Node) "run()".\n 417 ///If you need better control on the execution,you have to call418 ///\ref init() first, then you can add several source nodes with416 ///If you need more control on the execution, first you have to call 417 ///\ref init(), then you can add several source nodes with 419 418 ///\ref addSource(). Finally the actual path computation can be 420 419 ///performed with one of the \ref start() functions. … … 739 738 ///@{ 740 739 741 ///The shortest path to the givennode.742 743 ///Returns the shortest path to the given node from the root(s).740 ///The shortest path to a node. 741 742 ///Returns the shortest path to a node. 744 743 /// 745 744 ///\warning \c t should be reached from the root(s). … … 749 748 Path path(Node t) const { return Path(*G, *_pred, t); } 750 749 751 ///The distance of the givennode from the root(s).752 753 ///Returns the distance of the givennode from the root(s).750 ///The distance of a node from the root(s). 751 752 ///Returns the distance of a node from the root(s). 754 753 /// 755 754 ///\warning If node \c v is not reached from the root(s), then … … 760 759 int dist(Node v) const { return (*_dist)[v]; } 761 760 762 ///\brief Returns the 'previous arc' of the shortest path tree for 763 ///the given node. 764 /// 761 ///Returns the 'previous arc' of the shortest path tree for a node. 762 765 763 ///This function returns the 'previous arc' of the shortest path 766 764 ///tree for the node \c v, i.e. it returns the last arc of a … … 769 767 /// 770 768 ///The shortest path tree used here is equal to the shortest path 771 ///tree used in \ref predNode() and \ref predMap().769 ///tree used in \ref predNode(). 772 770 /// 773 771 ///\pre Either \ref run(Node) "run()" or \ref init() … … 775 773 Arc predArc(Node v) const { return (*_pred)[v];} 776 774 777 ///\brief Returns the 'previous node' of the shortest path tree for 778 ///the given node. 779 /// 775 ///Returns the 'previous node' of the shortest path tree for a node. 776 780 777 ///This function returns the 'previous node' of the shortest path 781 778 ///tree for the node \c v, i.e. it returns the last but one node 782 /// ofa shortest path from a root to \c v. It is \c INVALID779 ///from a shortest path from a root to \c v. It is \c INVALID 783 780 ///if \c v is not reached from the root(s) or if \c v is a root. 784 781 /// 785 782 ///The shortest path tree used here is equal to the shortest path 786 ///tree used in \ref predArc() and \ref predMap().783 ///tree used in \ref predArc(). 787 784 /// 788 785 ///\pre Either \ref run(Node) "run()" or \ref init() … … 805 802 /// 806 803 ///Returns a const reference to the node map that stores the predecessor 807 ///arcs, which form the shortest path tree (forest).804 ///arcs, which form the shortest path tree. 808 805 /// 809 806 ///\pre Either \ref run(Node) "run()" or \ref init() … … 811 808 const PredMap &predMap() const { return *_pred;} 812 809 813 ///Checks if the givennode is reached from the root(s).810 ///Checks if a node is reached from the root(s). 814 811 815 812 ///Returns \c true if \c v is reached from the root(s). … … 837 834 ///The type of the map that stores the predecessor 838 835 ///arcs of the shortest paths. 839 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.836 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 840 837 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 841 838 ///Instantiates a PredMap. … … 852 849 853 850 ///The type of the map that indicates which nodes are processed. 854 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.851 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 855 852 ///By default it is a NullMap. 856 853 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; … … 872 869 873 870 ///The type of the map that indicates which nodes are reached. 874 ///It must conform tothe \ref concepts::ReadWriteMap "ReadWriteMap" concept.871 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 875 872 typedef typename Digraph::template NodeMap<bool> ReachedMap; 876 873 ///Instantiates a ReachedMap. … … 887 884 888 885 ///The type of the map that stores the distances of the nodes. 889 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.886 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 890 887 typedef typename Digraph::template NodeMap<int> DistMap; 891 888 ///Instantiates a DistMap. … … 902 899 903 900 ///The type of the shortest paths. 904 ///It must conform tothe \ref concepts::Path "Path" concept.901 ///It must meet the \ref concepts::Path "Path" concept. 905 902 typedef lemon::Path<Digraph> Path; 906 903 }; … … 908 905 /// Default traits class used by BfsWizard 909 906 910 /// Default traits class used by BfsWizard. 911 /// \tparam GR The type of the digraph. 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. 912 913 template<class GR> 913 914 class BfsWizardBase : public BfsWizardDefaultTraits<GR> … … 937 938 /// Constructor. 938 939 939 /// This constructor does not require parameters, it initiates940 /// This constructor does not require parameters, therefore it initiates 940 941 /// all of the attributes to \c 0. 941 942 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 967 968 typedef TR Base; 968 969 970 ///The type of the digraph the algorithm runs on. 969 971 typedef typename TR::Digraph Digraph; 970 972 … … 974 976 typedef typename Digraph::OutArcIt OutArcIt; 975 977 978 ///\brief The type of the map that stores the predecessor 979 ///arcs of the shortest paths. 976 980 typedef typename TR::PredMap PredMap; 981 ///\brief The type of the map that stores the distances of the nodes. 977 982 typedef typename TR::DistMap DistMap; 983 ///\brief The type of the map that indicates which nodes are reached. 978 984 typedef typename TR::ReachedMap ReachedMap; 985 ///\brief The type of the map that indicates which nodes are processed. 979 986 typedef typename TR::ProcessedMap ProcessedMap; 987 ///The type of the shortest paths 980 988 typedef typename TR::Path Path; 981 989 … … 1060 1068 SetPredMapBase(const TR &b) : TR(b) {} 1061 1069 }; 1062 1063 ///\brief \ref named-templ-param "Named parameter" for setting 1064 ///the predecessor map. 1065 /// 1066 ///\ref named-templ-param "Named parameter" function for setting 1067 ///the map that stores the predecessor arcs of the nodes. 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. 1068 1075 template<class T> 1069 1076 BfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1079 1086 SetReachedMapBase(const TR &b) : TR(b) {} 1080 1087 }; 1081 1082 ///\brief \ref named-templ-param "Named parameter" for setting 1083 ///the reached map. 1084 /// 1085 ///\ref named-templ-param "Named parameter" function for setting 1086 ///the map that indicates which nodes are reached. 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. 1087 1093 template<class T> 1088 1094 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1098 1104 SetDistMapBase(const TR &b) : TR(b) {} 1099 1105 }; 1100 1101 ///\brief \ref named-templ-param "Named parameter" for setting 1102 ///the distance map. 1103 /// 1104 ///\ref named-templ-param "Named parameter" function for setting 1105 ///the map that stores the distances of the nodes calculated 1106 ///by the algorithm. 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 1111 template<class T> 1108 1112 BfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1118 1122 SetProcessedMapBase(const TR &b) : TR(b) {} 1119 1123 }; 1120 1121 ///\brief \ref named-func-param "Named parameter" for setting 1122 ///the processed map. 1123 /// 1124 ///\ref named-templ-param "Named parameter" function for setting 1125 ///the map that indicates which nodes are processed. 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. 1126 1129 template<class T> 1127 1130 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1192 1195 /// This class defines the interface of the BfsVisit events, and 1193 1196 /// it could be the base of a real visitor class. 1194 template <typename GR>1197 template <typename _Digraph> 1195 1198 struct BfsVisitor { 1196 typedef GRDigraph;1199 typedef _Digraph Digraph; 1197 1200 typedef typename Digraph::Arc Arc; 1198 1201 typedef typename Digraph::Node Node; … … 1222 1225 }; 1223 1226 #else 1224 template <typename GR>1227 template <typename _Digraph> 1225 1228 struct BfsVisitor { 1226 typedef GRDigraph;1229 typedef _Digraph Digraph; 1227 1230 typedef typename Digraph::Arc Arc; 1228 1231 typedef typename Digraph::Node Node; … … 1252 1255 /// 1253 1256 /// Default traits class of BfsVisit class. 1254 /// \tparam GRThe type of the digraph the algorithm runs on.1255 template<class GR>1257 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1258 template<class _Digraph> 1256 1259 struct BfsVisitDefaultTraits { 1257 1260 1258 1261 /// \brief The type of the digraph the algorithm runs on. 1259 typedef GRDigraph;1262 typedef _Digraph Digraph; 1260 1263 1261 1264 /// \brief The type of the map that indicates which nodes are reached. 1262 1265 /// 1263 1266 /// The type of the map that indicates which nodes are reached. 1264 /// It must conform tothe \ref concepts::ReadWriteMap "ReadWriteMap" concept.1267 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1265 1268 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1266 1269 … … 1278 1281 /// \ingroup search 1279 1282 /// 1280 /// \brief BFS algorithm class with visitor interface.1283 /// \brief %BFS algorithm class with visitor interface. 1281 1284 /// 1282 /// This class provides an efficient implementation of the BFS algorithm1285 /// This class provides an efficient implementation of the %BFS algorithm 1283 1286 /// with visitor interface. 1284 1287 /// 1285 /// The BfsVisit class provides an alternative interface to the Bfs1288 /// The %BfsVisit class provides an alternative interface to the Bfs 1286 1289 /// class. It works with callback mechanism, the BfsVisit object calls 1287 1290 /// the member functions of the \c Visitor class on every BFS event. … … 1292 1295 /// instead. 1293 1296 /// 1294 /// \tparam GRThe type of the digraph the algorithm runs on.1295 /// The default type is \ref ListDigraph.1296 /// The value of GR is not used directly by \ref BfsVisit,1297 /// it is only passed to \ref BfsVisitDefaultTraits.1298 /// \tparam VSThe Visitor type that is used by the algorithm.1299 /// \ref BfsVisitor "BfsVisitor< GR>" is an empty visitor, which1297 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1298 /// The default value is 1299 /// \ref ListDigraph. The value of _Digraph is not used directly by 1300 /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits. 1301 /// \tparam _Visitor The Visitor type that is used by the algorithm. 1302 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which 1300 1303 /// does not observe the BFS events. If you want to observe the BFS 1301 1304 /// events, you should implement your own visitor class. 1302 /// \tparam TRTraits class to set various data types used by the1305 /// \tparam _Traits Traits class to set various data types used by the 1303 1306 /// algorithm. The default traits class is 1304 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits< GR>".1307 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>". 1305 1308 /// See \ref BfsVisitDefaultTraits for the documentation of 1306 1309 /// a BFS visit traits class. 1307 1310 #ifdef DOXYGEN 1308 template <typename GR, typename VS, typename TR>1311 template <typename _Digraph, typename _Visitor, typename _Traits> 1309 1312 #else 1310 template <typename GR= ListDigraph,1311 typename VS = BfsVisitor<GR>,1312 typename TR = BfsVisitDefaultTraits<GR> >1313 template <typename _Digraph = ListDigraph, 1314 typename _Visitor = BfsVisitor<_Digraph>, 1315 typename _Traits = BfsVisitDefaultTraits<_Digraph> > 1313 1316 #endif 1314 1317 class BfsVisit { … … 1316 1319 1317 1320 ///The traits class. 1318 typedef TRTraits;1321 typedef _Traits Traits; 1319 1322 1320 1323 ///The type of the digraph the algorithm runs on. … … 1322 1325 1323 1326 ///The visitor type used by the algorithm. 1324 typedef VSVisitor;1327 typedef _Visitor Visitor; 1325 1328 1326 1329 ///The type of the map that indicates which nodes are reached. … … 1423 1426 /// The simplest way to execute the BFS algorithm is to use one of the 1424 1427 /// member functions called \ref run(Node) "run()".\n 1425 /// If you need better control on the execution,you have to call1426 /// \ref init() first, then you can add several source nodes with1428 /// If you need more control on the execution, first you have to call 1429 /// \ref init(), then you can add several source nodes with 1427 1430 /// \ref addSource(). Finally the actual path computation can be 1428 1431 /// performed with one of the \ref start() functions. … … 1733 1736 ///@{ 1734 1737 1735 /// \brief Checks if the givennode is reached from the root(s).1738 /// \brief Checks if a node is reached from the root(s). 1736 1739 /// 1737 1740 /// Returns \c true if \c v is reached from the root(s).
Note: See TracChangeset
for help on using the changeset viewer.
