COIN-OR::LEMON - Graph Library

Changeset 2190:dd887831e9c1 in lemon-0.x for lemon/smart_graph.h


Ignore:
Timestamp:
09/04/06 13:09:13 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2915
Message:

Snapshot for SmartUGraph an SmartBpUGraph

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/smart_graph.h

    r2162 r2190  
    4444  ///
    4545  class SmartGraphBase {
    46 
    47     friend class SmatGraph;
    48 
    4946  protected:
     47
    5048    struct NodeT
    5149    {
    52       int first_in,first_out;     
    53       NodeT() : first_in(-1), first_out(-1) {}
     50      int first_in, first_out;     
     51      NodeT() {}
    5452    };
    5553    struct EdgeT
    5654    {
    5755      int target, source, next_in, next_out;     
    58       //FIXME: is this necessary?
    59       EdgeT() : next_in(-1), next_out(-1) {} 
     56      EdgeT() {} 
    6057    };
    6158
     
    8279    typedef True EdgeNumTag;
    8380
    84     ///Number of nodes.
    8581    int nodeNum() const { return nodes.size(); }
    86     ///Number of edges.
    8782    int edgeNum() const { return edges.size(); }
    8883
    89     /// Maximum node ID.
    90    
    91     /// Maximum node ID.
    92     ///\sa id(Node)
    9384    int maxNodeId() const { return nodes.size()-1; }
    94     /// Maximum edge ID.
    95    
    96     /// Maximum edge ID.
    97     ///\sa id(Edge)
    9885    int maxEdgeId() const { return edges.size()-1; }
    9986
    10087    Node addNode() {
    101       Node n; n.n=nodes.size();
    102       nodes.push_back(NodeT()); //FIXME: Hmmm...
    103       return n;
     88      int n = nodes.size();     
     89      nodes.push_back(NodeT());
     90      nodes[n].first_in = -1;
     91      nodes[n].first_out = -1;
     92      return Node(n);
    10493    }
    10594   
    10695    Edge addEdge(Node u, Node v) {
    107       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
    108       edges[e.n].source=u.n; edges[e.n].target=v.n;
    109       edges[e.n].next_out=nodes[u.n].first_out;
    110       edges[e.n].next_in=nodes[v.n].first_in;
    111       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
    112 
    113       return e;
    114     }
    115 
    116 
    117     Node source(Edge e) const { return edges[e.n].source; }
    118     Node target(Edge e) const { return edges[e.n].target; }
    119 
    120     /// Node ID.
    121    
    122     /// The ID of a valid Node is a nonnegative integer not greater than
    123     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    124     /// and the greatest node ID can be actually less then \ref maxNodeId().
    125     ///
    126     /// The ID of the \ref INVALID node is -1.
    127     ///\return The ID of the node \c v.
    128     static int id(Node v) { return v.n; }
    129     /// Edge ID.
    130    
    131     /// The ID of a valid Edge is a nonnegative integer not greater than
    132     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    133     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    134     ///
    135     /// The ID of the \ref INVALID edge is -1.
    136     ///\return The ID of the edge \c e.
    137     static int id(Edge e) { return e.n; }
    138 
    139     /// \brief Returns the node from its \c id.
    140     ///
    141     /// Returns the node from its \c id. If there is not node
    142     /// with the given id the effect of the function is undefinied.
     96      int n = edges.size();
     97      edges.push_back(EdgeT());
     98      edges[n].source = u.id;
     99      edges[n].target = v.id;
     100      edges[n].next_out = nodes[u.id].first_out;
     101      edges[n].next_in = nodes[v.id].first_in;
     102      nodes[u.id].first_out = nodes[v.id].first_in = n;
     103
     104      return Edge(n);
     105    }
     106
     107    void clear() {
     108      edges.clear();
     109      nodes.clear();
     110    }
     111
     112    Node source(Edge e) const { return Node(edges[e.id].source); }
     113    Node target(Edge e) const { return Node(edges[e.id].target); }
     114
     115    static int id(Node v) { return v.id; }
     116    static int id(Edge e) { return e.id; }
     117
    143118    static Node nodeFromId(int id) { return Node(id);}
    144 
    145     /// \brief Returns the edge from its \c id.
    146     ///
    147     /// Returns the edge from its \c id. If there is not edge
    148     /// with the given id the effect of the function is undefinied.
    149119    static Edge edgeFromId(int id) { return Edge(id);}
    150120
     
    154124
    155125    protected:
    156       int n;
    157       Node(int nn) {n=nn;}
     126      int id;
     127      explicit Node(int _id) : id(_id) {}
    158128    public:
    159129      Node() {}
    160       Node (Invalid) { n=-1; }
    161       bool operator==(const Node i) const {return n==i.n;}
    162       bool operator!=(const Node i) const {return n!=i.n;}
    163       bool operator<(const Node i) const {return n<i.n;}
     130      Node (Invalid) : id(-1) {}
     131      bool operator==(const Node i) const {return id == i.id;}
     132      bool operator!=(const Node i) const {return id != i.id;}
     133      bool operator<(const Node i) const {return id < i.id;}
    164134    };
    165135   
     
    170140
    171141    protected:
    172       int n;
    173       Edge(int nn) {n=nn;}
     142      int id;
     143      explicit Edge(int _id) : id(_id) {}
    174144    public:
    175145      Edge() { }
    176       Edge (Invalid) { n=-1; }
    177       bool operator==(const Edge i) const {return n==i.n;}
    178       bool operator!=(const Edge i) const {return n!=i.n;}
    179       bool operator<(const Edge i) const {return n<i.n;}
     146      Edge (Invalid) : id(-1) {}
     147      bool operator==(const Edge i) const {return id == i.id;}
     148      bool operator!=(const Edge i) const {return id != i.id;}
     149      bool operator<(const Edge i) const {return id < i.id;}
    180150    };
    181151
    182152    void first(Node& node) const {
    183       node.n = nodes.size() - 1;
     153      node.id = nodes.size() - 1;
    184154    }
    185155
    186156    static void next(Node& node) {
    187       --node.n;
     157      --node.id;
    188158    }
    189159
    190160    void first(Edge& edge) const {
    191       edge.n = edges.size() - 1;
     161      edge.id = edges.size() - 1;
    192162    }
    193163
    194164    static void next(Edge& edge) {
    195       --edge.n;
     165      --edge.id;
    196166    }
    197167
    198168    void firstOut(Edge& edge, const Node& node) const {
    199       edge.n = nodes[node.n].first_out;
     169      edge.id = nodes[node.id].first_out;
    200170    }
    201171
    202172    void nextOut(Edge& edge) const {
    203       edge.n = edges[edge.n].next_out;
     173      edge.id = edges[edge.id].next_out;
    204174    }
    205175
    206176    void firstIn(Edge& edge, const Node& node) const {
    207       edge.n = nodes[node.n].first_in;
     177      edge.id = nodes[node.id].first_in;
    208178    }
    209179   
    210180    void nextIn(Edge& edge) const {
    211       edge.n = edges[edge.n].next_in;
     181      edge.id = edges[edge.id].next_in;
    212182    }
    213183
     
    234204    typedef ExtendedSmartGraphBase Parent;
    235205
    236     class Snapshot;
    237     friend class Snapshot;
    238 
    239206  private:
     207
    240208    ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
    241209
    242210    ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
    243211    ///
    244     SmartGraph(const SmartGraph &) :ExtendedSmartGraphBase() {};
     212    SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
    245213    ///\brief Assignment of SmartGraph to another one is \e not allowed.
    246214    ///Use GraphCopy() instead.
     
    249217    ///Use GraphCopy() instead.
    250218    void operator=(const SmartGraph &) {}
    251   protected:
    252     void restoreSnapshot(const Snapshot &s)
    253     {
    254       while(s.edge_num<edges.size()) {
    255         Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
    256         nodes[edges.back().target].first_in=edges.back().next_in;
    257         nodes[edges.back().source].first_out=edges.back().next_out;
    258         edges.pop_back();
    259       }
    260       //nodes.resize(s.nodes_num);
    261       while(s.node_num<nodes.size()) {
    262         Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
    263         nodes.pop_back();
    264       }
    265     }   
    266219
    267220  public:
     
    288241    }
    289242
    290     ///\e
    291    
    292     ///\bug Undocumented
    293     ///\bug Doesn't destruct the maps.
     243    ///Clear the graph.
     244   
     245    ///Erase all the nodes and edges from the graph.
     246    ///
    294247    void clear() {
    295       edges.clear();
    296       nodes.clear();
     248      Parent::clear();
    297249    }
    298250
     
    315267    {
    316268      Node b = addNode();
    317       nodes[b.n].first_out=nodes[n.n].first_out;
    318       nodes[n.n].first_out=-1;
    319       for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
     269      nodes[b.id].first_out=nodes[n.id].first_out;
     270      nodes[n.id].first_out=-1;
     271      for(int i=nodes[b.id].first_out;i!=-1;i++) edges[i].source=b.id;
    320272      if(connect) addEdge(n,b);
    321273      return b;
    322274    }
     275
     276  public:
     277   
     278    class Snapshot;
     279
     280  protected:
     281
     282    void restoreSnapshot(const Snapshot &s)
     283    {
     284      while(s.edge_num<edges.size()) {
     285        Edge edge = edgeFromId(edges.size()-1);
     286        Parent::getNotifier(Edge()).erase(edge);
     287        nodes[edges.back().source].first_out=edges.back().next_out;
     288        nodes[edges.back().target].first_in=edges.back().next_in;
     289        edges.pop_back();
     290      }
     291      while(s.node_num<nodes.size()) {
     292        Node node = nodeFromId(nodes.size()-1);
     293        Parent::getNotifier(Node()).erase(node);
     294        nodes.pop_back();
     295      }
     296    }   
     297
     298  public:
    323299
    324300    ///Class to make a snapshot of the graph and to restrore to it later.
     
    332308    ///by restore() using another one Snapshot instance.
    333309    ///
     310    ///\warning If you do not use correctly the snapshot that can cause
     311    ///either broken program, invalid state of the graph, valid but
     312    ///not the restored graph or no change. Because the runtime performance
     313    ///the validity of the snapshot is not stored.
    334314    class Snapshot
    335315    {
     
    376356      ///a later state, in other word you cannot add again the edges deleted
    377357      ///by restore().
    378       ///
    379       ///\todo This function might be called undo().
    380      
    381358      void restore()
    382359      {
     
    408385  class SmartUGraph : public ExtendedSmartUGraphBase {
    409386  private:
     387
    410388    ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
    411389
     
    413391    ///
    414392    SmartUGraph(const SmartUGraph &) : ExtendedSmartUGraphBase() {};
     393
    415394    ///\brief Assignment of SmartUGraph to another one is \e not allowed.
    416395    ///Use UGraphCopy() instead.
     
    419398    ///Use UGraphCopy() instead.
    420399    void operator=(const SmartUGraph &) {}
    421   public:
     400
     401  public:
     402
     403    typedef ExtendedSmartUGraphBase Parent;
     404
    422405    /// Constructor
    423406   
     
    425408    ///
    426409    SmartUGraph() {}
     410
     411    ///Add a new node to the graph.
     412   
     413    /// \return the new node.
     414    ///
     415    Node addNode() { return Parent::addNode(); }
     416   
     417    ///Add a new undirected edge to the graph.
     418   
     419    ///Add a new undirected edge to the graph with node \c s
     420    ///and \c t.
     421    ///\return the new undirected edge.
     422    UEdge addEdge(const Node& s, const Node& t) {
     423      return Parent::addEdge(s, t);
     424    }
     425
     426    ///Clear the graph.
     427   
     428    ///Erase all the nodes and edges from the graph.
     429    ///
     430    void clear() {
     431      Parent::clear();
     432    }
     433
     434  public:
     435   
     436    class Snapshot;
     437
     438  protected:
     439
     440
     441    void restoreSnapshot(const Snapshot &s)
     442    {
     443      while(s.edge_num<edges.size()) {
     444        UEdge edge = uEdgeFromId(edges.size()-1);
     445        Parent::getNotifier(UEdge()).erase(edge);
     446        std::vector<Edge> dir;
     447        dir.push_back(Parent::direct(edge, true));
     448        dir.push_back(Parent::direct(edge, false));
     449        Parent::getNotifier(Edge()).erase(dir);
     450        nodes[edges.back().source].first_out=edges.back().next_out;
     451        nodes[edges.back().target].first_in=edges.back().next_in;
     452        edges.pop_back();
     453      }
     454      while(s.node_num<nodes.size()) {
     455        Node node = nodeFromId(nodes.size()-1);
     456        Parent::getNotifier(Node()).erase(node);
     457        nodes.pop_back();
     458      }
     459    }   
     460
     461  public:
     462
     463    ///Class to make a snapshot of the graph and to restrore to it later.
     464
     465    ///Class to make a snapshot of the graph and to restrore to it later.
     466    ///
     467    ///The newly added nodes and edges can be removed using the
     468    ///restore() function.
     469    ///
     470    ///\note After you restore a state, you cannot restore
     471    ///a later state, in other word you cannot add again the edges deleted
     472    ///by restore() using another one Snapshot instance.
     473    ///
     474    ///\warning If you do not use correctly the snapshot that can cause
     475    ///either broken program, invalid state of the graph, valid but
     476    ///not the restored graph or no change. Because the runtime performance
     477    ///the validity of the snapshot is not stored.
     478    class Snapshot
     479    {
     480      SmartUGraph *g;
     481    protected:
     482      friend class SmartUGraph;
     483      unsigned int node_num;
     484      unsigned int edge_num;
     485    public:
     486      ///Default constructor.
     487     
     488      ///Default constructor.
     489      ///To actually make a snapshot you must call save().
     490      ///
     491      Snapshot() : g(0) {}
     492      ///Constructor that immediately makes a snapshot
     493     
     494      ///This constructor immediately makes a snapshot of the graph.
     495      ///\param _g The graph we make a snapshot of.
     496      Snapshot(SmartUGraph &_g) :g(&_g) {
     497        node_num=g->nodes.size();
     498        edge_num=g->edges.size();
     499      }
     500
     501      ///Make a snapshot.
     502
     503      ///Make a snapshot of the graph.
     504      ///
     505      ///This function can be called more than once. In case of a repeated
     506      ///call, the previous snapshot gets lost.
     507      ///\param _g The graph we make the snapshot of.
     508      void save(SmartUGraph &_g)
     509      {
     510        g=&_g;
     511        node_num=g->nodes.size();
     512        edge_num=g->edges.size();
     513      }
     514
     515      ///Undo the changes until a snapshot.
     516     
     517      ///Undo the changes until a snapshot created by save().
     518      ///
     519      ///\note After you restored a state, you cannot restore
     520      ///a later state, in other word you cannot add again the edges deleted
     521      ///by restore().
     522      void restore()
     523      {
     524        g->restoreSnapshot(*this);
     525      }
     526    };
    427527  };
    428528
     
    463563      int id;
    464564
    465       Node(int _id) : id(_id) {}
     565      explicit Node(int _id) : id(_id) {}
    466566    public:
    467567      Node() {}
    468       Node(Invalid) { id = -1; }
     568      Node(Invalid) : id(-1) {}
    469569      bool operator==(const Node i) const {return id==i.id;}
    470570      bool operator!=(const Node i) const {return id!=i.id;}
     
    477577      int id;
    478578
    479       UEdge(int _id) { id = _id;}
     579      UEdge(int _id) : id(_id) {}
    480580    public:
    481581      UEdge() {}
    482       UEdge (Invalid) { id = -1; }
     582      UEdge(Invalid) : id(-1) {}
    483583      bool operator==(const UEdge i) const {return id==i.id;}
    484584      bool operator!=(const UEdge i) const {return id!=i.id;}
     
    657757  /// \sa concept::BpUGraph.
    658758  ///
    659   class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
     759  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {
     760  private:
     761
     762    /// \brief SmartBpUGraph is \e not copy constructible.
     763    ///
     764    ///SmartBpUGraph is \e not copy constructible.
     765    SmartBpUGraph(const SmartBpUGraph &) : ExtendedSmartBpUGraphBase() {};
     766
     767    /// \brief Assignment of SmartBpUGraph to another one is \e not
     768    /// allowed.
     769    ///
     770    /// Assignment of SmartBpUGraph to another one is \e not allowed.
     771    void operator=(const SmartBpUGraph &) {}
     772
     773  public:
     774
     775    typedef ExtendedSmartBpUGraphBase Parent;
     776
     777    ///Constructor
     778   
     779    ///Constructor.
     780    ///
     781    SmartBpUGraph() : ExtendedSmartBpUGraphBase() {}
     782
     783    ///Add a new ANode to the graph.
     784   
     785    /// \return the new node.
     786    ///
     787    Node addANode() { return Parent::addANode(); }
     788
     789    ///Add a new BNode to the graph.
     790   
     791    /// \return the new node.
     792    ///
     793    Node addBNode() { return Parent::addBNode(); }
     794   
     795    ///Add a new undirected edge to the graph.
     796   
     797    ///Add a new undirected edge to the graph with node \c s
     798    ///and \c t.
     799    ///\return the new undirected edge.
     800    UEdge addEdge(const Node& s, const Node& t) {
     801      return Parent::addEdge(s, t);
     802    }
     803
     804    ///Clear the graph.
     805   
     806    ///Erase all the nodes and edges from the graph.
     807    ///
     808    void clear() {
     809      Parent::clear();
     810    }
     811   
     812  public:
     813
     814    class Snapshot;
     815
     816  protected:
     817   
     818    void restoreSnapshot(const Snapshot &s)
     819    {
     820      while(s.edge_num<edges.size()) {
     821        UEdge edge = uEdgeFromId(edges.size()-1);
     822        Parent::getNotifier(UEdge()).erase(edge);
     823        std::vector<Edge> dir;
     824        dir.push_back(Parent::direct(edge, true));
     825        dir.push_back(Parent::direct(edge, false));
     826        Parent::getNotifier(Edge()).erase(dir);
     827        aNodes[edges.back().aNode >> 1].first=edges.back().next_out;
     828        bNodes[edges.back().bNode >> 1].first=edges.back().next_in;
     829        edges.pop_back();
     830      }
     831      while(s.anode_num<aNodes.size()) {
     832        Node node = fromANodeId(aNodes.size() - 1);
     833        Parent::getNotifier(ANode()).erase(node);
     834        Parent::getNotifier(Node()).erase(node);
     835        aNodes.pop_back();
     836      }
     837      while(s.bnode_num<bNodes.size()) {
     838        Node node = fromBNodeId(bNodes.size() - 1);
     839        Parent::getNotifier(BNode()).erase(node);
     840        Parent::getNotifier(Node()).erase(node);
     841        bNodes.pop_back();
     842      }
     843    }   
     844
     845  public:
     846
     847    ///Class to make a snapshot of the graph and to restrore to it later.
     848
     849    ///Class to make a snapshot of the graph and to restrore to it later.
     850    ///
     851    ///The newly added nodes and edges can be removed using the
     852    ///restore() function.
     853    ///
     854    ///\note After you restore a state, you cannot restore
     855    ///a later state, in other word you cannot add again the edges deleted
     856    ///by restore() using another one Snapshot instance.
     857    ///
     858    ///\warning If you do not use correctly the snapshot that can cause
     859    ///either broken program, invalid state of the graph, valid but
     860    ///not the restored graph or no change. Because the runtime performance
     861    ///the validity of the snapshot is not stored.
     862    class Snapshot
     863    {
     864      SmartBpUGraph *g;
     865    protected:
     866      friend class SmartBpUGraph;
     867      unsigned int anode_num;
     868      unsigned int bnode_num;
     869      unsigned int edge_num;
     870    public:
     871      ///Default constructor.
     872     
     873      ///Default constructor.
     874      ///To actually make a snapshot you must call save().
     875      ///
     876      Snapshot() : g(0) {}
     877
     878      ///Constructor that immediately makes a snapshot
     879     
     880      ///This constructor immediately makes a snapshot of the graph.
     881      ///\param _g The graph we make a snapshot of.
     882      Snapshot(SmartBpUGraph &_g) : g(&_g) {
     883        anode_num=g->aNodes.size();
     884        bnode_num=g->bNodes.size();
     885        edge_num=g->edges.size();
     886      }
     887
     888      ///Make a snapshot.
     889
     890      ///Make a snapshot of the graph.
     891      ///
     892      ///This function can be called more than once. In case of a repeated
     893      ///call, the previous snapshot gets lost.
     894      ///\param _g The graph we make the snapshot of.
     895      void save(SmartBpUGraph &_g)
     896      {
     897        g=&_g;
     898        anode_num=g->aNodes.size();
     899        bnode_num=g->bNodes.size();
     900        edge_num=g->edges.size();
     901      }
     902
     903      ///Undo the changes until a snapshot.
     904     
     905      ///Undo the changes until a snapshot created by save().
     906      ///
     907      ///\note After you restored a state, you cannot restore
     908      ///a later state, in other word you cannot add again the edges deleted
     909      ///by restore().
     910      void restore()
     911      {
     912        g->restoreSnapshot(*this);
     913      }
     914    };
     915  };
    660916
    661917 
Note: See TracChangeset for help on using the changeset viewer.