COIN-OR::LEMON - Graph Library

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


Ignore:
Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/connectivity.h

    r417 r419  
    1717 */
    1818
    19 #ifndef LEMON_TOPOLOGY_H
    20 #define LEMON_TOPOLOGY_H
     19#ifndef LEMON_CONNECTIVITY_H
     20#define LEMON_CONNECTIVITY_H
    2121
    2222#include <lemon/dfs.h>
     
    155155  }
    156156
    157   namespace _topology_bits {
     157  namespace _connectivity_bits {
    158158
    159159    template <typename Digraph, typename Iterator >
     
    189189
    190190    template <typename Digraph, typename ArcMap>
    191     struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
     191    struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
    192192    public:
    193193      typedef typename Digraph::Node Node;
    194194      typedef typename Digraph::Arc Arc;
    195195
    196       StronglyConnectedCutEdgesVisitor(const Digraph& digraph,
    197                                        ArcMap& cutMap,
    198                                        int& cutNum)
     196      StronglyConnectedCutArcsVisitor(const Digraph& digraph,
     197                                      ArcMap& cutMap,
     198                                      int& cutNum)
    199199        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
    200           _compMap(digraph), _num(0) {
    201       }
    202 
    203       void stop(const Node&) {
     200          _compMap(digraph, -1), _num(-1) {
     201      }
     202
     203      void start(const Node&) {
    204204        ++_num;
    205205      }
     
    249249    if (source == INVALID) return true;
    250250
    251     using namespace _topology_bits;
     251    using namespace _connectivity_bits;
    252252
    253253    typedef DfsVisitor<Digraph> Visitor;
     
    266266
    267267    typedef ReverseDigraph<const Digraph> RDigraph;
     268    typedef typename RDigraph::NodeIt RNodeIt;
    268269    RDigraph rdigraph(digraph);
    269270
     
    276277    rdfs.start();
    277278
    278     for (NodeIt it(rdigraph); it != INVALID; ++it) {
     279    for (RNodeIt it(rdigraph); it != INVALID; ++it) {
    279280      if (!rdfs.reached(it)) {
    280281        return false;
     
    303304    checkConcept<concepts::Digraph, Digraph>();
    304305
    305     using namespace _topology_bits;
     306    using namespace _connectivity_bits;
    306307
    307308    typedef typename Digraph::Node Node;
     
    375376    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
    376377
    377     using namespace _topology_bits;
     378    using namespace _connectivity_bits;
    378379
    379380    typedef std::vector<Node> Container;
     
    439440    checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
    440441
    441     using namespace _topology_bits;
     442    using namespace _connectivity_bits;
    442443
    443444    typedef std::vector<Node> Container;
     
    464465    int cutNum = 0;
    465466
    466     typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor;
     467    typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
    467468    RVisitor rvisitor(rgraph, cutMap, cutNum);
    468469
     
    479480  }
    480481
    481   namespace _topology_bits {
     482  namespace _connectivity_bits {
    482483
    483484    template <typename Digraph>
     
    731732    typedef typename Graph::NodeIt NodeIt;
    732733
    733     using namespace _topology_bits;
     734    using namespace _connectivity_bits;
    734735
    735736    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
     
    774775    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
    775776
    776     using namespace _topology_bits;
     777    using namespace _connectivity_bits;
    777778
    778779    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
     
    814815    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
    815816
    816     using namespace _topology_bits;
     817    using namespace _connectivity_bits;
    817818
    818819    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
     
    833834  }
    834835
    835   namespace _topology_bits {
     836  namespace _connectivity_bits {
    836837
    837838    template <typename Digraph>
     
    10541055    typedef typename Graph::NodeIt NodeIt;
    10551056
    1056     using namespace _topology_bits;
     1057    using namespace _connectivity_bits;
    10571058
    10581059    typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
     
    10961097    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
    10971098
    1098     using namespace _topology_bits;
     1099    using namespace _connectivity_bits;
    10991100
    11001101    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
     
    11371138    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
    11381139
    1139     using namespace _topology_bits;
     1140    using namespace _connectivity_bits;
    11401141
    11411142    typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
     
    11571158
    11581159
    1159   namespace _topology_bits {
     1160  namespace _connectivity_bits {
    11601161
    11611162    template <typename Digraph, typename IntNodeMap>
     
    11941195  template <typename Digraph, typename NodeMap>
    11951196  void topologicalSort(const Digraph& graph, NodeMap& order) {
    1196     using namespace _topology_bits;
     1197    using namespace _connectivity_bits;
    11971198
    11981199    checkConcept<concepts::Digraph, Digraph>();
     
    12351236  /// \see dag
    12361237  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;
    12391240
    12401241    checkConcept<concepts::Digraph, Digraph>();
     
    12461247    typedef typename Digraph::Arc Arc;
    12471248
    1248     order = constMap<Node, int, -1>();
     1249    for (NodeIt it(digraph); it != INVALID; ++it) {
     1250      order.set(it, -1);
     1251    }
    12491252
    12501253    TopologicalSortVisitor<Digraph, NodeMap>
    1251       visitor(order, countNodes(graph));
     1254      visitor(order, countNodes(digraph));
    12521255
    12531256    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
    1254       dfs(graph, visitor);
     1257      dfs(digraph, visitor);
    12551258
    12561259    dfs.init();
    1257     for (NodeIt it(graph); it != INVALID; ++it) {
     1260    for (NodeIt it(digraph); it != INVALID; ++it) {
    12581261      if (!dfs.reached(it)) {
    12591262        dfs.addSource(it);
    12601263        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);
    12631266           if (dfs.reached(target) && order[target] == -1) {
    12641267             return false;
     
    12801283  /// \see acyclic
    12811284  template <typename Digraph>
    1282   bool dag(const Digraph& graph) {
     1285  bool dag(const Digraph& digraph) {
    12831286
    12841287    checkConcept<concepts::Digraph, Digraph>();
     
    12911294
    12921295    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
    1293       Create dfs(graph);
    1294 
    1295     ProcessedMap processed(graph);
     1296      Create dfs(digraph);
     1297
     1298    ProcessedMap processed(digraph);
    12961299    dfs.processedMap(processed);
    12971300
    12981301    dfs.init();
    1299     for (NodeIt it(graph); it != INVALID; ++it) {
     1302    for (NodeIt it(digraph); it != INVALID; ++it) {
    13001303      if (!dfs.reached(it)) {
    13011304        dfs.addSource(it);
    13021305        while (!dfs.emptyQueue()) {
    13031306          Arc edge = dfs.nextArc();
    1304           Node target = graph.target(edge);
     1307          Node target = digraph.target(edge);
    13051308          if (dfs.reached(target) && !processed[target]) {
    13061309            return false;
     
    13811384  }
    13821385
    1383   namespace _topology_bits {
     1386  namespace _connectivity_bits {
    13841387
    13851388    template <typename Digraph>
     
    14501453  template<typename Graph>
    14511454  inline bool bipartite(const Graph &graph){
    1452     using namespace _topology_bits;
     1455    using namespace _connectivity_bits;
    14531456
    14541457    checkConcept<concepts::Graph, Graph>();
     
    14901493  template<typename Graph, typename NodeMap>
    14911494  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
    1492     using namespace _topology_bits;
     1495    using namespace _connectivity_bits;
    14931496
    14941497    checkConcept<concepts::Graph, Graph>();
     
    15211524  /// Returns true when there are not loop edges in the graph.
    15221525  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;
    15261529    }
    15271530    return true;
     
    15321535  /// Returns true when there are not parallel edges in the graph.
    15331536  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);
    15431546      }
    15441547    }
     
    15521555  /// the graph.
    15531556  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) {
    15571560      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);
    15641567      }
    15651568      reached.set(n, false);
     
    15701573} //namespace lemon
    15711574
    1572 #endif //LEMON_TOPOLOGY_H
     1575#endif //LEMON_CONNECTIVITY_H
  • lemon/dfs.h

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