COIN-OR::LEMON - Graph Library

Changeset 209:765619b7cbb2 in lemon-1.2 for lemon/bits/graph_extender.h


Ignore:
Timestamp:
07/13/08 20:51:02 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/graph_extender.h

    r125 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
     
    6767    Node oppositeNode(const Node &node, const Arc &arc) const {
    6868      if (node == Parent::source(arc))
    69         return Parent::target(arc);
     69        return Parent::target(arc);
    7070      else if(node == Parent::target(arc))
    71         return Parent::source(arc);
     71        return Parent::source(arc);
    7272      else
    73         return INVALID;
     73        return INVALID;
    7474    }
    7575
     
    9090      return node_notifier;
    9191    }
    92    
     92
    9393    ArcNotifier& notifier(Arc) const {
    9494      return arc_notifier;
    9595    }
    9696
    97     class NodeIt : public Node { 
     97    class NodeIt : public Node {
    9898      const Digraph* _digraph;
    9999    public:
     
    104104
    105105      explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
    106         _digraph->first(static_cast<Node&>(*this));
    107       }
    108 
    109       NodeIt(const Digraph& digraph, const Node& node) 
    110         : Node(node), _digraph(&digraph) {}
    111 
    112       NodeIt& operator++() { 
    113         _digraph->next(*this);
    114         return *this;
    115       }
    116 
    117     };
    118 
    119 
    120     class ArcIt : public Arc { 
     106        _digraph->first(static_cast<Node&>(*this));
     107      }
     108
     109      NodeIt(const Digraph& digraph, const Node& node)
     110        : Node(node), _digraph(&digraph) {}
     111
     112      NodeIt& operator++() {
     113        _digraph->next(*this);
     114        return *this;
     115      }
     116
     117    };
     118
     119
     120    class ArcIt : public Arc {
    121121      const Digraph* _digraph;
    122122    public:
     
    127127
    128128      explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
    129         _digraph->first(static_cast<Arc&>(*this));
    130       }
    131 
    132       ArcIt(const Digraph& digraph, const Arc& arc) : 
    133         Arc(arc), _digraph(&digraph) { }
    134 
    135       ArcIt& operator++() { 
    136         _digraph->next(*this);
    137         return *this;
    138       }
    139 
    140     };
    141 
    142 
    143     class OutArcIt : public Arc { 
     129        _digraph->first(static_cast<Arc&>(*this));
     130      }
     131
     132      ArcIt(const Digraph& digraph, const Arc& arc) :
     133        Arc(arc), _digraph(&digraph) { }
     134
     135      ArcIt& operator++() {
     136        _digraph->next(*this);
     137        return *this;
     138      }
     139
     140    };
     141
     142
     143    class OutArcIt : public Arc {
    144144      const Digraph* _digraph;
    145145    public:
     
    149149      OutArcIt(Invalid i) : Arc(i) { }
    150150
    151       OutArcIt(const Digraph& digraph, const Node& node) 
    152         : _digraph(&digraph) {
    153         _digraph->firstOut(*this, node);
    154       }
    155 
    156       OutArcIt(const Digraph& digraph, const Arc& arc) 
    157         : Arc(arc), _digraph(&digraph) {}
    158 
    159       OutArcIt& operator++() { 
    160         _digraph->nextOut(*this);
    161         return *this;
    162       }
    163 
    164     };
    165 
    166 
    167     class InArcIt : public Arc { 
     151      OutArcIt(const Digraph& digraph, const Node& node)
     152        : _digraph(&digraph) {
     153        _digraph->firstOut(*this, node);
     154      }
     155
     156      OutArcIt(const Digraph& digraph, const Arc& arc)
     157        : Arc(arc), _digraph(&digraph) {}
     158
     159      OutArcIt& operator++() {
     160        _digraph->nextOut(*this);
     161        return *this;
     162      }
     163
     164    };
     165
     166
     167    class InArcIt : public Arc {
    168168      const Digraph* _digraph;
    169169    public:
     
    173173      InArcIt(Invalid i) : Arc(i) { }
    174174
    175       InArcIt(const Digraph& digraph, const Node& node) 
    176         : _digraph(&digraph) {
    177         _digraph->firstIn(*this, node);
    178       }
    179 
    180       InArcIt(const Digraph& digraph, const Arc& arc) : 
    181         Arc(arc), _digraph(&digraph) {}
    182 
    183       InArcIt& operator++() { 
    184         _digraph->nextIn(*this);
    185         return *this;
     175      InArcIt(const Digraph& digraph, const Node& node)
     176        : _digraph(&digraph) {
     177        _digraph->firstIn(*this, node);
     178      }
     179
     180      InArcIt(const Digraph& digraph, const Arc& arc) :
     181        Arc(arc), _digraph(&digraph) {}
     182
     183      InArcIt& operator++() {
     184        _digraph->nextIn(*this);
     185        return *this;
    186186      }
    187187
     
    216216    }
    217217
    218    
     218
    219219    template <typename _Value>
    220     class NodeMap 
     220    class NodeMap
    221221      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
    222222    public:
     
    224224      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
    225225
    226       explicit NodeMap(const Digraph& digraph) 
    227         : Parent(digraph) {}
    228       NodeMap(const Digraph& digraph, const _Value& value) 
    229         : Parent(digraph, value) {}
     226      explicit NodeMap(const Digraph& digraph)
     227        : Parent(digraph) {}
     228      NodeMap(const Digraph& digraph, const _Value& value)
     229        : Parent(digraph, value) {}
    230230
    231231      NodeMap& operator=(const NodeMap& cmap) {
    232         return operator=<NodeMap>(cmap);
     232        return operator=<NodeMap>(cmap);
    233233      }
    234234
     
    236236      NodeMap& operator=(const CMap& cmap) {
    237237        Parent::operator=(cmap);
    238         return *this;
     238        return *this;
    239239      }
    240240
     
    242242
    243243    template <typename _Value>
    244     class ArcMap 
     244    class ArcMap
    245245      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    246246    public:
     
    248248      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    249249
    250       explicit ArcMap(const Digraph& digraph) 
    251         : Parent(digraph) {}
    252       ArcMap(const Digraph& digraph, const _Value& value) 
    253         : Parent(digraph, value) {}
     250      explicit ArcMap(const Digraph& digraph)
     251        : Parent(digraph) {}
     252      ArcMap(const Digraph& digraph, const _Value& value)
     253        : Parent(digraph, value) {}
    254254
    255255      ArcMap& operator=(const ArcMap& cmap) {
    256         return operator=<ArcMap>(cmap);
     256        return operator=<ArcMap>(cmap);
    257257      }
    258258
     
    260260      ArcMap& operator=(const CMap& cmap) {
    261261        Parent::operator=(cmap);
    262         return *this;
     262        return *this;
    263263      }
    264264    };
     
    270270      return node;
    271271    }
    272    
     272
    273273    Arc addArc(const Node& from, const Node& to) {
    274274      Arc arc = Parent::addArc(from, to);
     
    294294      Parent::firstOut(arc, node);
    295295      while (arc != INVALID ) {
    296         erase(arc);
    297         Parent::firstOut(arc, node);
    298       } 
     296        erase(arc);
     297        Parent::firstOut(arc, node);
     298      }
    299299
    300300      Parent::firstIn(arc, node);
    301301      while (arc != INVALID ) {
    302         erase(arc);
    303         Parent::firstIn(arc, node);
     302        erase(arc);
     303        Parent::firstIn(arc, node);
    304304      }
    305305
     
    307307      Parent::erase(node);
    308308    }
    309    
     309
    310310    void erase(const Arc& arc) {
    311311      notifier(Arc()).erase(arc);
     
    316316      node_notifier.setContainer(*this);
    317317      arc_notifier.setContainer(*this);
    318     } 
    319    
     318    }
     319
    320320
    321321    ~DigraphExtender() {
     
    328328  ///
    329329  /// \brief Extender for the Graphs
    330   template <typename Base> 
     330  template <typename Base>
    331331  class GraphExtender : public Base {
    332332  public:
    333    
     333
    334334    typedef Base Parent;
    335335    typedef GraphExtender Graph;
     
    341341    typedef typename Parent::Edge Edge;
    342342
    343     // Graph extension   
     343    // Graph extension
    344344
    345345    int maxId(Node) const {
     
    369369    Node oppositeNode(const Node &n, const Edge &e) const {
    370370      if( n == Parent::u(e))
    371         return Parent::v(e);
     371        return Parent::v(e);
    372372      else if( n == Parent::v(e))
    373         return Parent::u(e);
     373        return Parent::u(e);
    374374      else
    375         return INVALID;
     375        return INVALID;
    376376    }
    377377
     
    403403      return node_notifier;
    404404    }
    405    
     405
    406406    ArcNotifier& notifier(Arc) const {
    407407      return arc_notifier;
     
    414414
    415415
    416     class NodeIt : public Node { 
     416    class NodeIt : public Node {
    417417      const Graph* _graph;
    418418    public:
     
    423423
    424424      explicit NodeIt(const Graph& graph) : _graph(&graph) {
    425         _graph->first(static_cast<Node&>(*this));
    426       }
    427 
    428       NodeIt(const Graph& graph, const Node& node) 
    429         : Node(node), _graph(&graph) {}
    430 
    431       NodeIt& operator++() { 
    432         _graph->next(*this);
    433         return *this;
    434       }
    435 
    436     };
    437 
    438 
    439     class ArcIt : public Arc { 
     425        _graph->first(static_cast<Node&>(*this));
     426      }
     427
     428      NodeIt(const Graph& graph, const Node& node)
     429        : Node(node), _graph(&graph) {}
     430
     431      NodeIt& operator++() {
     432        _graph->next(*this);
     433        return *this;
     434      }
     435
     436    };
     437
     438
     439    class ArcIt : public Arc {
    440440      const Graph* _graph;
    441441    public:
     
    446446
    447447      explicit ArcIt(const Graph& graph) : _graph(&graph) {
    448         _graph->first(static_cast<Arc&>(*this));
    449       }
    450 
    451       ArcIt(const Graph& graph, const Arc& arc) : 
    452         Arc(arc), _graph(&graph) { }
    453 
    454       ArcIt& operator++() { 
    455         _graph->next(*this);
    456         return *this;
    457       }
    458 
    459     };
    460 
    461 
    462     class OutArcIt : public Arc { 
     448        _graph->first(static_cast<Arc&>(*this));
     449      }
     450
     451      ArcIt(const Graph& graph, const Arc& arc) :
     452        Arc(arc), _graph(&graph) { }
     453
     454      ArcIt& operator++() {
     455        _graph->next(*this);
     456        return *this;
     457      }
     458
     459    };
     460
     461
     462    class OutArcIt : public Arc {
    463463      const Graph* _graph;
    464464    public:
     
    468468      OutArcIt(Invalid i) : Arc(i) { }
    469469
    470       OutArcIt(const Graph& graph, const Node& node) 
    471         : _graph(&graph) {
    472         _graph->firstOut(*this, node);
    473       }
    474 
    475       OutArcIt(const Graph& graph, const Arc& arc) 
    476         : Arc(arc), _graph(&graph) {}
    477 
    478       OutArcIt& operator++() { 
    479         _graph->nextOut(*this);
    480         return *this;
    481       }
    482 
    483     };
    484 
    485 
    486     class InArcIt : public Arc { 
     470      OutArcIt(const Graph& graph, const Node& node)
     471        : _graph(&graph) {
     472        _graph->firstOut(*this, node);
     473      }
     474
     475      OutArcIt(const Graph& graph, const Arc& arc)
     476        : Arc(arc), _graph(&graph) {}
     477
     478      OutArcIt& operator++() {
     479        _graph->nextOut(*this);
     480        return *this;
     481      }
     482
     483    };
     484
     485
     486    class InArcIt : public Arc {
    487487      const Graph* _graph;
    488488    public:
     
    492492      InArcIt(Invalid i) : Arc(i) { }
    493493
    494       InArcIt(const Graph& graph, const Node& node) 
    495         : _graph(&graph) {
    496         _graph->firstIn(*this, node);
    497       }
    498 
    499       InArcIt(const Graph& graph, const Arc& arc) : 
    500         Arc(arc), _graph(&graph) {}
    501 
    502       InArcIt& operator++() { 
    503         _graph->nextIn(*this);
    504         return *this;
    505       }
    506 
    507     };
    508 
    509 
    510     class EdgeIt : public Parent::Edge { 
     494      InArcIt(const Graph& graph, const Node& node)
     495        : _graph(&graph) {
     496        _graph->firstIn(*this, node);
     497      }
     498
     499      InArcIt(const Graph& graph, const Arc& arc) :
     500        Arc(arc), _graph(&graph) {}
     501
     502      InArcIt& operator++() {
     503        _graph->nextIn(*this);
     504        return *this;
     505      }
     506
     507    };
     508
     509
     510    class EdgeIt : public Parent::Edge {
    511511      const Graph* _graph;
    512512    public:
     
    517517
    518518      explicit EdgeIt(const Graph& graph) : _graph(&graph) {
    519         _graph->first(static_cast<Edge&>(*this));
    520       }
    521 
    522       EdgeIt(const Graph& graph, const Edge& edge) : 
    523         Edge(edge), _graph(&graph) { }
    524 
    525       EdgeIt& operator++() { 
    526         _graph->next(*this);
    527         return *this;
     519        _graph->first(static_cast<Edge&>(*this));
     520      }
     521
     522      EdgeIt(const Graph& graph, const Edge& edge) :
     523        Edge(edge), _graph(&graph) { }
     524
     525      EdgeIt& operator++() {
     526        _graph->next(*this);
     527        return *this;
    528528      }
    529529
     
    541541
    542542      IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
    543         _graph->firstInc(*this, _direction, node);
     543        _graph->firstInc(*this, _direction, node);
    544544      }
    545545
    546546      IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
    547         : _graph(&graph), Edge(edge) {
    548         _direction = (_graph->source(edge) == node);
     547        : _graph(&graph), Edge(edge) {
     548        _direction = (_graph->source(edge) == node);
    549549      }
    550550
    551551      IncEdgeIt& operator++() {
    552         _graph->nextInc(*this, _direction);
    553         return *this;
     552        _graph->nextInc(*this, _direction);
     553        return *this;
    554554      }
    555555    };
     
    599599
    600600    template <typename _Value>
    601     class NodeMap 
     601    class NodeMap
    602602      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
    603603    public:
     
    605605      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    606606
    607       NodeMap(const Graph& graph) 
    608         : Parent(graph) {}
    609       NodeMap(const Graph& graph, const _Value& value) 
    610         : Parent(graph, value) {}
     607      NodeMap(const Graph& graph)
     608        : Parent(graph) {}
     609      NodeMap(const Graph& graph, const _Value& value)
     610        : Parent(graph, value) {}
    611611
    612612      NodeMap& operator=(const NodeMap& cmap) {
    613         return operator=<NodeMap>(cmap);
     613        return operator=<NodeMap>(cmap);
    614614      }
    615615
     
    617617      NodeMap& operator=(const CMap& cmap) {
    618618        Parent::operator=(cmap);
    619         return *this;
     619        return *this;
    620620      }
    621621
     
    623623
    624624    template <typename _Value>
    625     class ArcMap 
     625    class ArcMap
    626626      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    627627    public:
     
    629629      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    630630
    631       ArcMap(const Graph& graph) 
    632         : Parent(graph) {}
    633       ArcMap(const Graph& graph, const _Value& value) 
    634         : Parent(graph, value) {}
     631      ArcMap(const Graph& graph)
     632        : Parent(graph) {}
     633      ArcMap(const Graph& graph, const _Value& value)
     634        : Parent(graph, value) {}
    635635
    636636      ArcMap& operator=(const ArcMap& cmap) {
    637         return operator=<ArcMap>(cmap);
     637        return operator=<ArcMap>(cmap);
    638638      }
    639639
     
    641641      ArcMap& operator=(const CMap& cmap) {
    642642        Parent::operator=(cmap);
    643         return *this;
     643        return *this;
    644644      }
    645645    };
     
    647647
    648648    template <typename _Value>
    649     class EdgeMap 
     649    class EdgeMap
    650650      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    651651    public:
     
    653653      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    654654
    655       EdgeMap(const Graph& graph) 
    656         : Parent(graph) {}
    657 
    658       EdgeMap(const Graph& graph, const _Value& value) 
    659         : Parent(graph, value) {}
     655      EdgeMap(const Graph& graph)
     656        : Parent(graph) {}
     657
     658      EdgeMap(const Graph& graph, const _Value& value)
     659        : Parent(graph, value) {}
    660660
    661661      EdgeMap& operator=(const EdgeMap& cmap) {
    662         return operator=<EdgeMap>(cmap);
     662        return operator=<EdgeMap>(cmap);
    663663      }
    664664
     
    666666      EdgeMap& operator=(const CMap& cmap) {
    667667        Parent::operator=(cmap);
    668         return *this;
     668        return *this;
    669669      }
    670670
     
    684684      std::vector<Arc> ev;
    685685      ev.push_back(Parent::direct(edge, true));
    686       ev.push_back(Parent::direct(edge, false));     
     686      ev.push_back(Parent::direct(edge, false));
    687687      notifier(Arc()).add(ev);
    688688      return edge;
    689689    }
    690    
     690
    691691    void clear() {
    692692      notifier(Arc()).clear();
     
    697697
    698698    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
    699     void build(const Graph& graph, NodeRefMap& nodeRef, 
     699    void build(const Graph& graph, NodeRefMap& nodeRef,
    700700               EdgeRefMap& edgeRef) {
    701701      Parent::build(graph, nodeRef, edgeRef);
     
    709709      Parent::firstOut(arc, node);
    710710      while (arc != INVALID ) {
    711         erase(arc);
    712         Parent::firstOut(arc, node);
    713       } 
     711        erase(arc);
     712        Parent::firstOut(arc, node);
     713      }
    714714
    715715      Parent::firstIn(arc, node);
    716716      while (arc != INVALID ) {
    717         erase(arc);
    718         Parent::firstIn(arc, node);
     717        erase(arc);
     718        Parent::firstIn(arc, node);
    719719      }
    720720
     
    726726      std::vector<Arc> av;
    727727      av.push_back(Parent::direct(edge, true));
    728       av.push_back(Parent::direct(edge, false));     
     728      av.push_back(Parent::direct(edge, false));
    729729      notifier(Arc()).erase(av);
    730730      notifier(Edge()).erase(edge);
     
    733733
    734734    GraphExtender() {
    735       node_notifier.setContainer(*this); 
     735      node_notifier.setContainer(*this);
    736736      arc_notifier.setContainer(*this);
    737737      edge_notifier.setContainer(*this);
    738     } 
     738    }
    739739
    740740    ~GraphExtender() {
    741741      edge_notifier.clear();
    742742      arc_notifier.clear();
    743       node_notifier.clear(); 
    744     } 
     743      node_notifier.clear();
     744    }
    745745
    746746  };
Note: See TracChangeset for help on using the changeset viewer.