Changeset - r421:0f2091856dab
« 419:9afe81
« 420:6a2a33
422:62c1ed »
gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Merge
0 2 0
merge default
1 file changed with 65 insertions and 61 deletions:
lemon/connectivity.h
64
61
lemon/dfs.h
1
↑ Collapse diff ↑
lemon/connectivity.h
Show white space 6 line context
... ... 
@@ -18,4 +18,4 @@
18 18 

			




	19
	
	
		
#ifndef LEMON_TOPOLOGY_H


			




	20
	
	
		
#define LEMON_TOPOLOGY_H


			




	
	19
	
		
#ifndef LEMON_CONNECTIVITY_H


			




	
	20
	
		
#define LEMON_CONNECTIVITY_H


			




	21
	21
	
		

			




	...
	...
	
		
@@ -156,3 +156,3 @@


			




	156
	156
	
		

			




	157
	
	
		
  namespace _topology_bits {


			




	
	157
	
		
  namespace _connectivity_bits {


			




	158
	158
	
		

			




	...
	...
	
		
@@ -190,3 +190,3 @@


			




	190
	190
	
		
    template <typename Digraph, typename ArcMap>


			




	191
	
	
		
    struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {


			




	
	191
	
		
    struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {


			




	192
	192
	
		
    public:


			




	...
	...
	
		
@@ -195,10 +195,10 @@


			




	195
	195
	
		

			




	196
	
	
		
      StronglyConnectedCutEdgesVisitor(const Digraph& digraph,


			




	197
	
	
		
                                       ArcMap& cutMap,


			




	198
	
	
		
                                       int& cutNum)


			




	
	196
	
		
      StronglyConnectedCutArcsVisitor(const Digraph& digraph,


			




	
	197
	
		
                                      ArcMap& cutMap,


			




	
	198
	
		
                                      int& cutNum)


			




	199
	199
	
		
        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),


			




	200
	
	
		
          _compMap(digraph), _num(0) {


			




	
	200
	
		
          _compMap(digraph, -1), _num(-1) {


			




	201
	201
	
		
      }


			




	202
	202
	
		

			




	203
	
	
		
      void stop(const Node&) {


			




	
	203
	
		
      void start(const Node&) {


			




	204
	204
	
		
        ++_num;


			




	...
	...
	
		
@@ -250,3 +250,3 @@


			




	250
	250
	
		

			




	251
	
	
		
    using namespace _topology_bits;


			




	
	251
	
		
    using namespace _connectivity_bits;


			




	252
	252
	
		

			




	...
	...
	
		
@@ -267,2 +267,3 @@


			




	267
	267
	
		
    typedef ReverseDigraph<const Digraph> RDigraph;


			




	
	268
	
		
    typedef typename RDigraph::NodeIt RNodeIt;


			




	268
	269
	
		
    RDigraph rdigraph(digraph);


			




	...
	...
	
		
@@ -277,3 +278,3 @@


			




	277
	278
	
		

			




	278
	
	
		
    for (NodeIt it(rdigraph); it != INVALID; ++it) {


			




	
	279
	
		
    for (RNodeIt it(rdigraph); it != INVALID; ++it) {


			




	279
	280
	
		
      if (!rdfs.reached(it)) {


			




	...
	...
	
		
@@ -304,3 +305,3 @@


			




	304
	305
	
		

			




	305
	
	
		
    using namespace _topology_bits;


			




	
	306
	
		
    using namespace _connectivity_bits;


			




	306
	307
	
		

			




	...
	...
	
		
@@ -376,3 +377,3 @@


			




	376
	377
	
		

			




	377
	
	
		
    using namespace _topology_bits;


			




	
	378
	
		
    using namespace _connectivity_bits;


			




	378
	379
	
		

			




	...
	...
	
		
@@ -440,3 +441,3 @@


			




	440
	441
	
		

			




	441
	
	
		
    using namespace _topology_bits;


			




	
	442
	
		
    using namespace _connectivity_bits;


			




	442
	443
	
		

			




	...
	...
	
		
@@ -465,3 +466,3 @@


			




	465
	466
	
		

			




	466
	
	
		
    typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor;


			




	
	467
	
		
    typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;


			




	467
	468
	
		
    RVisitor rvisitor(rgraph, cutMap, cutNum);


			




	...
	...
	
		
@@ -480,3 +481,3 @@


			




	480
	481
	
		

			




	481
	
	
		
  namespace _topology_bits {


			




	
	482
	
		
  namespace _connectivity_bits {


			




	482
	483
	
		

			




	...
	...
	
		
@@ -732,3 +733,3 @@


			




	732
	733
	
		

			




	733
	
	
		
    using namespace _topology_bits;


			




	
	734
	
		
    using namespace _connectivity_bits;


			




	734
	735
	
		

			




	...
	...
	
		
@@ -775,3 +776,3 @@


			




	775
	776
	
		

			




	776
	
	
		
    using namespace _topology_bits;


			




	
	777
	
		
    using namespace _connectivity_bits;


			




	777
	778
	
		

			




	...
	...
	
		
@@ -815,3 +816,3 @@


			




	815
	816
	
		

			




	816
	
	
		
    using namespace _topology_bits;


			




	
	817
	
		
    using namespace _connectivity_bits;


			




	817
	818
	
		

			




	...
	...
	
		
@@ -834,3 +835,3 @@


			




	834
	835
	
		

			




	835
	
	
		
  namespace _topology_bits {


			




	
	836
	
		
  namespace _connectivity_bits {


			




	836
	837
	
		

			




	...
	...
	
		
@@ -1055,3 +1056,3 @@


			




	1055
	1056
	
		

			




	1056
	
	
		
    using namespace _topology_bits;


			




	
	1057
	
		
    using namespace _connectivity_bits;


			




	1057
	1058
	
		

			




	...
	...
	
		
@@ -1097,3 +1098,3 @@


			




	1097
	1098
	
		

			




	1098
	
	
		
    using namespace _topology_bits;


			




	
	1099
	
		
    using namespace _connectivity_bits;


			




	1099
	1100
	
		

			




	...
	...
	
		
@@ -1138,3 +1139,3 @@


			




	1138
	1139
	
		

			




	1139
	
	
		
    using namespace _topology_bits;


			




	
	1140
	
		
    using namespace _connectivity_bits;


			




	1140
	1141
	
		

			




	...
	...
	
		
@@ -1158,3 +1159,3 @@


			




	1158
	1159
	
		

			




	1159
	
	
		
  namespace _topology_bits {


			




	
	1160
	
		
  namespace _connectivity_bits {


			




	1160
	1161
	
		

			




	...
	...
	
		
@@ -1195,3 +1196,3 @@


			




	1195
	1196
	
		
  void topologicalSort(const Digraph& graph, NodeMap& order) {


			




	1196
	
	
		
    using namespace _topology_bits;


			




	
	1197
	
		
    using namespace _connectivity_bits;


			




	1197
	1198
	
		

			




	...
	...
	
		
@@ -1236,4 +1237,4 @@


			




	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
	
		

			




	...
	...
	
		
@@ -1247,12 +1248,14 @@


			




	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)) {


			




	...
	...
	
		
@@ -1260,4 +1263,4 @@


			




	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) {


			




	...
	...
	
		
@@ -1281,3 +1284,3 @@


			




	1281
	1284
	
		
  template <typename Digraph>


			




	1282
	
	
		
  bool dag(const Digraph& graph) {


			




	
	1285
	
		
  bool dag(const Digraph& digraph) {


			




	1283
	1286
	
		

			




	...
	...
	
		
@@ -1292,5 +1295,5 @@


			




	1292
	1295
	
		
    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::


			




	1293
	
	
		
      Create dfs(graph);


			




	
	1296
	
		
      Create dfs(digraph);


			




	1294
	1297
	
		

			




	1295
	
	
		
    ProcessedMap processed(graph);


			




	
	1298
	
		
    ProcessedMap processed(digraph);


			




	1296
	1299
	
		
    dfs.processedMap(processed);


			




	...
	...
	
		
@@ -1298,3 +1301,3 @@


			




	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)) {


			




	...
	...
	
		
@@ -1303,3 +1306,3 @@


			




	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]) {


			




	...
	...
	
		
@@ -1382,3 +1385,3 @@


			




	1382
	1385
	
		

			




	1383
	
	
		
  namespace _topology_bits {


			




	
	1386
	
		
  namespace _connectivity_bits {


			




	1384
	1387
	
		

			




	...
	...
	
		
@@ -1451,3 +1454,3 @@


			




	1451
	1454
	
		
  inline bool bipartite(const Graph &graph){


			




	1452
	
	
		
    using namespace _topology_bits;


			




	
	1455
	
		
    using namespace _connectivity_bits;


			




	1453
	1456
	
		

			




	...
	...
	
		
@@ -1491,3 +1494,3 @@


			




	1491
	1494
	
		
  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){


			




	1492
	
	
		
    using namespace _topology_bits;


			




	
	1495
	
		
    using namespace _connectivity_bits;


			




	1493
	1496
	
		

			




	...
	...
	
		
@@ -1522,5 +1525,5 @@


			




	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
	
		
    }


			




	...
	...
	
		
@@ -1533,11 +1536,11 @@


			




	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);


			




	
	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);


			




	1540
	1543
	
		
      }


			




	1541
	
	
		
      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {


			




	1542
	
	
		
        reached.set(graph.target(e), false);


			




	
	1544
	
		
      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {


			




	
	1545
	
		
        reached.set(digraph.target(a), false);


			




	1543
	1546
	
		
      }


			




	...
	...
	
		
@@ -1553,12 +1556,12 @@


			




	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
	
		
      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);


			




	1561
	1564
	
		
      }


			




	1562
	
	
		
      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {


			




	1563
	
	
		
        reached.set(graph.target(e), false);


			




	
	1565
	
		
      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {


			




	
	1566
	
		
        reached.set(digraph.target(a), false);


			




	1564
	1567
	
		
      }


			




	...
	...
	
		
@@ -1571,2 +1574,2 @@


			




	1571
	1574
	
		

			




	1572
	
	
		
#endif //LEMON_TOPOLOGY_H


			




	
	1575
	
		
#endif //LEMON_CONNECTIVITY_H

			




        

    

    

    

        

            

                

                    lemon/dfs.h
                

                

                  
                  
                  
                  Ignore white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -1412,2 +1412,3 @@


			




	1412
	1412
	
		
            _visitor->leave(s);


			




	
	1413
	
		
            _visitor->stop(s);


			




	1413
	1414
	
		
          }


			




        

    






    
    



    


    

     
    
0 comments (0 inline)