COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 209:765619b7cbb2 in lemon-main for lemon/smart_graph.h


Ignore:
Timestamp:
07/13/08 20:51:02 (17 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/smart_graph.h

    r157 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
    … …  
    4646  protected:
    4747
    48     struct NodeT 
     48    struct NodeT
    4949    {
    50       int first_in, first_out;     
     50      int first_in, first_out;
    5151      NodeT() {}
    5252    };
    53     struct ArcT 
     53    struct ArcT
    5454    {
    55       int target, source, next_in, next_out;     
    56       ArcT() {} 
     55      int target, source, next_in, next_out;
     56      ArcT() {}
    5757    };
    5858
    5959    std::vector<NodeT> nodes;
    6060    std::vector<ArcT> arcs;
    61        
     61
    6262  public:
    6363
    … …  
    7070
    7171    SmartDigraphBase() : nodes(), arcs() { }
    72     SmartDigraphBase(const SmartDigraphBase &_g) 
     72    SmartDigraphBase(const SmartDigraphBase &_g)
    7373      : nodes(_g.nodes), arcs(_g.arcs) { }
    74    
     74
    7575    typedef True NodeNumTag;
    7676    typedef True EdgeNumTag;
    … …  
    8383
    8484    Node addNode() {
    85       int n = nodes.size();     
     85      int n = nodes.size();
    8686      nodes.push_back(NodeT());
    8787      nodes[n].first_in = -1;
    … …  
    8989      return Node(n);
    9090    }
    91    
     91
    9292    Arc addArc(Node u, Node v) {
    93       int n = arcs.size(); 
     93      int n = arcs.size();
    9494      arcs.push_back(ArcT());
    95       arcs[n].source = u._id; 
     95      arcs[n].source = u._id;
    9696      arcs[n].target = v._id;
    9797      arcs[n].next_out = nodes[u._id].first_out;
    … …  
    116116    static Arc arcFromId(int id) { return Arc(id);}
    117117
    118     bool valid(Node n) const { 
    119       return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 
    120     }
    121     bool valid(Arc a) const { 
    122       return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 
     118    bool valid(Node n) const {
     119      return n._id >= 0 && n._id < static_cast<int>(nodes.size());
     120    }
     121    bool valid(Arc a) const {
     122      return a._id >= 0 && a._id < static_cast<int>(arcs.size());
    123123    }
    124124
    … …  
    137137      bool operator<(const Node i) const {return _id < i._id;}
    138138    };
    139    
     139
    140140
    141141    class Arc {
    … …  
    181181      arc._id = nodes[node._id].first_in;
    182182    }
    183    
     183
    184184    void nextIn(Arc& arc) const {
    185185      arc._id = arcs[arc._id].next_in;
    … …  
    223223
    224224  public:
    225    
     225
    226226    /// Constructor
    227    
     227
    228228    /// Constructor.
    229229    ///
    230230    SmartDigraph() {};
    231    
     231
    232232    ///Add a new node to the digraph.
    233    
     233
    234234    /// \return the new node.
    235235    ///
    236236    Node addNode() { return Parent::addNode(); }
    237    
     237
    238238    ///Add a new arc to the digraph.
    239    
     239
    240240    ///Add a new arc to the digraph with source node \c s
    241241    ///and target node \c t.
    242242    ///\return the new arc.
    243     Arc addArc(const Node& s, const Node& t) { 
    244       return Parent::addArc(s, t); 
     243    Arc addArc(const Node& s, const Node& t) {
     244      return Parent::addArc(s, t);
    245245    }
    246246
    … …  
    270270    ///
    271271    /// This function gives back true if the given node is valid,
    272     /// ie. it is a real node of the graph. 
     272    /// ie. it is a real node of the graph.
    273273    ///
    274274    /// \warning A removed node (using Snapshot) could become valid again
    … …  
    279279    ///
    280280    /// This function gives back true if the given arc is valid,
    281     /// ie. it is a real arc of the graph. 
     281    /// ie. it is a real arc of the graph.
    282282    ///
    283283    /// \warning A removed arc (using Snapshot) could become valid again
    … …  
    286286
    287287    ///Clear the digraph.
    288    
     288
    289289    ///Erase all the nodes and arcs from the digraph.
    290290    ///
    … …  
    294294
    295295    ///Split a node.
    296    
     296
    297297    ///This function splits a node. First a new node is added to the digraph,
    298298    ///then the source of each outgoing arc of \c n is moved to this new node.
    … …  
    319319
    320320  public:
    321    
     321
    322322    class Snapshot;
    323323
    … …  
    328328      while(s.arc_num<arcs.size()) {
    329329        Arc arc = arcFromId(arcs.size()-1);
    330         Parent::notifier(Arc()).erase(arc);
    331         nodes[arcs.back().source].first_out=arcs.back().next_out;
    332         nodes[arcs.back().target].first_in=arcs.back().next_in;
    333         arcs.pop_back();
     330        Parent::notifier(Arc()).erase(arc);
     331        nodes[arcs.back().source].first_out=arcs.back().next_out;
     332        nodes[arcs.back().target].first_in=arcs.back().next_in;
     333        arcs.pop_back();
    334334      }
    335335      while(s.node_num<nodes.size()) {
    336336        Node node = nodeFromId(nodes.size()-1);
    337         Parent::notifier(Node()).erase(node);
    338         nodes.pop_back();
    339       }
    340     }   
     337        Parent::notifier(Node()).erase(node);
     338        nodes.pop_back();
     339      }
     340    }
    341341
    342342  public:
    … …  
    356356    ///not the restored digraph or no change. Because the runtime performance
    357357    ///the validity of the snapshot is not stored.
    358     class Snapshot 
     358    class Snapshot
    359359    {
    360360      SmartDigraph *_graph;
    … …  
    365365    public:
    366366      ///Default constructor.
    367      
     367
    368368      ///Default constructor.
    369369      ///To actually make a snapshot you must call save().
    … …  
    371371      Snapshot() : _graph(0) {}
    372372      ///Constructor that immediately makes a snapshot
    373      
     373
    374374      ///This constructor immediately makes a snapshot of the digraph.
    375375      ///\param _g The digraph we make a snapshot of.
    376376      Snapshot(SmartDigraph &graph) : _graph(&graph) {
    377         node_num=_graph->nodes.size();
    378         arc_num=_graph->arcs.size();
     377        node_num=_graph->nodes.size();
     378        arc_num=_graph->arcs.size();
    379379      }
    380380
    … …  
    386386      ///call, the previous snapshot gets lost.
    387387      ///\param _g The digraph we make the snapshot of.
    388       void save(SmartDigraph &graph) 
     388      void save(SmartDigraph &graph)
    389389      {
    390         _graph=&graph;
    391         node_num=_graph->nodes.size();
    392         arc_num=_graph->arcs.size();
     390        _graph=&graph;
     391        node_num=_graph->nodes.size();
     392        arc_num=_graph->arcs.size();
    393393      }
    394394
    395395      ///Undo the changes until a snapshot.
    396      
     396
    397397      ///Undo the changes until a snapshot created by save().
    398398      ///
    … …  
    402402      void restore()
    403403      {
    404         _graph->restoreSnapshot(*this);
     404        _graph->restoreSnapshot(*this);
    405405      }
    406406    };
    … …  
    415415      int first_out;
    416416    };
    417  
     417
    418418    struct ArcT {
    419419      int target;
    … …  
    425425
    426426    int first_free_arc;
    427    
    428   public:
    429    
     427
     428  public:
     429
    430430    typedef SmartGraphBase Digraph;
    431431
    … …  
    433433    class Arc;
    434434    class Edge;
    435    
     435
    436436    class Node {
    437437      friend class SmartGraphBase;
    … …  
    486486      : nodes(), arcs() {}
    487487
    488    
    489     int maxNodeId() const { return nodes.size()-1; } 
     488
     489    int maxNodeId() const { return nodes.size()-1; }
    490490    int maxEdgeId() const { return arcs.size() / 2 - 1; }
    491491    int maxArcId() const { return arcs.size()-1; }
    … …  
    505505    }
    506506
    507     void first(Node& node) const { 
     507    void first(Node& node) const {
    508508      node._id = nodes.size() - 1;
    509509    }
    … …  
    513513    }
    514514
    515     void first(Arc& arc) const { 
     515    void first(Arc& arc) const {
    516516      arc._id = arcs.size() - 1;
    517517    }
    … …  
    521521    }
    522522
    523     void first(Edge& arc) const { 
     523    void first(Edge& arc) const {
    524524      arc._id = arcs.size() / 2 - 1;
    525525    }
    … …  
    562562      } else {
    563563        arc._id = -1;
    564         d = true;     
    565       }
    566     }
    567    
     564        d = true;
     565      }
     566    }
     567
    568568    static int id(Node v) { return v._id; }
    569569    static int id(Arc e) { return e._id; }
    … …  
    574574    static Edge edgeFromId(int id) { return Edge(id);}
    575575
    576     bool valid(Node n) const { 
    577       return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 
    578     }
    579     bool valid(Arc a) const { 
     576    bool valid(Node n) const {
     577      return n._id >= 0 && n._id < static_cast<int>(nodes.size());
     578    }
     579    bool valid(Arc a) const {
    580580      return a._id >= 0 && a._id < static_cast<int>(arcs.size());
    581581    }
    582     bool valid(Edge e) const { 
    583       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); 
    584     }
    585 
    586     Node addNode() {     
     582    bool valid(Edge e) const {
     583      return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
     584    }
     585
     586    Node addNode() {
    587587      int n = nodes.size();
    588588      nodes.push_back(NodeT());
    589589      nodes[n].first_out = -1;
    590      
     590
    591591      return Node(n);
    592592    }
    593    
     593
    594594    Edge addEdge(Node u, Node v) {
    595595      int n = arcs.size();
    596596      arcs.push_back(ArcT());
    597597      arcs.push_back(ArcT());
    598      
     598
    599599      arcs[n].target = u._id;
    600600      arcs[n | 1].target = v._id;
    … …  
    603603      nodes[v._id].first_out = n;
    604604
    605       arcs[n | 1].next_out = nodes[u._id].first_out;   
     605      arcs[n | 1].next_out = nodes[u._id].first_out;
    606606      nodes[u._id].first_out = (n | 1);
    607607
    608608      return Edge(n / 2);
    609609    }
    610    
     610
    611611    void clear() {
    612612      arcs.clear();
    … …  
    626626  /// that <b> it does support only limited (only stack-like)
    627627  /// node and arc deletions</b>.
    628   /// Except from this it conforms to 
     628  /// Except from this it conforms to
    629629  /// the \ref concepts::Graph "Graph concept".
    630630  ///
    … …  
    656656
    657657    /// Constructor
    658    
     658
    659659    /// Constructor.
    660660    ///
    … …  
    662662
    663663    ///Add a new node to the graph.
    664    
     664
    665665    /// \return the new node.
    666666    ///
    667667    Node addNode() { return Parent::addNode(); }
    668    
     668
    669669    ///Add a new edge to the graph.
    670    
     670
    671671    ///Add a new edge to the graph with node \c s
    672672    ///and \c t.
    673673    ///\return the new edge.
    674     Edge addEdge(const Node& s, const Node& t) { 
    675       return Parent::addEdge(s, t); 
     674    Edge addEdge(const Node& s, const Node& t) {
     675      return Parent::addEdge(s, t);
    676676    }
    677677
    … …  
    679679    ///
    680680    /// This function gives back true if the given node is valid,
    681     /// ie. it is a real node of the graph. 
     681    /// ie. it is a real node of the graph.
    682682    ///
    683683    /// \warning A removed node (using Snapshot) could become valid again
    … …  
    688688    ///
    689689    /// This function gives back true if the given arc is valid,
    690     /// ie. it is a real arc of the graph. 
     690    /// ie. it is a real arc of the graph.
    691691    ///
    692692    /// \warning A removed arc (using Snapshot) could become valid again
    … …  
    697697    ///
    698698    /// This function gives back true if the given edge is valid,
    699     /// ie. it is a real edge of the graph. 
     699    /// ie. it is a real edge of the graph.
    700700    ///
    701701    /// \warning A removed edge (using Snapshot) could become valid again
    … …  
    704704
    705705    ///Clear the graph.
    706    
     706
    707707    ///Erase all the nodes and edges from the graph.
    708708    ///
    … …  
    712712
    713713  public:
    714    
     714
    715715    class Snapshot;
    716716
    … …  
    729729        int n=arcs.size()-1;
    730730        Edge arc=edgeFromId(n/2);
    731         Parent::notifier(Edge()).erase(arc);
     731        Parent::notifier(Edge()).erase(arc);
    732732        std::vector<Arc> dir;
    733733        dir.push_back(arcFromId(n));
    734734        dir.push_back(arcFromId(n-1));
    735         Parent::notifier(Arc()).erase(dir);
    736         nodes[arcs[n].target].first_out=arcs[n].next_out;
    737         nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
    738         arcs.pop_back();
    739         arcs.pop_back();
     735        Parent::notifier(Arc()).erase(dir);
     736        nodes[arcs[n].target].first_out=arcs[n].next_out;
     737        nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
     738        arcs.pop_back();
     739        arcs.pop_back();
    740740      }
    741741      while(s.node_num<nodes.size()) {
    742742        int n=nodes.size()-1;
    743743        Node node = nodeFromId(n);
    744         Parent::notifier(Node()).erase(node);
    745         nodes.pop_back();
    746       }
    747     }   
     744        Parent::notifier(Node()).erase(node);
     745        nodes.pop_back();
     746      }
     747    }
    748748
    749749  public:
    … …  
    764764    ///not the restored digraph or no change. Because the runtime performance
    765765    ///the validity of the snapshot is not stored.
    766     class Snapshot 
     766    class Snapshot
    767767    {
    768768      SmartGraph *_graph;
    … …  
    773773    public:
    774774      ///Default constructor.
    775      
     775
    776776      ///Default constructor.
    777777      ///To actually make a snapshot you must call save().
    … …  
    779779      Snapshot() : _graph(0) {}
    780780      ///Constructor that immediately makes a snapshot
    781      
     781
    782782      ///This constructor immediately makes a snapshot of the digraph.
    783783      ///\param g The digraph we make a snapshot of.
    … …  
    793793      ///call, the previous snapshot gets lost.
    794794      ///\param g The digraph we make the snapshot of.
    795       void save(SmartGraph &graph) 
     795      void save(SmartGraph &graph)
    796796      {
    797797        graph.saveSnapshot(*this);
    … …  
    799799
    800800      ///Undo the changes until a snapshot.
    801      
     801
    802802      ///Undo the changes until a snapshot created by save().
    803803      ///
    … …  
    811811    };
    812812  };
    813  
     813
    814814} //namespace lemon
    815815
Note: See TracChangeset for help on using the changeset viewer.