Changes in / [534:6d3a9eec82b4:533:6643fc6dafc1] in lemon-main
- Location:
- lemon
- Files:
-
- 8 edited
-
bfs.h (modified) (16 diffs)
-
bits/array_map.h (modified) (1 diff)
-
bits/vector_map.h (modified) (1 diff)
-
circulation.h (modified) (6 diffs)
-
concepts/graph_components.h (modified) (4 diffs)
-
dfs.h (modified) (16 diffs)
-
dijkstra.h (modified) (17 diffs)
-
preflow.h (modified) (4 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r503 r440 50 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 { … … 65 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 66 66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 ///Instantiates a \cProcessedMap.68 69 ///This function instantiates a \refProcessedMap.67 ///Instantiates a ProcessedMap. 68 69 ///This function instantiates a ProcessedMap. 70 70 ///\param g is the digraph, to which 71 ///we would like to define the \refProcessedMap71 ///we would like to define the ProcessedMap 72 72 #ifdef DOXYGEN 73 73 static ProcessedMap *createProcessedMap(const Digraph &g) … … 84 84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 85 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 ///Instantiates a \cReachedMap.87 88 ///This function instantiates a \refReachedMap.86 ///Instantiates a ReachedMap. 87 88 ///This function instantiates a ReachedMap. 89 89 ///\param g is the digraph, to which 90 ///we would like to define the \refReachedMap.90 ///we would like to define the ReachedMap. 91 91 static ReachedMap *createReachedMap(const Digraph &g) 92 92 { … … 99 99 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 100 100 typedef typename Digraph::template NodeMap<int> DistMap; 101 ///Instantiates a \cDistMap.102 103 ///This function instantiates a \refDistMap.101 ///Instantiates a DistMap. 102 103 ///This function instantiates a DistMap. 104 104 ///\param g is the digraph, to which we would like to define the 105 /// \refDistMap.105 ///DistMap. 106 106 static DistMap *createDistMap(const Digraph &g) 107 107 { … … 222 222 }; 223 223 ///\brief \ref named-templ-param "Named parameter" for setting 224 /// \cPredMap type.224 ///PredMap type. 225 225 /// 226 226 ///\ref named-templ-param "Named parameter" for setting 227 /// \cPredMap type.227 ///PredMap type. 228 228 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 229 229 template <class T> … … 242 242 }; 243 243 ///\brief \ref named-templ-param "Named parameter" for setting 244 /// \cDistMap type.244 ///DistMap type. 245 245 /// 246 246 ///\ref named-templ-param "Named parameter" for setting 247 /// \cDistMap type.247 ///DistMap type. 248 248 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 249 249 template <class T> … … 262 262 }; 263 263 ///\brief \ref named-templ-param "Named parameter" for setting 264 /// \cReachedMap type.264 ///ReachedMap type. 265 265 /// 266 266 ///\ref named-templ-param "Named parameter" for setting 267 /// \cReachedMap type.267 ///ReachedMap type. 268 268 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 269 269 template <class T> … … 282 282 }; 283 283 ///\brief \ref named-templ-param "Named parameter" for setting 284 /// \cProcessedMap type.284 ///ProcessedMap type. 285 285 /// 286 286 ///\ref named-templ-param "Named parameter" for setting 287 /// \cProcessedMap type.287 ///ProcessedMap type. 288 288 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 289 289 template <class T> … … 301 301 }; 302 302 ///\brief \ref named-templ-param "Named parameter" for setting 303 /// \cProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.303 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 304 304 /// 305 305 ///\ref named-templ-param "Named parameter" for setting 306 /// \cProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.306 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 307 307 ///If you don't set it explicitly, it will be automatically allocated. 308 308 struct SetStandardProcessedMap : … … 1195 1195 /// This class defines the interface of the BfsVisit events, and 1196 1196 /// it could be the base of a real visitor class. 1197 template <typename GR>1197 template <typename _Digraph> 1198 1198 struct BfsVisitor { 1199 typedef GRDigraph;1199 typedef _Digraph Digraph; 1200 1200 typedef typename Digraph::Arc Arc; 1201 1201 typedef typename Digraph::Node Node; … … 1225 1225 }; 1226 1226 #else 1227 template <typename GR>1227 template <typename _Digraph> 1228 1228 struct BfsVisitor { 1229 typedef GRDigraph;1229 typedef _Digraph Digraph; 1230 1230 typedef typename Digraph::Arc Arc; 1231 1231 typedef typename Digraph::Node Node; … … 1255 1255 /// 1256 1256 /// Default traits class of BfsVisit class. 1257 /// \tparam GRThe type of the digraph the algorithm runs on.1258 template<class GR>1257 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1258 template<class _Digraph> 1259 1259 struct BfsVisitDefaultTraits { 1260 1260 1261 1261 /// \brief The type of the digraph the algorithm runs on. 1262 typedef GRDigraph;1262 typedef _Digraph Digraph; 1263 1263 1264 1264 /// \brief The type of the map that indicates which nodes are reached. … … 1281 1281 /// \ingroup search 1282 1282 /// 1283 /// \brief BFS algorithm class with visitor interface.1283 /// \brief %BFS algorithm class with visitor interface. 1284 1284 /// 1285 /// This class provides an efficient implementation of the BFS algorithm1285 /// This class provides an efficient implementation of the %BFS algorithm 1286 1286 /// with visitor interface. 1287 1287 /// 1288 /// The BfsVisit class provides an alternative interface to the Bfs1288 /// The %BfsVisit class provides an alternative interface to the Bfs 1289 1289 /// class. It works with callback mechanism, the BfsVisit object calls 1290 1290 /// the member functions of the \c Visitor class on every BFS event. … … 1295 1295 /// instead. 1296 1296 /// 1297 /// \tparam GRThe type of the digraph the algorithm runs on.1298 /// The default type is \ref ListDigraph.1299 /// The value of GR is not used directly by \ref BfsVisit,1300 /// it is only passed to \ref BfsVisitDefaultTraits.1301 /// \tparam VSThe Visitor type that is used by the algorithm.1302 /// \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 1303 1303 /// does not observe the BFS events. If you want to observe the BFS 1304 1304 /// events, you should implement your own visitor class. 1305 /// \tparam TRTraits class to set various data types used by the1305 /// \tparam _Traits Traits class to set various data types used by the 1306 1306 /// algorithm. The default traits class is 1307 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits< GR>".1307 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>". 1308 1308 /// See \ref BfsVisitDefaultTraits for the documentation of 1309 1309 /// a BFS visit traits class. 1310 1310 #ifdef DOXYGEN 1311 template <typename GR, typename VS, typename TR>1311 template <typename _Digraph, typename _Visitor, typename _Traits> 1312 1312 #else 1313 template <typename GR= ListDigraph,1314 typename VS = BfsVisitor<GR>,1315 typename TR = BfsVisitDefaultTraits<GR> >1313 template <typename _Digraph = ListDigraph, 1314 typename _Visitor = BfsVisitor<_Digraph>, 1315 typename _Traits = BfsVisitDefaultTraits<_Digraph> > 1316 1316 #endif 1317 1317 class BfsVisit { … … 1319 1319 1320 1320 ///The traits class. 1321 typedef TRTraits;1321 typedef _Traits Traits; 1322 1322 1323 1323 ///The type of the digraph the algorithm runs on. … … 1325 1325 1326 1326 ///The visitor type used by the algorithm. 1327 typedef VSVisitor;1327 typedef _Visitor Visitor; 1328 1328 1329 1329 ///The type of the map that indicates which nodes are reached. -
lemon/bits/array_map.h
r503 r440 136 136 // \brief Template assign operator. 137 137 // 138 // The given parameter should conform to the ReadMap138 // The given parameter should be conform to the ReadMap 139 139 // concecpt and could be indiced by the current item set of 140 140 // the NodeMap. In this case the value for each item -
lemon/bits/vector_map.h
r503 r440 125 125 // \brief Template assign operator. 126 126 // 127 // The given parameter should conform to the ReadMap127 // The given parameter should be conform to the ReadMap 128 128 // concecpt and could be indiced by the current item set of 129 129 // the NodeMap. In this case the value for each item -
lemon/circulation.h
r503 r440 32 32 /// 33 33 /// Default traits class of Circulation class. 34 /// \tparam GRDigraph type.35 /// \tparam LMLower bound capacity map type.36 /// \tparam UMUpper bound capacity map type.37 /// \tparam DMDelta map type.38 template <typename GR, typename LM,39 typename UM, typename DM>34 /// \tparam _Diraph Digraph type. 35 /// \tparam _LCapMap Lower bound capacity map type. 36 /// \tparam _UCapMap Upper bound capacity map type. 37 /// \tparam _DeltaMap Delta map type. 38 template <typename _Diraph, typename _LCapMap, 39 typename _UCapMap, typename _DeltaMap> 40 40 struct CirculationDefaultTraits { 41 41 42 42 /// \brief The type of the digraph the algorithm runs on. 43 typedef GRDigraph;43 typedef _Diraph Digraph; 44 44 45 45 /// \brief The type of the map that stores the circulation lower … … 48 48 /// The type of the map that stores the circulation lower bound. 49 49 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. 50 typedef LMLCapMap;50 typedef _LCapMap LCapMap; 51 51 52 52 /// \brief The type of the map that stores the circulation upper … … 55 55 /// The type of the map that stores the circulation upper bound. 56 56 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. 57 typedef UMUCapMap;57 typedef _UCapMap UCapMap; 58 58 59 59 /// \brief The type of the map that stores the lower bound for … … 63 63 /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap" 64 64 /// concept. 65 typedef DMDeltaMap;65 typedef _DeltaMap DeltaMap; 66 66 67 67 /// \brief The type of the flow values. … … 138 138 in this way. 139 139 140 \tparam GRThe type of the digraph the algorithm runs on.141 \tparam LMThe type of the lower bound capacity map. The default142 map type is \ref concepts::Digraph::ArcMap " GR::ArcMap<int>".143 \tparam UMThe type of the upper bound capacity map. The default144 map type is \c LM.145 \tparam DMThe type of the map that stores the lower bound140 \tparam _Digraph The type of the digraph the algorithm runs on. 141 \tparam _LCapMap The type of the lower bound capacity map. The default 142 map type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>". 143 \tparam _UCapMap The type of the upper bound capacity map. The default 144 map type is \c _LCapMap. 145 \tparam _DeltaMap The type of the map that stores the lower bound 146 146 for the supply of the nodes. The default map type is 147 \ ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".147 \c _Digraph::ArcMap<_UCapMap::Value>. 148 148 */ 149 149 #ifdef DOXYGEN 150 template< typename GR,151 typename LM,152 typename UM,153 typename DM,154 typename TR>150 template< typename _Digraph, 151 typename _LCapMap, 152 typename _UCapMap, 153 typename _DeltaMap, 154 typename _Traits > 155 155 #else 156 template< typename GR, 157 typename LM = typename GR::template ArcMap<int>, 158 typename UM = LM, 159 typename DM = typename GR::template NodeMap<typename UM::Value>, 160 typename TR = CirculationDefaultTraits<GR, LM, UM, DM> > 156 template< typename _Digraph, 157 typename _LCapMap = typename _Digraph::template ArcMap<int>, 158 typename _UCapMap = _LCapMap, 159 typename _DeltaMap = typename _Digraph:: 160 template NodeMap<typename _UCapMap::Value>, 161 typename _Traits=CirculationDefaultTraits<_Digraph, _LCapMap, 162 _UCapMap, _DeltaMap> > 161 163 #endif 162 164 class Circulation { … … 164 166 165 167 ///The \ref CirculationDefaultTraits "traits class" of the algorithm. 166 typedef TRTraits;168 typedef _Traits Traits; 167 169 ///The type of the digraph the algorithm runs on. 168 170 typedef typename Traits::Digraph Digraph; -
lemon/concepts/graph_components.h
r534 r529 115 115 /// 116 116 /// This class provides the minimal set of features needed for a 117 /// directed graph structure. All digraph concepts have to 117 /// directed graph structure. All digraph concepts have to be 118 118 /// conform to this base directed graph. It just provides types 119 119 /// for nodes and arcs and functions to get the source and the … … 180 180 /// This class provides the minimal set of features needed for an 181 181 /// undirected graph structure. All undirected graph concepts have 182 /// to conform to this base graph. It just provides types for182 /// to be conform to this base graph. It just provides types for 183 183 /// nodes, arcs and edges and functions to get the 184 184 /// source and the target of the arcs and edges, … … 295 295 /// This class provides beside the core digraph features 296 296 /// core id functions for the digraph structure. 297 /// The most of the base digraphs should conform to this concept.297 /// The most of the base digraphs should be conform to this concept. 298 298 /// The id's are unique and immutable. 299 299 template <typename _Base = BaseDigraphComponent> … … 373 373 /// This class provides beside the core undirected graph features 374 374 /// core id functions for the undirected graph structure. The 375 /// most of the base undirected graphs should conform to this375 /// most of the base undirected graphs should be conform to this 376 376 /// concept. The id's are unique and immutable. 377 377 template <typename _Base = BaseGraphComponent> -
lemon/dfs.h
r503 r440 50 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 { … … 65 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 66 66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 ///Instantiates a \cProcessedMap.68 69 ///This function instantiates a \refProcessedMap.67 ///Instantiates a ProcessedMap. 68 69 ///This function instantiates a ProcessedMap. 70 70 ///\param g is the digraph, to which 71 ///we would like to define the \ref ProcessedMap.71 ///we would like to define the ProcessedMap 72 72 #ifdef DOXYGEN 73 73 static ProcessedMap *createProcessedMap(const Digraph &g) … … 84 84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 85 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 ///Instantiates a \cReachedMap.87 88 ///This function instantiates a \refReachedMap.86 ///Instantiates a ReachedMap. 87 88 ///This function instantiates a ReachedMap. 89 89 ///\param g is the digraph, to which 90 ///we would like to define the \refReachedMap.90 ///we would like to define the ReachedMap. 91 91 static ReachedMap *createReachedMap(const Digraph &g) 92 92 { … … 99 99 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 100 100 typedef typename Digraph::template NodeMap<int> DistMap; 101 ///Instantiates a \cDistMap.102 103 ///This function instantiates a \refDistMap.101 ///Instantiates a DistMap. 102 103 ///This function instantiates a DistMap. 104 104 ///\param g is the digraph, to which we would like to define the 105 /// \refDistMap.105 ///DistMap. 106 106 static DistMap *createDistMap(const Digraph &g) 107 107 { … … 221 221 }; 222 222 ///\brief \ref named-templ-param "Named parameter" for setting 223 /// \cPredMap type.223 ///PredMap type. 224 224 /// 225 225 ///\ref named-templ-param "Named parameter" for setting 226 /// \cPredMap type.226 ///PredMap type. 227 227 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 228 228 template <class T> … … 241 241 }; 242 242 ///\brief \ref named-templ-param "Named parameter" for setting 243 /// \cDistMap type.243 ///DistMap type. 244 244 /// 245 245 ///\ref named-templ-param "Named parameter" for setting 246 /// \cDistMap type.246 ///DistMap type. 247 247 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 248 248 template <class T> … … 261 261 }; 262 262 ///\brief \ref named-templ-param "Named parameter" for setting 263 /// \cReachedMap type.263 ///ReachedMap type. 264 264 /// 265 265 ///\ref named-templ-param "Named parameter" for setting 266 /// \cReachedMap type.266 ///ReachedMap type. 267 267 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 268 268 template <class T> … … 281 281 }; 282 282 ///\brief \ref named-templ-param "Named parameter" for setting 283 /// \cProcessedMap type.283 ///ProcessedMap type. 284 284 /// 285 285 ///\ref named-templ-param "Named parameter" for setting 286 /// \cProcessedMap type.286 ///ProcessedMap type. 287 287 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 288 288 template <class T> … … 299 299 }; 300 300 ///\brief \ref named-templ-param "Named parameter" for setting 301 /// \cProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.301 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 302 302 /// 303 303 ///\ref named-templ-param "Named parameter" for setting 304 /// \cProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.304 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 305 305 ///If you don't set it explicitly, it will be automatically allocated. 306 306 struct SetStandardProcessedMap : … … 1127 1127 /// This class defines the interface of the DfsVisit events, and 1128 1128 /// it could be the base of a real visitor class. 1129 template <typename GR>1129 template <typename _Digraph> 1130 1130 struct DfsVisitor { 1131 typedef GRDigraph;1131 typedef _Digraph Digraph; 1132 1132 typedef typename Digraph::Arc Arc; 1133 1133 typedef typename Digraph::Node Node; … … 1165 1165 }; 1166 1166 #else 1167 template <typename GR>1167 template <typename _Digraph> 1168 1168 struct DfsVisitor { 1169 typedef GRDigraph;1169 typedef _Digraph Digraph; 1170 1170 typedef typename Digraph::Arc Arc; 1171 1171 typedef typename Digraph::Node Node; … … 1200 1200 /// Default traits class of DfsVisit class. 1201 1201 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1202 template<class GR>1202 template<class _Digraph> 1203 1203 struct DfsVisitDefaultTraits { 1204 1204 1205 1205 /// \brief The type of the digraph the algorithm runs on. 1206 typedef GRDigraph;1206 typedef _Digraph Digraph; 1207 1207 1208 1208 /// \brief The type of the map that indicates which nodes are reached. … … 1225 1225 /// \ingroup search 1226 1226 /// 1227 /// \brief DFS algorithm class with visitor interface.1227 /// \brief %DFS algorithm class with visitor interface. 1228 1228 /// 1229 /// This class provides an efficient implementation of the DFS algorithm1229 /// This class provides an efficient implementation of the %DFS algorithm 1230 1230 /// with visitor interface. 1231 1231 /// 1232 /// The DfsVisit class provides an alternative interface to the Dfs1232 /// The %DfsVisit class provides an alternative interface to the Dfs 1233 1233 /// class. It works with callback mechanism, the DfsVisit object calls 1234 1234 /// the member functions of the \c Visitor class on every DFS event. … … 1239 1239 /// instead. 1240 1240 /// 1241 /// \tparam GRThe type of the digraph the algorithm runs on.1242 /// The default type is \ref ListDigraph.1243 /// The value of GR is not used directly by \ref DfsVisit,1244 /// it is only passed to \ref DfsVisitDefaultTraits.1245 /// \tparam VSThe Visitor type that is used by the algorithm.1246 /// \ref DfsVisitor "DfsVisitor< GR>" is an empty visitor, which1241 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1242 /// The default value is 1243 /// \ref ListDigraph. The value of _Digraph is not used directly by 1244 /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits. 1245 /// \tparam _Visitor The Visitor type that is used by the algorithm. 1246 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which 1247 1247 /// does not observe the DFS events. If you want to observe the DFS 1248 1248 /// events, you should implement your own visitor class. 1249 /// \tparam TRTraits class to set various data types used by the1249 /// \tparam _Traits Traits class to set various data types used by the 1250 1250 /// algorithm. The default traits class is 1251 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits< GR>".1251 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>". 1252 1252 /// See \ref DfsVisitDefaultTraits for the documentation of 1253 1253 /// a DFS visit traits class. 1254 1254 #ifdef DOXYGEN 1255 template <typename GR, typename VS, typename TR>1255 template <typename _Digraph, typename _Visitor, typename _Traits> 1256 1256 #else 1257 template <typename GR= ListDigraph,1258 typename VS = DfsVisitor<GR>,1259 typename TR = DfsVisitDefaultTraits<GR> >1257 template <typename _Digraph = ListDigraph, 1258 typename _Visitor = DfsVisitor<_Digraph>, 1259 typename _Traits = DfsVisitDefaultTraits<_Digraph> > 1260 1260 #endif 1261 1261 class DfsVisit { … … 1263 1263 1264 1264 ///The traits class. 1265 typedef TRTraits;1265 typedef _Traits Traits; 1266 1266 1267 1267 ///The type of the digraph the algorithm runs on. … … 1269 1269 1270 1270 ///The visitor type used by the algorithm. 1271 typedef VSVisitor;1271 typedef _Visitor Visitor; 1272 1272 1273 1273 ///The type of the map that indicates which nodes are reached. -
lemon/dijkstra.h
r503 r440 74 74 typedef typename LM::Value Value; 75 75 76 /// Operation traits for %Dijkstra algorithm.76 /// Operation traits for Dijkstra algorithm. 77 77 78 78 /// This class defines the operations that are used in the algorithm. … … 85 85 /// Usually it is \c Digraph::NodeMap<int>. 86 86 typedef typename Digraph::template NodeMap<int> HeapCrossRef; 87 ///Instantiates a \ cHeapCrossRef.87 ///Instantiates a \ref HeapCrossRef. 88 88 89 89 ///This function instantiates a \ref HeapCrossRef. … … 95 95 } 96 96 97 ///The heap type used by the %Dijkstra algorithm.97 ///The heap type used by the Dijkstra algorithm. 98 98 99 99 ///The heap type used by the Dijkstra algorithm. … … 102 102 ///\sa Dijkstra 103 103 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap; 104 ///Instantiates a \ cHeap.104 ///Instantiates a \ref Heap. 105 105 106 106 ///This function instantiates a \ref Heap. … … 117 117 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 118 118 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 119 ///Instantiates a \cPredMap.120 121 ///This function instantiates a \refPredMap.119 ///Instantiates a PredMap. 120 121 ///This function instantiates a PredMap. 122 122 ///\param g is the digraph, to which we would like to define the 123 /// \refPredMap.123 ///PredMap. 124 124 static PredMap *createPredMap(const Digraph &g) 125 125 { … … 133 133 ///By default it is a NullMap. 134 134 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 135 ///Instantiates a \cProcessedMap.136 137 ///This function instantiates a \refProcessedMap.135 ///Instantiates a ProcessedMap. 136 137 ///This function instantiates a ProcessedMap. 138 138 ///\param g is the digraph, to which 139 ///we would like to define the \ref ProcessedMap.139 ///we would like to define the ProcessedMap 140 140 #ifdef DOXYGEN 141 141 static ProcessedMap *createProcessedMap(const Digraph &g) … … 152 152 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 153 153 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap; 154 ///Instantiates a \cDistMap.155 156 ///This function instantiates a \refDistMap.154 ///Instantiates a DistMap. 155 156 ///This function instantiates a DistMap. 157 157 ///\param g is the digraph, to which we would like to define 158 ///the \ref DistMap.158 ///the DistMap 159 159 static DistMap *createDistMap(const Digraph &g) 160 160 { … … 217 217 ///The heap type used by the algorithm. 218 218 typedef typename TR::Heap Heap; 219 ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class" 220 ///of the algorithm. 219 ///The operation traits class. 221 220 typedef typename TR::OperationTraits OperationTraits; 222 221 … … 234 233 const Digraph *G; 235 234 //Pointer to the length map. 236 const LengthMap * _length;235 const LengthMap *length; 237 236 //Pointer to the map of predecessors arcs. 238 237 PredMap *_pred; … … 299 298 }; 300 299 ///\brief \ref named-templ-param "Named parameter" for setting 301 /// \cPredMap type.300 ///PredMap type. 302 301 /// 303 302 ///\ref named-templ-param "Named parameter" for setting 304 /// \cPredMap type.303 ///PredMap type. 305 304 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 306 305 template <class T> … … 320 319 }; 321 320 ///\brief \ref named-templ-param "Named parameter" for setting 322 /// \cDistMap type.321 ///DistMap type. 323 322 /// 324 323 ///\ref named-templ-param "Named parameter" for setting 325 /// \cDistMap type.324 ///DistMap type. 326 325 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 327 326 template <class T> … … 341 340 }; 342 341 ///\brief \ref named-templ-param "Named parameter" for setting 343 /// \cProcessedMap type.342 ///ProcessedMap type. 344 343 /// 345 344 ///\ref named-templ-param "Named parameter" for setting 346 /// \cProcessedMap type.345 ///ProcessedMap type. 347 346 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 348 347 template <class T> … … 360 359 }; 361 360 ///\brief \ref named-templ-param "Named parameter" for setting 362 /// \cProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.361 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 363 362 /// 364 363 ///\ref named-templ-param "Named parameter" for setting 365 /// \cProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.364 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 366 365 ///If you don't set it explicitly, it will be automatically allocated. 367 366 struct SetStandardProcessedMap … … 441 440 /// 442 441 ///\ref named-templ-param "Named parameter" for setting 443 ///\ cOperationTraits type.442 ///\ref OperationTraits type. 444 443 template <class T> 445 444 struct SetOperationTraits … … 460 459 461 460 ///Constructor. 462 ///\param g The digraph the algorithm runs on.463 ///\param length The length map used by the algorithm.464 Dijkstra(const Digraph& g, const LengthMap&length) :465 G(& g), _length(&length),461 ///\param _g The digraph the algorithm runs on. 462 ///\param _length The length map used by the algorithm. 463 Dijkstra(const Digraph& _g, const LengthMap& _length) : 464 G(&_g), length(&_length), 466 465 _pred(NULL), local_pred(false), 467 466 _dist(NULL), local_dist(false), … … 487 486 Dijkstra &lengthMap(const LengthMap &m) 488 487 { 489 _length = &m;488 length = &m; 490 489 return *this; 491 490 } … … 640 639 switch(_heap->state(w)) { 641 640 case Heap::PRE_HEAP: 642 _heap->push(w,OperationTraits::plus(oldvalue, (* _length)[e]));641 _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e])); 643 642 _pred->set(w,e); 644 643 break; 645 644 case Heap::IN_HEAP: 646 645 { 647 Value newvalue = OperationTraits::plus(oldvalue, (* _length)[e]);646 Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]); 648 647 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) { 649 648 _heap->decrease(w, newvalue); -
lemon/preflow.h
r503 r440 32 32 /// 33 33 /// Default traits class of Preflow class. 34 /// \tparam GRDigraph type.35 /// \tparam CMCapacity map type.36 template <typename GR, typename CM>34 /// \tparam _Digraph Digraph type. 35 /// \tparam _CapacityMap Capacity map type. 36 template <typename _Digraph, typename _CapacityMap> 37 37 struct PreflowDefaultTraits { 38 38 39 39 /// \brief The type of the digraph the algorithm runs on. 40 typedef GRDigraph;40 typedef _Digraph Digraph; 41 41 42 42 /// \brief The type of the map that stores the arc capacities. … … 44 44 /// The type of the map that stores the arc capacities. 45 45 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. 46 typedef CMCapacityMap;46 typedef _CapacityMap CapacityMap; 47 47 48 48 /// \brief The type of the flow values. … … 105 105 /// second phase constructs a feasible maximum flow on each arc. 106 106 /// 107 /// \tparam GRThe type of the digraph the algorithm runs on.108 /// \tparam CMThe type of the capacity map. The default map109 /// type is \ref concepts::Digraph::ArcMap " GR::ArcMap<int>".107 /// \tparam _Digraph The type of the digraph the algorithm runs on. 108 /// \tparam _CapacityMap The type of the capacity map. The default map 109 /// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>". 110 110 #ifdef DOXYGEN 111 template <typename GR, typename CM, typename TR>111 template <typename _Digraph, typename _CapacityMap, typename _Traits> 112 112 #else 113 template <typename GR,114 typename CM = typename GR::template ArcMap<int>,115 typename TR = PreflowDefaultTraits<GR, CM> >113 template <typename _Digraph, 114 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 115 typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> > 116 116 #endif 117 117 class Preflow { … … 119 119 120 120 ///The \ref PreflowDefaultTraits "traits class" of the algorithm. 121 typedef TRTraits;121 typedef _Traits Traits; 122 122 ///The type of the digraph the algorithm runs on. 123 123 typedef typename Traits::Digraph Digraph;
Note: See TracChangeset
for help on using the changeset viewer.
