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