Changeset 2306:42cce226b87b in lemon-0.x for lemon/bfs.h
- Timestamp:
- 11/21/06 19:22:08 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3081
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r2300 r2306 588 588 } 589 589 590 ///Executes the algorithm until \c dest is reached.591 592 ///Executes the algorithm until \c dest is reached.590 ///Executes the algorithm until \c dest is the next node to processed. 591 592 ///Executes the algorithm until \c dest is the next node to processed. 593 593 /// 594 594 ///\pre init() must be called and at least one node should be added … … 615 615 ///with addSource() before using this function. 616 616 /// 617 ///\param nm must be a bool (or convertible) node map. The algorithm 618 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>. 617 ///\param nm must be a bool (or convertible) node map. The 618 ///algorithm will stop when for the next processable node \c v is 619 ///<tt>nm[v]</tt> true. 619 620 ///\todo query the reached target 620 621 template<class NM> … … 634 635 ///- The distance of each node from the root. 635 636 /// 636 ///\note d.run(s) is just a shortcut of the following code.637 ///\note b.run(s) is just a shortcut of the following code. 637 638 ///\code 638 /// d.init();639 /// d.addSource(s);640 /// d.start();639 /// b.init(); 640 /// b.addSource(s); 641 /// b.start(); 641 642 ///\endcode 642 643 void run(Node s) { … … 652 653 ///\return The length of the shortest s---t path if there exists one, 653 654 ///0 otherwise. 654 ///\note Apart from the return value, d.run(s) is655 ///\note Apart from the return value, b.run(s) is 655 656 ///just a shortcut of the following code. 656 657 ///\code 657 /// d.init();658 /// d.addSource(s);659 /// d.start(t);658 /// b.init(); 659 /// b.addSource(s); 660 /// b.start(t); 660 661 ///\endcode 661 662 int run(Node s,Node t) { … … 672 673 ///functions.\n 673 674 ///Before the use of these functions, 674 ///either run() or start() must be calle d.675 ///either run() or start() must be calleb. 675 676 676 677 ///@{ … … 944 945 typedef typename TR::DistMap DistMap; 945 946 946 public:947 public: 947 948 /// Constructor. 948 949 BfsWizard() : TR() {} … … 1105 1106 } 1106 1107 1108 #ifdef DOXYGEN 1109 /// \brief Visitor class for bfs. 1110 /// 1111 /// It gives a simple interface for a functional interface for bfs 1112 /// traversal. The traversal on a linear data structure. 1113 template <typename _Graph> 1114 struct BfsVisitor { 1115 typedef _Graph Graph; 1116 typedef typename Graph::Edge Edge; 1117 typedef typename Graph::Node Node; 1118 /// \brief Called when the edge reach a node. 1119 /// 1120 /// It is called when the bfs find an edge which target is not 1121 /// reached yet. 1122 void discover(const Edge& edge) {} 1123 /// \brief Called when the node reached first time. 1124 /// 1125 /// It is Called when the node reached first time. 1126 void reach(const Node& node) {} 1127 /// \brief Called when the edge examined but target of the edge 1128 /// already discovered. 1129 /// 1130 /// It called when the edge examined but the target of the edge 1131 /// already discovered. 1132 void examine(const Edge& edge) {} 1133 /// \brief Called for the source node of the bfs. 1134 /// 1135 /// It is called for the source node of the bfs. 1136 void start(const Node& node) {} 1137 /// \brief Called when the node processed. 1138 /// 1139 /// It is Called when the node processed. 1140 void process(const Node& node) {} 1141 }; 1142 #else 1143 template <typename _Graph> 1144 struct BfsVisitor { 1145 typedef _Graph Graph; 1146 typedef typename Graph::Edge Edge; 1147 typedef typename Graph::Node Node; 1148 void discover(const Edge&) {} 1149 void reach(const Node&) {} 1150 void examine(const Edge&) {} 1151 void start(const Node&) {} 1152 void process(const Node&) {} 1153 1154 template <typename _Visitor> 1155 struct Constraints { 1156 void constraints() { 1157 Edge edge; 1158 Node node; 1159 visitor.discover(edge); 1160 visitor.reach(node); 1161 visitor.examine(edge); 1162 visitor.start(node); 1163 visitor.process(node); 1164 } 1165 _Visitor& visitor; 1166 }; 1167 }; 1168 #endif 1169 1170 /// \brief Default traits class of BfsVisit class. 1171 /// 1172 /// Default traits class of BfsVisit class. 1173 /// \param _Graph Graph type. 1174 template<class _Graph> 1175 struct BfsVisitDefaultTraits { 1176 1177 /// \brief The graph type the algorithm runs on. 1178 typedef _Graph Graph; 1179 1180 /// \brief The type of the map that indicates which nodes are reached. 1181 /// 1182 /// The type of the map that indicates which nodes are reached. 1183 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. 1184 /// \todo named parameter to set this type, function to read and write. 1185 typedef typename Graph::template NodeMap<bool> ReachedMap; 1186 1187 /// \brief Instantiates a ReachedMap. 1188 /// 1189 /// This function instantiates a \ref ReachedMap. 1190 /// \param graph is the graph, to which 1191 /// we would like to define the \ref ReachedMap. 1192 static ReachedMap *createReachedMap(const Graph &graph) { 1193 return new ReachedMap(graph); 1194 } 1195 1196 }; 1197 1198 /// %BFS Visit algorithm class. 1199 1200 /// \ingroup flowalgs 1201 /// This class provides an efficient implementation of the %BFS algorithm 1202 /// with visitor interface. 1203 /// 1204 /// The %BfsVisit class provides an alternative interface to the Bfs 1205 /// class. It works with callback mechanism, the BfsVisit object calls 1206 /// on every bfs event the \c Visitor class member functions. 1207 /// 1208 /// \param _Graph The graph type the algorithm runs on. The default value is 1209 /// \ref ListGraph. The value of _Graph is not used directly by Bfs, it 1210 /// is only passed to \ref BfsDefaultTraits. 1211 /// \param _Visitor The Visitor object for the algorithm. The 1212 /// \ref BfsVisitor "BfsVisitor<_Graph>" is an empty Visitor which 1213 /// does not observe the Bfs events. If you want to observe the bfs 1214 /// events you should implement your own Visitor class. 1215 /// \param _Traits Traits class to set various data types used by the 1216 /// algorithm. The default traits class is 1217 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Graph>". 1218 /// See \ref BfsVisitDefaultTraits for the documentation of 1219 /// a Bfs visit traits class. 1220 /// 1221 /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso 1222 #ifdef DOXYGEN 1223 template <typename _Graph, typename _Visitor, typename _Traits> 1224 #else 1225 template <typename _Graph = ListGraph, 1226 typename _Visitor = BfsVisitor<_Graph>, 1227 typename _Traits = BfsDefaultTraits<_Graph> > 1228 #endif 1229 class BfsVisit { 1230 public: 1231 1232 /// \brief \ref Exception for uninitialized parameters. 1233 /// 1234 /// This error represents problems in the initialization 1235 /// of the parameters of the algorithms. 1236 class UninitializedParameter : public lemon::UninitializedParameter { 1237 public: 1238 virtual const char* what() const throw() 1239 { 1240 return "lemon::BfsVisit::UninitializedParameter"; 1241 } 1242 }; 1243 1244 typedef _Traits Traits; 1245 1246 typedef typename Traits::Graph Graph; 1247 1248 typedef _Visitor Visitor; 1249 1250 ///The type of the map indicating which nodes are reached. 1251 typedef typename Traits::ReachedMap ReachedMap; 1252 1253 private: 1254 1255 typedef typename Graph::Node Node; 1256 typedef typename Graph::NodeIt NodeIt; 1257 typedef typename Graph::Edge Edge; 1258 typedef typename Graph::OutEdgeIt OutEdgeIt; 1259 1260 /// Pointer to the underlying graph. 1261 const Graph *_graph; 1262 /// Pointer to the visitor object. 1263 Visitor *_visitor; 1264 ///Pointer to the map of reached status of the nodes. 1265 ReachedMap *_reached; 1266 ///Indicates if \ref _reached is locally allocated (\c true) or not. 1267 bool local_reached; 1268 1269 std::vector<typename Graph::Node> _list; 1270 int _list_front, _list_back; 1271 1272 /// \brief Creates the maps if necessary. 1273 /// 1274 /// Creates the maps if necessary. 1275 void create_maps() { 1276 if(!_reached) { 1277 local_reached = true; 1278 _reached = Traits::createReachedMap(*_graph); 1279 } 1280 } 1281 1282 protected: 1283 1284 BfsVisit() {} 1285 1286 public: 1287 1288 typedef BfsVisit Create; 1289 1290 /// \name Named template parameters 1291 1292 ///@{ 1293 template <class T> 1294 struct DefReachedMapTraits : public Traits { 1295 typedef T ReachedMap; 1296 static ReachedMap *createReachedMap(const Graph &graph) { 1297 throw UninitializedParameter(); 1298 } 1299 }; 1300 /// \brief \ref named-templ-param "Named parameter" for setting 1301 /// ReachedMap type 1302 /// 1303 /// \ref named-templ-param "Named parameter" for setting ReachedMap type 1304 template <class T> 1305 struct DefReachedMap : public BfsVisit< Graph, Visitor, 1306 DefReachedMapTraits<T> > { 1307 typedef BfsVisit< Graph, Visitor, DefReachedMapTraits<T> > Create; 1308 }; 1309 ///@} 1310 1311 public: 1312 1313 /// \brief Constructor. 1314 /// 1315 /// Constructor. 1316 /// 1317 /// \param graph the graph the algorithm will run on. 1318 /// \param visitor The visitor of the algorithm. 1319 /// 1320 BfsVisit(const Graph& graph, Visitor& visitor) 1321 : _graph(&graph), _visitor(&visitor), 1322 _reached(0), local_reached(false) {} 1323 1324 /// \brief Destructor. 1325 /// 1326 /// Destructor. 1327 ~BfsVisit() { 1328 if(local_reached) delete _reached; 1329 } 1330 1331 /// \brief Sets the map indicating if a node is reached. 1332 /// 1333 /// Sets the map indicating if a node is reached. 1334 /// If you don't use this function before calling \ref run(), 1335 /// it will allocate one. The destuctor deallocates this 1336 /// automatically allocated map, of course. 1337 /// \return <tt> (*this) </tt> 1338 BfsVisit &reachedMap(ReachedMap &m) { 1339 if(local_reached) { 1340 delete _reached; 1341 local_reached = false; 1342 } 1343 _reached = &m; 1344 return *this; 1345 } 1346 1347 public: 1348 /// \name Execution control 1349 /// The simplest way to execute the algorithm is to use 1350 /// one of the member functions called \c run(...). 1351 /// \n 1352 /// If you need more control on the execution, 1353 /// first you must call \ref init(), then you can adda source node 1354 /// with \ref addSource(). 1355 /// Finally \ref start() will perform the actual path 1356 /// computation. 1357 1358 /// @{ 1359 /// \brief Initializes the internal data structures. 1360 /// 1361 /// Initializes the internal data structures. 1362 /// 1363 void init() { 1364 create_maps(); 1365 _list.resize(countNodes(*_graph)); 1366 _list_front = _list_back = -1; 1367 for (NodeIt u(*_graph) ; u != INVALID ; ++u) { 1368 _reached->set(u, false); 1369 } 1370 } 1371 1372 /// \brief Adds a new source node. 1373 /// 1374 /// Adds a new source node to the set of nodes to be processed. 1375 void addSource(Node s) { 1376 if(!(*_reached)[s]) { 1377 _reached->set(s,true); 1378 _visitor->start(s); 1379 _visitor->reach(s); 1380 _list[++_list_back] = s; 1381 } 1382 } 1383 1384 /// \brief Processes the next node. 1385 /// 1386 /// Processes the next node. 1387 /// 1388 /// \return The processed node. 1389 /// 1390 /// \pre The queue must not be empty! 1391 Node processNextNode() { 1392 Node n = _list[++_list_front]; 1393 _visitor->process(n); 1394 Edge e; 1395 for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) { 1396 Node m = _graph->target(e); 1397 if (!(*_reached)[m]) { 1398 _visitor->discover(e); 1399 _visitor->reach(m); 1400 _reached->set(m, true); 1401 _list[++_list_back] = m; 1402 } else { 1403 _visitor->examine(e); 1404 } 1405 } 1406 return n; 1407 } 1408 1409 /// \brief Processes the next node. 1410 /// 1411 /// Processes the next node. And checks that the given target node 1412 /// is reached. If the target node is reachable from the processed 1413 /// node then the reached parameter will be set true. The reached 1414 /// parameter should be initially false. 1415 /// 1416 /// \param target The target node. 1417 /// \retval reached Indicates that the target node is reached. 1418 /// \return The processed node. 1419 /// 1420 /// \warning The queue must not be empty! 1421 Node processNextNode(Node target, bool& reached) { 1422 Node n = _list[++_list_front]; 1423 _visitor->process(n); 1424 Edge e; 1425 for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) { 1426 Node m = _graph->target(e); 1427 if (!(*_reached)[m]) { 1428 _visitor->discover(e); 1429 _visitor->reach(m); 1430 _reached->set(m, true); 1431 _list[++_list_back] = m; 1432 reached = reached || (target == m); 1433 } else { 1434 _visitor->examine(e); 1435 } 1436 } 1437 return n; 1438 } 1439 1440 /// \brief Processes the next node. 1441 /// 1442 /// Processes the next node. And checks that at least one of 1443 /// reached node has true value in the \c nm nodemap. If one node 1444 /// with true value is reachable from the processed node then the 1445 /// reached parameter will be set true. The reached parameter 1446 /// should be initially false. 1447 /// 1448 /// \param target The nodemaps of possible targets. 1449 /// \retval reached Indicates that one of the target nodes is reached. 1450 /// \return The processed node. 1451 /// 1452 /// \warning The queue must not be empty! 1453 template <typename NM> 1454 Node processNextNode(const NM& nm, bool& reached) { 1455 Node n = _list[++_list_front]; 1456 _visitor->process(n); 1457 Edge e; 1458 for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) { 1459 Node m = _graph->target(e); 1460 if (!(*_reached)[m]) { 1461 _visitor->discover(e); 1462 _visitor->reach(m); 1463 _reached->set(m, true); 1464 _list[++_list_back] = m; 1465 reached = reached || nm[m]; 1466 } else { 1467 _visitor->examine(e); 1468 } 1469 } 1470 return n; 1471 } 1472 1473 /// \brief Next node to be processed. 1474 /// 1475 /// Next node to be processed. 1476 /// 1477 /// \return The next node to be processed or INVALID if the stack is 1478 /// empty. 1479 Node nextNode() { 1480 return _list_front != _list_back ? _list[_list_front + 1] : INVALID; 1481 } 1482 1483 /// \brief Returns \c false if there are nodes 1484 /// to be processed in the queue 1485 /// 1486 /// Returns \c false if there are nodes 1487 /// to be processed in the queue 1488 bool emptyQueue() { return _list_front == _list_back; } 1489 1490 /// \brief Returns the number of the nodes to be processed. 1491 /// 1492 /// Returns the number of the nodes to be processed in the queue. 1493 int queueSize() { return _list_back - _list_front; } 1494 1495 /// \brief Executes the algorithm. 1496 /// 1497 /// Executes the algorithm. 1498 /// 1499 /// \pre init() must be called and at least one node should be added 1500 /// with addSource() before using this function. 1501 void start() { 1502 while ( !emptyQueue() ) processNextNode(); 1503 } 1504 1505 /// \brief Executes the algorithm until \c dest will be next processed. 1506 /// 1507 /// Executes the algorithm until \c dest will be next processed. 1508 /// 1509 /// \pre init() must be called and at least one node should be added 1510 /// with addSource() before using this function. 1511 void start(Node dest) { 1512 bool reached = false; 1513 while (!emptyQueue() && !reached) { 1514 processNextNode(dest, reached); 1515 } 1516 } 1517 1518 /// \brief Executes the algorithm until a condition is met. 1519 /// 1520 /// Executes the algorithm until a condition is met. 1521 /// 1522 /// \pre init() must be called and at least one node should be added 1523 /// with addSource() before using this function. 1524 /// 1525 ///\param nm must be a bool (or convertible) node map. The 1526 ///algorithm will stop when it reaches a node \c v with 1527 ///<tt>nm[v]</tt> true. 1528 template <typename NM> 1529 void start(const NM &nm) { 1530 bool reached = false; 1531 while (!emptyQueue() && !reached) { 1532 processNextNode(nm, reached); 1533 } 1534 } 1535 1536 /// \brief Runs %BFSVisit algorithm from node \c s. 1537 /// 1538 /// This method runs the %BFS algorithm from a root node \c s. 1539 /// \note b.run(s) is just a shortcut of the following code. 1540 ///\code 1541 /// b.init(); 1542 /// b.addSource(s); 1543 /// b.start(); 1544 ///\endcode 1545 void run(Node s) { 1546 init(); 1547 addSource(s); 1548 start(); 1549 } 1550 1551 /// \brief Runs %BFSVisit algorithm to visit all nodes in the graph. 1552 /// 1553 /// This method runs the %BFS algorithm in order to 1554 /// compute the %BFS path to each node. The algorithm computes 1555 /// - The %BFS tree. 1556 /// - The distance of each node from the root in the %BFS tree. 1557 /// 1558 ///\note b.run() is just a shortcut of the following code. 1559 ///\code 1560 /// b.init(); 1561 /// for (NodeIt it(graph); it != INVALID; ++it) { 1562 /// if (!b.reached(it)) { 1563 /// b.addSource(it); 1564 /// b.start(); 1565 /// } 1566 /// } 1567 ///\endcode 1568 void run() { 1569 init(); 1570 for (NodeIt it(*_graph); it != INVALID; ++it) { 1571 if (!reached(it)) { 1572 addSource(it); 1573 start(); 1574 } 1575 } 1576 } 1577 ///@} 1578 1579 /// \name Query Functions 1580 /// The result of the %BFS algorithm can be obtained using these 1581 /// functions.\n 1582 /// Before the use of these functions, 1583 /// either run() or start() must be called. 1584 ///@{ 1585 1586 /// \brief Checks if a node is reachable from the root. 1587 /// 1588 /// Returns \c true if \c v is reachable from the root(s). 1589 /// \warning The source nodes are inditated as unreachable. 1590 /// \pre Either \ref run() or \ref start() 1591 /// must be called before using this function. 1592 /// 1593 bool reached(Node v) { return (*_reached)[v]; } 1594 ///@} 1595 }; 1596 1107 1597 } //END OF NAMESPACE LEMON 1108 1598
Note: See TracChangeset
for help on using the changeset viewer.