Changeset 1749:c13f6b4aa40e in lemon0.x for lemon/dfs.h
 Timestamp:
 11/02/05 16:22:28 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2278
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/dfs.h
r1710 r1749 28 28 #include <lemon/maps.h> 29 29 30 #include <lemon/concept_check.h> 31 30 32 namespace lemon { 31 32 33 33 34 … … 124 125 /// 125 126 ///\author Jacint Szabo and Alpar Juttner 126 ///\todo A compare object would be nice.127 128 127 #ifdef DOXYGEN 129 128 template <typename GR, … … 276 275 /// 277 276 template <class T> 278 struct DefReachedMap {277 struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > { 279 278 typedef Dfs< Graph, DefReachedMapTraits<T> > Create; 280 279 }; … … 327 326 G(&_G), 328 327 _pred(NULL), local_pred(false), 329 // _predNode(NULL), local_predNode(false),330 328 _dist(NULL), local_dist(false), 331 329 _reached(NULL), local_reached(false), … … 337 335 { 338 336 if(local_pred) delete _pred; 339 // if(local_predNode) delete _predNode;340 337 if(local_dist) delete _dist; 341 338 if(local_reached) delete _reached; … … 359 356 return *this; 360 357 } 361 362 // ///Sets the map storing the predecessor nodes.363 364 // ///Sets the map storing the predecessor nodes.365 // ///If you don't use this function before calling \ref run(),366 // ///it will allocate one. The destuctor deallocates this367 // ///automatically allocated map, of course.368 // ///\return <tt> (*this) </tt>369 // Dfs &predNodeMap(PredNodeMap &m)370 // {371 // if(local_predNode) {372 // delete _predNode;373 // local_predNode=false;374 // }375 // _predNode = &m;376 // return *this;377 // }378 358 379 359 ///Sets the map storing the distances calculated by the algorithm. … … 469 449 _reached>set(s,true); 470 450 _pred>set(s,INVALID); 471 // _predNode>set(u,INVALID);472 451 OutEdgeIt e(*G,s); 473 452 if(e!=INVALID) { … … 496 475 _pred>set(m,e); 497 476 _reached>set(m,true); 498 // _pred_node>set(m,G>source(e));499 477 ++_stack_head; 500 478 _stack[_stack_head] = OutEdgeIt(*G, m); … … 505 483 ++_stack[_stack_head]; 506 484 } 507 //'m' is now the (original) source of the _stack[_stack_head]508 485 while(_stack_head>=0 && _stack[_stack_head]==INVALID) { 509 486 _processed>set(m,true); … … 591 568 ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>. 592 569 /// 593 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,570 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map, 594 571 ///not a node map. 595 template<class NM>596 void start(const NM &nm)597 598 while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();599 600 572 template<class EM> 573 void start(const EM &em) 574 { 575 while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge(); 576 } 577 601 578 ///Runs %DFS algorithm from node \c s. 602 579 … … 726 703 const PredMap &predMap() const { return *_pred;} 727 704 728 // ///Returns a reference to the map of nodes of %DFS paths.729 730 // ///Returns a reference to the NodeMap of the last but one nodes of the731 // ///%DFS tree.732 // ///\pre \ref run() must be called before using this function.733 // const PredNodeMap &predNodeMap() const { return *_predNode;}734 735 705 ///Checks if a node is reachable from the root. 736 706 … … 775 745 return new PredMap(); 776 746 } 777 // ///\brief The type of the map that stores the last but one778 // ///nodes of the %DFS paths.779 // ///780 // ///The type of the map that stores the last but one781 // ///nodes of the %DFS paths.782 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.783 // ///784 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;785 // ///Instantiates a PredNodeMap.786 787 // ///This function instantiates a \ref PredNodeMap.788 // ///\param G is the graph, to which789 // ///we would like to define the \ref PredNodeMap790 // static PredNodeMap *createPredNodeMap(const GR &G)791 // {792 // return new PredNodeMap();793 // }794 747 795 748 ///The type of the map that indicates which nodes are processed. … … 872 825 ///Pointer to the map of predecessors edges. 873 826 void *_pred; 874 // ///Pointer to the map of predecessors nodes.875 // void *_predNode;876 827 ///Pointer to the map of distances. 877 828 void *_dist; … … 885 836 /// all of the attributes to default values (0, INVALID). 886 837 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 887 // _predNode(0),888 838 _dist(0), _source(INVALID) {} 889 839 … … 897 847 DfsWizardBase(const GR &g, Node s=INVALID) : 898 848 _g((void *)&g), _reached(0), _processed(0), _pred(0), 899 // _predNode(0),900 849 _dist(0), _source(s) {} 901 850 … … 946 895 ///edges of the %DFS paths. 947 896 typedef typename TR::PredMap PredMap; 948 // ///\brief The type of the map that stores the last but one949 // ///nodes of the %DFS paths.950 // typedef typename TR::PredNodeMap PredNodeMap;951 897 ///The type of the map that stores the distances of the nodes. 952 898 typedef typename TR::DistMap DistMap; … … 979 925 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed); 980 926 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred); 981 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);982 927 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist); 983 928 alg.run(Base::_source); … … 1056 1001 } 1057 1002 1058 1059 // template<class T>1060 // struct DefPredNodeMapBase : public Base {1061 // typedef T PredNodeMap;1062 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };1063 // DefPredNodeMapBase(const TR &b) : TR(b) {}1064 // };1065 1066 // ///\brief \ref namedtemplparam "Named parameter"1067 // ///function for setting PredNodeMap type1068 // ///1069 // /// \ref namedtemplparam "Named parameter"1070 // ///function for setting PredNodeMap type1071 // ///1072 // template<class T>1073 // DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)1074 // {1075 // Base::_predNode=(void *)&t;1076 // return DfsWizard<DefPredNodeMapBase<T> >(*this);1077 // }1078 1079 1003 template<class T> 1080 1004 struct DefDistMapBase : public Base { … … 1133 1057 } 1134 1058 1059 /// \brief Visitor class for dfs. 1060 /// 1061 /// It gives a simple interface for a functional interface for dfs 1062 /// traversal. The traversal on a linear data structure. 1063 template <typename _Graph> 1064 struct DfsVisitor { 1065 typedef _Graph Graph; 1066 typedef typename Graph::Edge Edge; 1067 typedef typename Graph::Node Node; 1068 /// \brief Called when the edge reach a node. 1069 /// 1070 /// It is called when the dfs find an edge which target is not 1071 /// reached yet. 1072 void discover(const Edge& edge) {} 1073 /// \brief Called when the node reached first time. 1074 /// 1075 /// It is Called when the node reached first time. 1076 void reach(const Node& node) {} 1077 /// \brief Called when we step back on an edge. 1078 /// 1079 /// It is called when the dfs should step back on the edge. 1080 void backtrack(const Edge& edge) {} 1081 /// \brief Called when we step back from the node. 1082 /// 1083 /// It is called when we step back from the node. 1084 void leave(const Node& node) {} 1085 /// \brief Called when the edge examined but target of the edge 1086 /// already discovered. 1087 /// 1088 /// It called when the edge examined but the target of the edge 1089 /// already discovered. 1090 void examine(const Edge& edge) {} 1091 /// \brief Called for the source node of the dfs. 1092 /// 1093 /// It is called for the source node of the dfs. 1094 void start(const Node&) {} 1095 /// \brief Called when we leave the source node of the dfs. 1096 /// 1097 /// It is called when we leave the source node of the dfs. 1098 void stop(const Node&) {} 1099 1100 template <typename _Visitor> 1101 struct Constraints { 1102 void constraints() { 1103 Edge edge; 1104 Node node; 1105 visitor.discover(edge); 1106 visitor.reach(node); 1107 visitor.backtrack(edge); 1108 visitor.leave(node); 1109 visitor.examine(edge); 1110 visitor.start(node); 1111 visitor.stop(edge); 1112 } 1113 _Visitor& visitor; 1114 }; 1115 }; 1116 1117 /// \brief Default traits class of DfsVisit class. 1118 /// 1119 /// Default traits class of DfsVisit class. 1120 /// \param _Graph Graph type. 1121 template<class _Graph> 1122 struct DfsVisitDefaultTraits { 1123 1124 /// \brief The graph type the algorithm runs on. 1125 typedef _Graph Graph; 1126 1127 /// \brief The type of the map that indicates which nodes are reached. 1128 /// 1129 /// The type of the map that indicates which nodes are reached. 1130 /// It must meet the \ref concept::WriteMap "WriteMap" concept. 1131 /// \todo named parameter to set this type, function to read and write. 1132 typedef typename Graph::template NodeMap<bool> ReachedMap; 1133 1134 /// \brief Instantiates a ReachedMap. 1135 /// 1136 /// This function instantiates a \ref ReachedMap. 1137 /// \param G is the graph, to which 1138 /// we would like to define the \ref ReachedMap. 1139 static ReachedMap *createReachedMap(const Graph &graph) { 1140 return new ReachedMap(graph); 1141 } 1142 1143 }; 1144 1145 /// %DFS Visit algorithm class. 1146 1147 /// \ingroup flowalgs 1148 /// This class provides an efficient implementation of the %DFS algorithm 1149 /// with visitor interface. 1150 /// 1151 /// The %DfsVisit class provides an alternative interface to the Dfs 1152 /// class. It works with callback mechanism, the DfsVisit object calls 1153 /// on every dfs event the \c Visitor class member functions. 1154 /// 1155 /// \param _Graph The graph type the algorithm runs on. The default value is 1156 /// \ref ListGraph. The value of _Graph is not used directly by Dfs, it 1157 /// is only passed to \ref DfsDefaultTraits. 1158 /// \param _Visitor The Visitor object for the algorithm. The 1159 /// \ref DfsVisitor "DfsVisitor<_Graph>" is an empty Visitor which 1160 /// does not observe the Dfs events. If you want to observe the dfs 1161 /// events you should implement your own Visitor class. 1162 /// \param _Traits Traits class to set various data types used by the 1163 /// algorithm. The default traits class is 1164 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Graph>". 1165 /// See \ref DfsVisitDefaultTraits for the documentation of 1166 /// a Dfs visit traits class. 1167 /// 1168 /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso 1169 #ifdef DOXYGEN 1170 template <typename _Graph, typename _Visitor, typename _Traits> 1171 #else 1172 template <typename _Graph = ListGraph, 1173 typename _Visitor = DfsVisitor<_Graph>, 1174 typename _Traits = DfsDefaultTraits<_Graph> > 1175 #endif 1176 class DfsVisit { 1177 public: 1178 1179 /// \brief \ref Exception for uninitialized parameters. 1180 /// 1181 /// This error represents problems in the initialization 1182 /// of the parameters of the algorithms. 1183 class UninitializedParameter : public lemon::UninitializedParameter { 1184 public: 1185 virtual const char* exceptionName() const { 1186 return "lemon::DfsVisit::UninitializedParameter"; 1187 } 1188 }; 1189 1190 typedef _Traits Traits; 1191 1192 typedef typename Traits::Graph Graph; 1193 1194 typedef _Visitor Visitor; 1195 1196 ///The type of the map indicating which nodes are reached. 1197 typedef typename Traits::ReachedMap ReachedMap; 1198 1199 private: 1200 1201 typedef typename Graph::Node Node; 1202 typedef typename Graph::NodeIt NodeIt; 1203 typedef typename Graph::Edge Edge; 1204 typedef typename Graph::OutEdgeIt OutEdgeIt; 1205 1206 /// Pointer to the underlying graph. 1207 const Graph *_graph; 1208 /// Pointer to the visitor object. 1209 Visitor *_visitor; 1210 ///Pointer to the map of reached status of the nodes. 1211 ReachedMap *_reached; 1212 ///Indicates if \ref _reached is locally allocated (\c true) or not. 1213 bool local_reached; 1214 1215 std::vector<typename Graph::Edge> _stack; 1216 int _stack_head; 1217 1218 /// \brief Creates the maps if necessary. 1219 /// 1220 /// Creates the maps if necessary. 1221 void create_maps() { 1222 if(!_reached) { 1223 local_reached = true; 1224 _reached = Traits::createReachedMap(*_graph); 1225 } 1226 } 1227 1228 protected: 1229 1230 DfsVisit() {} 1231 1232 public: 1233 1234 typedef DfsVisit Create; 1235 1236 /// \name Named template parameters 1237 1238 ///@{ 1239 template <class T> 1240 struct DefReachedMapTraits : public Traits { 1241 typedef T ReachedMap; 1242 static ReachedMap *createReachedMap(const Graph &graph) { 1243 throw UninitializedParameter(); 1244 } 1245 }; 1246 /// \brief \ref namedtemplparam "Named parameter" for setting 1247 /// ReachedMap type 1248 /// 1249 /// \ref namedtemplparam "Named parameter" for setting ReachedMap type 1250 template <class T> 1251 struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > { 1252 typedef Dfs< Graph, DefReachedMapTraits<T> > Create; 1253 }; 1254 ///@} 1255 1256 public: 1257 1258 /// \brief Constructor. 1259 /// 1260 /// Constructor. 1261 /// 1262 /// \param graph the graph the algorithm will run on. 1263 /// \param visitor The visitor of the algorithm. 1264 /// 1265 DfsVisit(const Graph& graph, Visitor& visitor) 1266 : _graph(&graph), _visitor(&visitor), 1267 _reached(0), local_reached(false) {} 1268 1269 /// \brief Destructor. 1270 /// 1271 /// Destructor. 1272 ~DfsVisit() { 1273 if(local_reached) delete _reached; 1274 } 1275 1276 /// \brief Sets the map indicating if a node is reached. 1277 /// 1278 /// Sets the map indicating if a node is reached. 1279 /// If you don't use this function before calling \ref run(), 1280 /// it will allocate one. The destuctor deallocates this 1281 /// automatically allocated map, of course. 1282 /// \return <tt> (*this) </tt> 1283 DfsVisit &reachedMap(ReachedMap &m) { 1284 if(local_reached) { 1285 delete _reached; 1286 local_reached=false; 1287 } 1288 _reached = &m; 1289 return *this; 1290 } 1291 1292 public: 1293 /// \name Execution control 1294 /// The simplest way to execute the algorithm is to use 1295 /// one of the member functions called \c run(...). 1296 /// \n 1297 /// If you need more control on the execution, 1298 /// first you must call \ref init(), then you can add several source nodes 1299 /// with \ref addSource(). 1300 /// Finally \ref start() will perform the actual path 1301 /// computation. 1302 1303 /// @{ 1304 /// \brief Initializes the internal data structures. 1305 /// 1306 /// Initializes the internal data structures. 1307 /// 1308 void init() { 1309 create_maps(); 1310 _stack.resize(countNodes(*_graph)); 1311 _stack_head = 1; 1312 for (NodeIt u(*_graph) ; u != INVALID ; ++u) { 1313 _reached>set(u, false); 1314 } 1315 } 1316 1317 /// \brief Adds a new source node. 1318 /// 1319 /// Adds a new source node to the set of nodes to be processed. 1320 void addSource(Node s) { 1321 if(!(*_reached)[s]) { 1322 _reached>set(s,true); 1323 _visitor>start(s); 1324 _visitor>reach(s); 1325 Edge e; 1326 _graph>firstOut(e, s); 1327 if (e != INVALID) { 1328 _stack[++_stack_head] = e; 1329 } else { 1330 _visitor>leave(s); 1331 } 1332 } 1333 } 1334 1335 /// \brief Processes the next edge. 1336 /// 1337 /// Processes the next edge. 1338 /// 1339 /// \return The processed edge. 1340 /// 1341 /// \pre The stack must not be empty! 1342 Edge processNextEdge() { 1343 Edge e = _stack[_stack_head]; 1344 Node m = _graph>target(e); 1345 if(!(*_reached)[m]) { 1346 _visitor>discover(e); 1347 _visitor>reach(m); 1348 _reached>set(m, true); 1349 _graph>firstOut(_stack[++_stack_head], m); 1350 } else { 1351 _visitor>examine(e); 1352 m = _graph>source(e); 1353 _graph>nextOut(_stack[_stack_head]); 1354 } 1355 while (_stack_head>=0 && _stack[_stack_head] == INVALID) { 1356 _visitor>leave(m); 1357 _stack_head; 1358 if (_stack_head >= 0) { 1359 _visitor>backtrack(_stack[_stack_head]); 1360 m = _graph>source(_stack[_stack_head]); 1361 _graph>nextOut(_stack[_stack_head]); 1362 } else { 1363 _visitor>stop(m); 1364 } 1365 } 1366 return e; 1367 } 1368 1369 /// \brief Next edge to be processed. 1370 /// 1371 /// Next edge to be processed. 1372 /// 1373 /// \return The next edge to be processed or INVALID if the stack is 1374 /// empty. 1375 Edge nextEdge() { 1376 return _stack_head >= 0 ? _stack[_stack_head] : INVALID; 1377 } 1378 1379 /// \brief Returns \c false if there are nodes 1380 /// to be processed in the queue 1381 /// 1382 /// Returns \c false if there are nodes 1383 /// to be processed in the queue 1384 /// 1385 /// \todo This should be called emptyStack() or some "neutral" name. 1386 bool emptyQueue() { return _stack_head < 0; } 1387 1388 /// \brief Returns the number of the nodes to be processed. 1389 /// 1390 /// Returns the number of the nodes to be processed in the queue. 1391 /// 1392 ///\todo This should be called stackSize() or some "neutral" name. 1393 int queueSize() { return _stack_head + 1; } 1394 1395 /// \brief Executes the algorithm. 1396 /// 1397 /// Executes the algorithm. 1398 /// 1399 /// \pre init() must be called and at least one node should be added 1400 /// with addSource() before using this function. 1401 void start() { 1402 while ( !emptyQueue() ) processNextEdge(); 1403 } 1404 1405 /// \brief Executes the algorithm until \c dest is reached. 1406 /// 1407 /// Executes the algorithm until \c dest is reached. 1408 /// 1409 /// \pre init() must be called and at least one node should be added 1410 /// with addSource() before using this function. 1411 void start(Node dest) { 1412 while ( !emptyQueue() && _graph>target(_stack[_stack_head]) != dest) 1413 processNextEdge(); 1414 } 1415 1416 /// \brief Executes the algorithm until a condition is met. 1417 /// 1418 /// Executes the algorithm until a condition is met. 1419 /// 1420 /// \pre init() must be called and at least one node should be added 1421 /// with addSource() before using this function. 1422 /// 1423 /// \param nm must be a bool (or convertible) edge map. The algorithm 1424 /// will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>. 1425 /// 1426 /// \warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map, 1427 /// not a node map. 1428 template <typename EM> 1429 void start(const EM &em) { 1430 while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge(); 1431 } 1432 1433 /// \brief Runs %DFS algorithm from node \c s. 1434 /// 1435 /// This method runs the %DFS algorithm from a root node \c s. 1436 /// \note d.run(s) is just a shortcut of the following code. 1437 /// \code 1438 /// d.init(); 1439 /// d.addSource(s); 1440 /// d.start(); 1441 /// \endcode 1442 void run(Node s) { 1443 init(); 1444 addSource(s); 1445 start(); 1446 } 1447 ///@} 1448 1449 /// \name Query Functions 1450 /// The result of the %DFS algorithm can be obtained using these 1451 /// functions.\n 1452 /// Before the use of these functions, 1453 /// either run() or start() must be called. 1454 ///@{ 1455 /// \brief Checks if a node is reachable from the root. 1456 /// 1457 /// Returns \c true if \c v is reachable from the root(s). 1458 /// \warning The source nodes are inditated as unreachable. 1459 /// \pre Either \ref run() or \ref start() 1460 /// must be called before using this function. 1461 /// 1462 bool reached(Node v) { return (*_reached)[v]; } 1463 ///@} 1464 }; 1465 1466 1135 1467 } //END OF NAMESPACE LEMON 1136 1468
Note: See TracChangeset
for help on using the changeset viewer.