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