Changes in / [421:0f2091856dab:420:6a2a33ad261b] in lemon-main
- Location:
- lemon
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/connectivity.h
r419 r417 17 17 */ 18 18 19 #ifndef LEMON_ CONNECTIVITY_H20 #define LEMON_ CONNECTIVITY_H19 #ifndef LEMON_TOPOLOGY_H 20 #define LEMON_TOPOLOGY_H 21 21 22 22 #include <lemon/dfs.h> … … 155 155 } 156 156 157 namespace _ connectivity_bits {157 namespace _topology_bits { 158 158 159 159 template <typename Digraph, typename Iterator > … … 189 189 190 190 template <typename Digraph, typename ArcMap> 191 struct StronglyConnectedCut ArcsVisitor : public DfsVisitor<Digraph> {191 struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> { 192 192 public: 193 193 typedef typename Digraph::Node Node; 194 194 typedef typename Digraph::Arc Arc; 195 195 196 StronglyConnectedCut ArcsVisitor(const Digraph& digraph,197 ArcMap& cutMap,198 int& cutNum)196 StronglyConnectedCutEdgesVisitor(const Digraph& digraph, 197 ArcMap& cutMap, 198 int& cutNum) 199 199 : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum), 200 _compMap(digraph , -1), _num(-1) {201 } 202 203 void st art(const Node&) {200 _compMap(digraph), _num(0) { 201 } 202 203 void stop(const Node&) { 204 204 ++_num; 205 205 } … … 249 249 if (source == INVALID) return true; 250 250 251 using namespace _ connectivity_bits;251 using namespace _topology_bits; 252 252 253 253 typedef DfsVisitor<Digraph> Visitor; … … 266 266 267 267 typedef ReverseDigraph<const Digraph> RDigraph; 268 typedef typename RDigraph::NodeIt RNodeIt;269 268 RDigraph rdigraph(digraph); 270 269 … … 277 276 rdfs.start(); 278 277 279 for ( RNodeIt it(rdigraph); it != INVALID; ++it) {278 for (NodeIt it(rdigraph); it != INVALID; ++it) { 280 279 if (!rdfs.reached(it)) { 281 280 return false; … … 304 303 checkConcept<concepts::Digraph, Digraph>(); 305 304 306 using namespace _ connectivity_bits;305 using namespace _topology_bits; 307 306 308 307 typedef typename Digraph::Node Node; … … 376 375 checkConcept<concepts::WriteMap<Node, int>, NodeMap>(); 377 376 378 using namespace _ connectivity_bits;377 using namespace _topology_bits; 379 378 380 379 typedef std::vector<Node> Container; … … 440 439 checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>(); 441 440 442 using namespace _ connectivity_bits;441 using namespace _topology_bits; 443 442 444 443 typedef std::vector<Node> Container; … … 465 464 int cutNum = 0; 466 465 467 typedef StronglyConnectedCut ArcsVisitor<RDigraph, ArcMap> RVisitor;466 typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor; 468 467 RVisitor rvisitor(rgraph, cutMap, cutNum); 469 468 … … 480 479 } 481 480 482 namespace _ connectivity_bits {481 namespace _topology_bits { 483 482 484 483 template <typename Digraph> … … 732 731 typedef typename Graph::NodeIt NodeIt; 733 732 734 using namespace _ connectivity_bits;733 using namespace _topology_bits; 735 734 736 735 typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor; … … 775 774 checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>(); 776 775 777 using namespace _ connectivity_bits;776 using namespace _topology_bits; 778 777 779 778 typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor; … … 815 814 checkConcept<concepts::WriteMap<Node, bool>, NodeMap>(); 816 815 817 using namespace _ connectivity_bits;816 using namespace _topology_bits; 818 817 819 818 typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor; … … 834 833 } 835 834 836 namespace _ connectivity_bits {835 namespace _topology_bits { 837 836 838 837 template <typename Digraph> … … 1055 1054 typedef typename Graph::NodeIt NodeIt; 1056 1055 1057 using namespace _ connectivity_bits;1056 using namespace _topology_bits; 1058 1057 1059 1058 typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor; … … 1097 1096 checkConcept<concepts::WriteMap<Node, int>, NodeMap>(); 1098 1097 1099 using namespace _ connectivity_bits;1098 using namespace _topology_bits; 1100 1099 1101 1100 typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor; … … 1138 1137 checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>(); 1139 1138 1140 using namespace _ connectivity_bits;1139 using namespace _topology_bits; 1141 1140 1142 1141 typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor; … … 1158 1157 1159 1158 1160 namespace _ connectivity_bits {1159 namespace _topology_bits { 1161 1160 1162 1161 template <typename Digraph, typename IntNodeMap> … … 1195 1194 template <typename Digraph, typename NodeMap> 1196 1195 void topologicalSort(const Digraph& graph, NodeMap& order) { 1197 using namespace _ connectivity_bits;1196 using namespace _topology_bits; 1198 1197 1199 1198 checkConcept<concepts::Digraph, Digraph>(); … … 1236 1235 /// \see dag 1237 1236 template <typename Digraph, typename NodeMap> 1238 bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {1239 using namespace _ connectivity_bits;1237 bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) { 1238 using namespace _topology_bits; 1240 1239 1241 1240 checkConcept<concepts::Digraph, Digraph>(); … … 1247 1246 typedef typename Digraph::Arc Arc; 1248 1247 1249 for (NodeIt it(digraph); it != INVALID; ++it) { 1250 order.set(it, -1); 1251 } 1248 order = constMap<Node, int, -1>(); 1252 1249 1253 1250 TopologicalSortVisitor<Digraph, NodeMap> 1254 visitor(order, countNodes( digraph));1251 visitor(order, countNodes(graph)); 1255 1252 1256 1253 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> > 1257 dfs( digraph, visitor);1254 dfs(graph, visitor); 1258 1255 1259 1256 dfs.init(); 1260 for (NodeIt it( digraph); it != INVALID; ++it) {1257 for (NodeIt it(graph); it != INVALID; ++it) { 1261 1258 if (!dfs.reached(it)) { 1262 1259 dfs.addSource(it); 1263 1260 while (!dfs.emptyQueue()) { 1264 Arc arc= dfs.nextArc();1265 Node target = digraph.target(arc);1261 Arc edge = dfs.nextArc(); 1262 Node target = graph.target(edge); 1266 1263 if (dfs.reached(target) && order[target] == -1) { 1267 1264 return false; … … 1283 1280 /// \see acyclic 1284 1281 template <typename Digraph> 1285 bool dag(const Digraph& digraph) {1282 bool dag(const Digraph& graph) { 1286 1283 1287 1284 checkConcept<concepts::Digraph, Digraph>(); … … 1294 1291 1295 1292 typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>:: 1296 Create dfs( digraph);1297 1298 ProcessedMap processed( digraph);1293 Create dfs(graph); 1294 1295 ProcessedMap processed(graph); 1299 1296 dfs.processedMap(processed); 1300 1297 1301 1298 dfs.init(); 1302 for (NodeIt it( digraph); it != INVALID; ++it) {1299 for (NodeIt it(graph); it != INVALID; ++it) { 1303 1300 if (!dfs.reached(it)) { 1304 1301 dfs.addSource(it); 1305 1302 while (!dfs.emptyQueue()) { 1306 1303 Arc edge = dfs.nextArc(); 1307 Node target = digraph.target(edge);1304 Node target = graph.target(edge); 1308 1305 if (dfs.reached(target) && !processed[target]) { 1309 1306 return false; … … 1384 1381 } 1385 1382 1386 namespace _ connectivity_bits {1383 namespace _topology_bits { 1387 1384 1388 1385 template <typename Digraph> … … 1453 1450 template<typename Graph> 1454 1451 inline bool bipartite(const Graph &graph){ 1455 using namespace _ connectivity_bits;1452 using namespace _topology_bits; 1456 1453 1457 1454 checkConcept<concepts::Graph, Graph>(); … … 1493 1490 template<typename Graph, typename NodeMap> 1494 1491 inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ 1495 using namespace _ connectivity_bits;1492 using namespace _topology_bits; 1496 1493 1497 1494 checkConcept<concepts::Graph, Graph>(); … … 1524 1521 /// Returns true when there are not loop edges in the graph. 1525 1522 template <typename Digraph> 1526 bool loopFree(const Digraph& digraph) {1527 for (typename Digraph::ArcIt it( digraph); it != INVALID; ++it) {1528 if ( digraph.source(it) == digraph.target(it)) return false;1523 bool loopFree(const Digraph& graph) { 1524 for (typename Digraph::ArcIt it(graph); it != INVALID; ++it) { 1525 if (graph.source(it) == graph.target(it)) return false; 1529 1526 } 1530 1527 return true; … … 1535 1532 /// Returns true when there are not parallel edges in the graph. 1536 1533 template <typename Digraph> 1537 bool parallelFree(const Digraph& digraph) {1538 typename Digraph::template NodeMap<bool> reached( digraph, false);1539 for (typename Digraph::NodeIt n( digraph); n != INVALID; ++n) {1540 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {1541 if (reached[ digraph.target(a)]) return false;1542 reached.set( digraph.target(a), true);1543 } 1544 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {1545 reached.set( digraph.target(a), false);1534 bool parallelFree(const Digraph& graph) { 1535 typename Digraph::template NodeMap<bool> reached(graph, false); 1536 for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) { 1537 for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) { 1538 if (reached[graph.target(e)]) return false; 1539 reached.set(graph.target(e), true); 1540 } 1541 for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) { 1542 reached.set(graph.target(e), false); 1546 1543 } 1547 1544 } … … 1555 1552 /// the graph. 1556 1553 template <typename Digraph> 1557 bool simpleDigraph(const Digraph& digraph) {1558 typename Digraph::template NodeMap<bool> reached( digraph, false);1559 for (typename Digraph::NodeIt n( digraph); n != INVALID; ++n) {1554 bool simpleDigraph(const Digraph& graph) { 1555 typename Digraph::template NodeMap<bool> reached(graph, false); 1556 for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) { 1560 1557 reached.set(n, true); 1561 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {1562 if (reached[ digraph.target(a)]) return false;1563 reached.set( digraph.target(a), true);1564 } 1565 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {1566 reached.set( digraph.target(a), false);1558 for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) { 1559 if (reached[graph.target(e)]) return false; 1560 reached.set(graph.target(e), true); 1561 } 1562 for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) { 1563 reached.set(graph.target(e), false); 1567 1564 } 1568 1565 reached.set(n, false); … … 1573 1570 } //namespace lemon 1574 1571 1575 #endif //LEMON_ CONNECTIVITY_H1572 #endif //LEMON_TOPOLOGY_H -
lemon/dfs.h
r421 r420 1411 1411 } else { 1412 1412 _visitor->leave(s); 1413 _visitor->stop(s);1414 1413 } 1415 1414 }
Note: See TracChangeset
for help on using the changeset viewer.