COIN-OR::LEMON - Graph Library

Changes in / [421:0f2091856dab:420:6a2a33ad261b] in lemon-main


Ignore:
Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/connectivity.h

    r419 r417  
    1717 */
    1818
    19 #ifndef LEMON_CONNECTIVITY_H
    20 #define LEMON_CONNECTIVITY_H
     19#ifndef LEMON_TOPOLOGY_H
     20#define LEMON_TOPOLOGY_H
    2121
    2222#include <lemon/dfs.h>
     
    155155  }
    156156
    157   namespace _connectivity_bits {
     157  namespace _topology_bits {
    158158
    159159    template <typename Digraph, typename Iterator >
     
    189189
    190190    template <typename Digraph, typename ArcMap>
    191     struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
     191    struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
    192192    public:
    193193      typedef typename Digraph::Node Node;
    194194      typedef typename Digraph::Arc Arc;
    195195
    196       StronglyConnectedCutArcsVisitor(const Digraph& digraph,
    197                                       ArcMap& cutMap,
    198                                       int& cutNum)
     196      StronglyConnectedCutEdgesVisitor(const Digraph& digraph,
     197                                       ArcMap& cutMap,
     198                                       int& cutNum)
    199199        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
    200           _compMap(digraph, -1), _num(-1) {
    201       }
    202 
    203       void start(const Node&) {
     200          _compMap(digraph), _num(0) {
     201      }
     202
     203      void stop(const Node&) {
    204204        ++_num;
    205205      }
     
    249249    if (source == INVALID) return true;
    250250
    251     using namespace _connectivity_bits;
     251    using namespace _topology_bits;
    252252
    253253    typedef DfsVisitor<Digraph> Visitor;
     
    266266
    267267    typedef ReverseDigraph<const Digraph> RDigraph;
    268     typedef typename RDigraph::NodeIt RNodeIt;
    269268    RDigraph rdigraph(digraph);
    270269
     
    277276    rdfs.start();
    278277
    279     for (RNodeIt it(rdigraph); it != INVALID; ++it) {
     278    for (NodeIt it(rdigraph); it != INVALID; ++it) {
    280279      if (!rdfs.reached(it)) {
    281280        return false;
     
    304303    checkConcept<concepts::Digraph, Digraph>();
    305304
    306     using namespace _connectivity_bits;
     305    using namespace _topology_bits;
    307306
    308307    typedef typename Digraph::Node Node;
     
    376375    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
    377376
    378     using namespace _connectivity_bits;
     377    using namespace _topology_bits;
    379378
    380379    typedef std::vector<Node> Container;
     
    440439    checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
    441440
    442     using namespace _connectivity_bits;
     441    using namespace _topology_bits;
    443442
    444443    typedef std::vector<Node> Container;
     
    465464    int cutNum = 0;
    466465
    467     typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
     466    typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor;
    468467    RVisitor rvisitor(rgraph, cutMap, cutNum);
    469468
     
    480479  }
    481480
    482   namespace _connectivity_bits {
     481  namespace _topology_bits {
    483482
    484483    template <typename Digraph>
     
    732731    typedef typename Graph::NodeIt NodeIt;
    733732
    734     using namespace _connectivity_bits;
     733    using namespace _topology_bits;
    735734
    736735    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
     
    775774    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
    776775
    777     using namespace _connectivity_bits;
     776    using namespace _topology_bits;
    778777
    779778    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
     
    815814    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
    816815
    817     using namespace _connectivity_bits;
     816    using namespace _topology_bits;
    818817
    819818    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
     
    834833  }
    835834
    836   namespace _connectivity_bits {
     835  namespace _topology_bits {
    837836
    838837    template <typename Digraph>
     
    10551054    typedef typename Graph::NodeIt NodeIt;
    10561055
    1057     using namespace _connectivity_bits;
     1056    using namespace _topology_bits;
    10581057
    10591058    typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
     
    10971096    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
    10981097
    1099     using namespace _connectivity_bits;
     1098    using namespace _topology_bits;
    11001099
    11011100    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
     
    11381137    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
    11391138
    1140     using namespace _connectivity_bits;
     1139    using namespace _topology_bits;
    11411140
    11421141    typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
     
    11581157
    11591158
    1160   namespace _connectivity_bits {
     1159  namespace _topology_bits {
    11611160
    11621161    template <typename Digraph, typename IntNodeMap>
     
    11951194  template <typename Digraph, typename NodeMap>
    11961195  void topologicalSort(const Digraph& graph, NodeMap& order) {
    1197     using namespace _connectivity_bits;
     1196    using namespace _topology_bits;
    11981197
    11991198    checkConcept<concepts::Digraph, Digraph>();
     
    12361235  /// \see dag
    12371236  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;
    12401239
    12411240    checkConcept<concepts::Digraph, Digraph>();
     
    12471246    typedef typename Digraph::Arc Arc;
    12481247
    1249     for (NodeIt it(digraph); it != INVALID; ++it) {
    1250       order.set(it, -1);
    1251     }
     1248    order = constMap<Node, int, -1>();
    12521249
    12531250    TopologicalSortVisitor<Digraph, NodeMap>
    1254       visitor(order, countNodes(digraph));
     1251      visitor(order, countNodes(graph));
    12551252
    12561253    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
    1257       dfs(digraph, visitor);
     1254      dfs(graph, visitor);
    12581255
    12591256    dfs.init();
    1260     for (NodeIt it(digraph); it != INVALID; ++it) {
     1257    for (NodeIt it(graph); it != INVALID; ++it) {
    12611258      if (!dfs.reached(it)) {
    12621259        dfs.addSource(it);
    12631260        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);
    12661263           if (dfs.reached(target) && order[target] == -1) {
    12671264             return false;
     
    12831280  /// \see acyclic
    12841281  template <typename Digraph>
    1285   bool dag(const Digraph& digraph) {
     1282  bool dag(const Digraph& graph) {
    12861283
    12871284    checkConcept<concepts::Digraph, Digraph>();
     
    12941291
    12951292    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
    1296       Create dfs(digraph);
    1297 
    1298     ProcessedMap processed(digraph);
     1293      Create dfs(graph);
     1294
     1295    ProcessedMap processed(graph);
    12991296    dfs.processedMap(processed);
    13001297
    13011298    dfs.init();
    1302     for (NodeIt it(digraph); it != INVALID; ++it) {
     1299    for (NodeIt it(graph); it != INVALID; ++it) {
    13031300      if (!dfs.reached(it)) {
    13041301        dfs.addSource(it);
    13051302        while (!dfs.emptyQueue()) {
    13061303          Arc edge = dfs.nextArc();
    1307           Node target = digraph.target(edge);
     1304          Node target = graph.target(edge);
    13081305          if (dfs.reached(target) && !processed[target]) {
    13091306            return false;
     
    13841381  }
    13851382
    1386   namespace _connectivity_bits {
     1383  namespace _topology_bits {
    13871384
    13881385    template <typename Digraph>
     
    14531450  template<typename Graph>
    14541451  inline bool bipartite(const Graph &graph){
    1455     using namespace _connectivity_bits;
     1452    using namespace _topology_bits;
    14561453
    14571454    checkConcept<concepts::Graph, Graph>();
     
    14931490  template<typename Graph, typename NodeMap>
    14941491  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
    1495     using namespace _connectivity_bits;
     1492    using namespace _topology_bits;
    14961493
    14971494    checkConcept<concepts::Graph, Graph>();
     
    15241521  /// Returns true when there are not loop edges in the graph.
    15251522  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;
    15291526    }
    15301527    return true;
     
    15351532  /// Returns true when there are not parallel edges in the graph.
    15361533  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);
    15461543      }
    15471544    }
     
    15551552  /// the graph.
    15561553  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) {
    15601557      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);
    15671564      }
    15681565      reached.set(n, false);
     
    15731570} //namespace lemon
    15741571
    1575 #endif //LEMON_CONNECTIVITY_H
     1572#endif //LEMON_TOPOLOGY_H
  • lemon/dfs.h

    r421 r420  
    14111411          } else {
    14121412            _visitor->leave(s);
    1413             _visitor->stop(s);
    14141413          }
    14151414        }
Note: See TracChangeset for help on using the changeset viewer.