Changes in / [533:6643fc6dafc1:534:6d3a9eec82b4] 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
r440 r503 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 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 { … … 65 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 66 66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 ///Instantiates a ProcessedMap.68 69 ///This function instantiates a ProcessedMap.67 ///Instantiates a \c ProcessedMap. 68 69 ///This function instantiates a \ref ProcessedMap. 70 70 ///\param g is the digraph, to which 71 ///we would like to define the ProcessedMap71 ///we would like to define the \ref 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 ReachedMap.87 88 ///This function instantiates a ReachedMap.86 ///Instantiates a \c ReachedMap. 87 88 ///This function instantiates a \ref ReachedMap. 89 89 ///\param g is the digraph, to which 90 ///we would like to define the ReachedMap.90 ///we would like to define the \ref 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 DistMap.102 103 ///This function instantiates a DistMap.101 ///Instantiates a \c DistMap. 102 103 ///This function instantiates a \ref DistMap. 104 104 ///\param g is the digraph, to which we would like to define the 105 /// DistMap.105 ///\ref 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 /// PredMap type.224 ///\c PredMap type. 225 225 /// 226 226 ///\ref named-templ-param "Named parameter" for setting 227 /// PredMap type.227 ///\c 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 /// DistMap type.244 ///\c DistMap type. 245 245 /// 246 246 ///\ref named-templ-param "Named parameter" for setting 247 /// DistMap type.247 ///\c 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 /// ReachedMap type.264 ///\c ReachedMap type. 265 265 /// 266 266 ///\ref named-templ-param "Named parameter" for setting 267 /// ReachedMap type.267 ///\c 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 /// ProcessedMap type.284 ///\c ProcessedMap type. 285 285 /// 286 286 ///\ref named-templ-param "Named parameter" for setting 287 /// ProcessedMap type.287 ///\c 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 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.303 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 304 304 /// 305 305 ///\ref named-templ-param "Named parameter" for setting 306 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.306 ///\c 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 _Digraph>1197 template <typename GR> 1198 1198 struct BfsVisitor { 1199 typedef _DigraphDigraph;1199 typedef GR Digraph; 1200 1200 typedef typename Digraph::Arc Arc; 1201 1201 typedef typename Digraph::Node Node; … … 1225 1225 }; 1226 1226 #else 1227 template <typename _Digraph>1227 template <typename GR> 1228 1228 struct BfsVisitor { 1229 typedef _DigraphDigraph;1229 typedef GR 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 _DigraphThe type of the digraph the algorithm runs on.1258 template<class _Digraph>1257 /// \tparam GR The type of the digraph the algorithm runs on. 1258 template<class GR> 1259 1259 struct BfsVisitDefaultTraits { 1260 1260 1261 1261 /// \brief The type of the digraph the algorithm runs on. 1262 typedef _DigraphDigraph;1262 typedef GR 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 _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, which1297 /// \tparam GR The 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 VS The Visitor type that is used by the algorithm. 1302 /// \ref BfsVisitor "BfsVisitor<GR>" 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 _TraitsTraits class to set various data types used by the1305 /// \tparam TR Traits class to set various data types used by the 1306 1306 /// algorithm. The default traits class is 1307 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits< _Digraph>".1307 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>". 1308 1308 /// See \ref BfsVisitDefaultTraits for the documentation of 1309 1309 /// a BFS visit traits class. 1310 1310 #ifdef DOXYGEN 1311 template <typename _Digraph, typename _Visitor, typename _Traits>1311 template <typename GR, typename VS, typename TR> 1312 1312 #else 1313 template <typename _Digraph= ListDigraph,1314 typename _Visitor = BfsVisitor<_Digraph>,1315 typename _Traits = BfsVisitDefaultTraits<_Digraph> >1313 template <typename GR = ListDigraph, 1314 typename VS = BfsVisitor<GR>, 1315 typename TR = BfsVisitDefaultTraits<GR> > 1316 1316 #endif 1317 1317 class BfsVisit { … … 1319 1319 1320 1320 ///The traits class. 1321 typedef _TraitsTraits;1321 typedef TR 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 _VisitorVisitor;1327 typedef VS Visitor; 1328 1328 1329 1329 ///The type of the map that indicates which nodes are reached. -
lemon/bits/array_map.h
r440 r503 136 136 // \brief Template assign operator. 137 137 // 138 // The given parameter should beconform to the ReadMap138 // The given parameter should 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
r440 r503 125 125 // \brief Template assign operator. 126 126 // 127 // The given parameter should beconform to the ReadMap127 // The given parameter should 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
r440 r503 32 32 /// 33 33 /// Default traits class of Circulation class. 34 /// \tparam _DiraphDigraph type.35 /// \tparam _LCapMapLower bound capacity map type.36 /// \tparam _UCapMapUpper bound capacity map type.37 /// \tparam _DeltaMapDelta map type.38 template <typename _Diraph, typename _LCapMap,39 typename _UCapMap, typename _DeltaMap>34 /// \tparam GR Digraph type. 35 /// \tparam LM Lower bound capacity map type. 36 /// \tparam UM Upper bound capacity map type. 37 /// \tparam DM Delta map type. 38 template <typename GR, typename LM, 39 typename UM, typename DM> 40 40 struct CirculationDefaultTraits { 41 41 42 42 /// \brief The type of the digraph the algorithm runs on. 43 typedef _DiraphDigraph;43 typedef GR 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 _LCapMapLCapMap;50 typedef LM 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 _UCapMapUCapMap;57 typedef UM 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 _DeltaMapDeltaMap;65 typedef DM DeltaMap; 66 66 67 67 /// \brief The type of the flow values. … … 138 138 in this way. 139 139 140 \tparam _DigraphThe type of the digraph the algorithm runs on.141 \tparam _LCapMapThe type of the lower bound capacity map. The default142 map type is \ref concepts::Digraph::ArcMap " _Digraph::ArcMap<int>".143 \tparam _UCapMapThe type of the upper bound capacity map. The default144 map type is \c _LCapMap.145 \tparam _DeltaMapThe type of the map that stores the lower bound140 \tparam GR The type of the digraph the algorithm runs on. 141 \tparam LM The type of the lower bound capacity map. The default 142 map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 143 \tparam UM The type of the upper bound capacity map. The default 144 map type is \c LM. 145 \tparam DM The type of the map that stores the lower bound 146 146 for the supply of the nodes. The default map type is 147 \ c _Digraph::ArcMap<_UCapMap::Value>.147 \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>". 148 148 */ 149 149 #ifdef DOXYGEN 150 template< typename _Digraph,151 typename _LCapMap,152 typename _UCapMap,153 typename _DeltaMap,154 typename _Traits>150 template< typename GR, 151 typename LM, 152 typename UM, 153 typename DM, 154 typename TR > 155 155 #else 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> > 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> > 163 161 #endif 164 162 class Circulation { … … 166 164 167 165 ///The \ref CirculationDefaultTraits "traits class" of the algorithm. 168 typedef _TraitsTraits;166 typedef TR Traits; 169 167 ///The type of the digraph the algorithm runs on. 170 168 typedef typename Traits::Digraph Digraph; -
lemon/concepts/graph_components.h
r529 r534 115 115 /// 116 116 /// This class provides the minimal set of features needed for a 117 /// directed graph structure. All digraph concepts have to be117 /// directed graph structure. All digraph concepts have to 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 beconform to this base graph. It just provides types for182 /// to 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 beconform to this concept.297 /// The most of the base digraphs should 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 beconform to this375 /// most of the base undirected graphs should conform to this 376 376 /// concept. The id's are unique and immutable. 377 377 template <typename _Base = BaseGraphComponent> -
lemon/dfs.h
r440 r503 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 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 { … … 65 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 66 66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 ///Instantiates a ProcessedMap.68 69 ///This function instantiates a ProcessedMap.67 ///Instantiates a \c ProcessedMap. 68 69 ///This function instantiates a \ref ProcessedMap. 70 70 ///\param g is the digraph, to which 71 ///we would like to define the ProcessedMap71 ///we would like to define the \ref 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 ReachedMap.87 88 ///This function instantiates a ReachedMap.86 ///Instantiates a \c ReachedMap. 87 88 ///This function instantiates a \ref ReachedMap. 89 89 ///\param g is the digraph, to which 90 ///we would like to define the ReachedMap.90 ///we would like to define the \ref 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 DistMap.102 103 ///This function instantiates a DistMap.101 ///Instantiates a \c DistMap. 102 103 ///This function instantiates a \ref DistMap. 104 104 ///\param g is the digraph, to which we would like to define the 105 /// DistMap.105 ///\ref 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 /// PredMap type.223 ///\c PredMap type. 224 224 /// 225 225 ///\ref named-templ-param "Named parameter" for setting 226 /// PredMap type.226 ///\c 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 /// DistMap type.243 ///\c DistMap type. 244 244 /// 245 245 ///\ref named-templ-param "Named parameter" for setting 246 /// DistMap type.246 ///\c 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 /// ReachedMap type.263 ///\c ReachedMap type. 264 264 /// 265 265 ///\ref named-templ-param "Named parameter" for setting 266 /// ReachedMap type.266 ///\c 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 /// ProcessedMap type.283 ///\c ProcessedMap type. 284 284 /// 285 285 ///\ref named-templ-param "Named parameter" for setting 286 /// ProcessedMap type.286 ///\c 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 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.301 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 302 302 /// 303 303 ///\ref named-templ-param "Named parameter" for setting 304 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.304 ///\c 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 _Digraph>1129 template <typename GR> 1130 1130 struct DfsVisitor { 1131 typedef _DigraphDigraph;1131 typedef GR Digraph; 1132 1132 typedef typename Digraph::Arc Arc; 1133 1133 typedef typename Digraph::Node Node; … … 1165 1165 }; 1166 1166 #else 1167 template <typename _Digraph>1167 template <typename GR> 1168 1168 struct DfsVisitor { 1169 typedef _DigraphDigraph;1169 typedef GR 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 _Digraph>1202 template<class GR> 1203 1203 struct DfsVisitDefaultTraits { 1204 1204 1205 1205 /// \brief The type of the digraph the algorithm runs on. 1206 typedef _DigraphDigraph;1206 typedef GR 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 _DigraphThe type of the digraph the algorithm runs on.1242 /// The default value is1243 /// \ref ListDigraph. The value of _Digraph is not used directly by1244 /// \ref DfsVisit,it is only passed to \ref DfsVisitDefaultTraits.1245 /// \tparam _VisitorThe Visitor type that is used by the algorithm.1246 /// \ref DfsVisitor "DfsVisitor< _Digraph>" is an empty visitor, which1241 /// \tparam GR The 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 VS The Visitor type that is used by the algorithm. 1246 /// \ref DfsVisitor "DfsVisitor<GR>" 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 _TraitsTraits class to set various data types used by the1249 /// \tparam TR Traits class to set various data types used by the 1250 1250 /// algorithm. The default traits class is 1251 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits< _Digraph>".1251 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>". 1252 1252 /// See \ref DfsVisitDefaultTraits for the documentation of 1253 1253 /// a DFS visit traits class. 1254 1254 #ifdef DOXYGEN 1255 template <typename _Digraph, typename _Visitor, typename _Traits>1255 template <typename GR, typename VS, typename TR> 1256 1256 #else 1257 template <typename _Digraph= ListDigraph,1258 typename _Visitor = DfsVisitor<_Digraph>,1259 typename _Traits = DfsVisitDefaultTraits<_Digraph> >1257 template <typename GR = ListDigraph, 1258 typename VS = DfsVisitor<GR>, 1259 typename TR = DfsVisitDefaultTraits<GR> > 1260 1260 #endif 1261 1261 class DfsVisit { … … 1263 1263 1264 1264 ///The traits class. 1265 typedef _TraitsTraits;1265 typedef TR 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 _VisitorVisitor;1271 typedef VS Visitor; 1272 1272 1273 1273 ///The type of the map that indicates which nodes are reached. -
lemon/dijkstra.h
r440 r503 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 \ refHeapCrossRef.87 ///Instantiates a \c 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 \ refHeap.104 ///Instantiates a \c 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 PredMap.120 121 ///This function instantiates a PredMap.119 ///Instantiates a \c PredMap. 120 121 ///This function instantiates a \ref PredMap. 122 122 ///\param g is the digraph, to which we would like to define the 123 /// PredMap.123 ///\ref 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 ProcessedMap.136 137 ///This function instantiates a ProcessedMap.135 ///Instantiates a \c ProcessedMap. 136 137 ///This function instantiates a \ref ProcessedMap. 138 138 ///\param g is the digraph, to which 139 ///we would like to define the ProcessedMap139 ///we would like to define the \ref 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 DistMap.155 156 ///This function instantiates a DistMap.154 ///Instantiates a \c DistMap. 155 156 ///This function instantiates a \ref DistMap. 157 157 ///\param g is the digraph, to which we would like to define 158 ///the DistMap158 ///the \ref 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 ///The operation traits class. 219 ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class" 220 ///of the algorithm. 220 221 typedef typename TR::OperationTraits OperationTraits; 221 222 … … 233 234 const Digraph *G; 234 235 //Pointer to the length map. 235 const LengthMap * length;236 const LengthMap *_length; 236 237 //Pointer to the map of predecessors arcs. 237 238 PredMap *_pred; … … 298 299 }; 299 300 ///\brief \ref named-templ-param "Named parameter" for setting 300 /// PredMap type.301 ///\c PredMap type. 301 302 /// 302 303 ///\ref named-templ-param "Named parameter" for setting 303 /// PredMap type.304 ///\c PredMap type. 304 305 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 305 306 template <class T> … … 319 320 }; 320 321 ///\brief \ref named-templ-param "Named parameter" for setting 321 /// DistMap type.322 ///\c DistMap type. 322 323 /// 323 324 ///\ref named-templ-param "Named parameter" for setting 324 /// DistMap type.325 ///\c DistMap type. 325 326 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 326 327 template <class T> … … 340 341 }; 341 342 ///\brief \ref named-templ-param "Named parameter" for setting 342 /// ProcessedMap type.343 ///\c ProcessedMap type. 343 344 /// 344 345 ///\ref named-templ-param "Named parameter" for setting 345 /// ProcessedMap type.346 ///\c ProcessedMap type. 346 347 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 347 348 template <class T> … … 359 360 }; 360 361 ///\brief \ref named-templ-param "Named parameter" for setting 361 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.362 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 362 363 /// 363 364 ///\ref named-templ-param "Named parameter" for setting 364 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.365 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 365 366 ///If you don't set it explicitly, it will be automatically allocated. 366 367 struct SetStandardProcessedMap … … 440 441 /// 441 442 ///\ref named-templ-param "Named parameter" for setting 442 ///\ refOperationTraits type.443 ///\c OperationTraits type. 443 444 template <class T> 444 445 struct SetOperationTraits … … 459 460 460 461 ///Constructor. 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),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), 465 466 _pred(NULL), local_pred(false), 466 467 _dist(NULL), local_dist(false), … … 486 487 Dijkstra &lengthMap(const LengthMap &m) 487 488 { 488 length = &m;489 _length = &m; 489 490 return *this; 490 491 } … … 639 640 switch(_heap->state(w)) { 640 641 case Heap::PRE_HEAP: 641 _heap->push(w,OperationTraits::plus(oldvalue, (* length)[e]));642 _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e])); 642 643 _pred->set(w,e); 643 644 break; 644 645 case Heap::IN_HEAP: 645 646 { 646 Value newvalue = OperationTraits::plus(oldvalue, (* length)[e]);647 Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]); 647 648 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) { 648 649 _heap->decrease(w, newvalue); -
lemon/preflow.h
r440 r503 32 32 /// 33 33 /// Default traits class of Preflow class. 34 /// \tparam _DigraphDigraph type.35 /// \tparam _CapacityMapCapacity map type.36 template <typename _Digraph, typename _CapacityMap>34 /// \tparam GR Digraph type. 35 /// \tparam CM Capacity map type. 36 template <typename GR, typename CM> 37 37 struct PreflowDefaultTraits { 38 38 39 39 /// \brief The type of the digraph the algorithm runs on. 40 typedef _DigraphDigraph;40 typedef GR 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 _CapacityMapCapacityMap;46 typedef CM 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 _DigraphThe type of the digraph the algorithm runs on.108 /// \tparam _CapacityMapThe type of the capacity map. The default map109 /// type is \ref concepts::Digraph::ArcMap " _Digraph::ArcMap<int>".107 /// \tparam GR The type of the digraph the algorithm runs on. 108 /// \tparam CM The type of the capacity map. The default map 109 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 110 110 #ifdef DOXYGEN 111 template <typename _Digraph, typename _CapacityMap, typename _Traits>111 template <typename GR, typename CM, typename TR> 112 112 #else 113 template <typename _Digraph,114 typename _CapacityMap = typename _Digraph::template ArcMap<int>,115 typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> >113 template <typename GR, 114 typename CM = typename GR::template ArcMap<int>, 115 typename TR = PreflowDefaultTraits<GR, CM> > 116 116 #endif 117 117 class Preflow { … … 119 119 120 120 ///The \ref PreflowDefaultTraits "traits class" of the algorithm. 121 typedef _TraitsTraits;121 typedef TR 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.
