COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 1956:a055123339d5

Last change on this file since 1956:a055123339d5 was 1956:a055123339d5, checked in by Alpar Juttner, 14 years ago

Unified copyright notices

File size: 15.4 KB
RevLine 
[906]1/* -*- C++ -*-
2 *
[1956]3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1359]7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[906]8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
[105]18
[921]19#ifndef LEMON_SMART_GRAPH_H
20#define LEMON_SMART_GRAPH_H
[104]21
[491]22///\ingroup graphs
[242]23///\file
[1909]24///\brief SmartGraph and SmartUGraph classes.
[242]25
[104]26#include <vector>
27
[921]28#include <lemon/invalid.h>
[157]29
[1307]30#include <lemon/bits/clearable_graph_extender.h>
31#include <lemon/bits/extendable_graph_extender.h>
32#include <lemon/bits/iterable_graph_extender.h>
33#include <lemon/bits/alteration_notifier.h>
34#include <lemon/bits/default_map.h>
[1791]35#include <lemon/bits/graph_extender.h>
[1034]36
[977]37#include <lemon/utility.h>
[1820]38#include <lemon/error.h>
[782]39
[921]40namespace lemon {
[104]41
[973]42  class SmartGraph;
[969]43  ///Base of SmartGraph
44
45  ///Base of SmartGraph
46  ///
[946]47  class SmartGraphBase {
[104]48
[973]49    friend class SmatGraph;
50
51  protected:
[104]52    struct NodeT
53    {
54      int first_in,first_out;     
[157]55      NodeT() : first_in(-1), first_out(-1) {}
[104]56    };
57    struct EdgeT
58    {
[986]59      int target, source, next_in, next_out;     
[104]60      //FIXME: is this necessary?
[157]61      EdgeT() : next_in(-1), next_out(-1) {} 
[104]62    };
63
64    std::vector<NodeT> nodes;
[129]65
[104]66    std::vector<EdgeT> edges;
67   
[185]68   
[104]69  public:
[782]70
[946]71    typedef SmartGraphBase Graph;
[104]72
[164]73    class Node;
74    class Edge;
[108]75
[104]76   
77  public:
78
[946]79    SmartGraphBase() : nodes(), edges() { }
[1718]80    SmartGraphBase(const SmartGraphBase &_g)
81      : nodes(_g.nodes), edges(_g.edges) { }
[104]82   
[977]83    typedef True NodeNumTag;
84    typedef True EdgeNumTag;
85
[813]86    ///Number of nodes.
87    int nodeNum() const { return nodes.size(); }
88    ///Number of edges.
89    int edgeNum() const { return edges.size(); }
[104]90
[813]91    /// Maximum node ID.
92   
93    /// Maximum node ID.
94    ///\sa id(Node)
[1791]95    int maxNodeId() const { return nodes.size()-1; }
[813]96    /// Maximum edge ID.
97   
98    /// Maximum edge ID.
99    ///\sa id(Edge)
[1791]100    int maxEdgeId() const { return edges.size()-1; }
[108]101
[986]102    Node source(Edge e) const { return edges[e.n].source; }
103    Node target(Edge e) const { return edges[e.n].target; }
[104]104
[813]105    /// Node ID.
106   
107    /// The ID of a valid Node is a nonnegative integer not greater than
[1791]108    /// \ref maxNodeId(). The range of the ID's is not surely continuous
109    /// and the greatest node ID can be actually less then \ref maxNodeId().
[813]110    ///
111    /// The ID of the \ref INVALID node is -1.
112    ///\return The ID of the node \c v.
[713]113    static int id(Node v) { return v.n; }
[813]114    /// Edge ID.
115   
116    /// The ID of a valid Edge is a nonnegative integer not greater than
[1791]117    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
118    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
[813]119    ///
120    /// The ID of the \ref INVALID edge is -1.
121    ///\return The ID of the edge \c e.
[713]122    static int id(Edge e) { return e.n; }
[104]123
[1791]124    static Node nodeFromId(int id) { return Node(id);}
[1106]125
[1791]126    static Edge edgeFromId(int id) { return Edge(id);}
[1106]127
[164]128    Node addNode() {
129      Node n; n.n=nodes.size();
[104]130      nodes.push_back(NodeT()); //FIXME: Hmmm...
131      return n;
132    }
[108]133   
[164]134    Edge addEdge(Node u, Node v) {
135      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
[986]136      edges[e.n].source=u.n; edges[e.n].target=v.n;
[104]137      edges[e.n].next_out=nodes[u.n].first_out;
138      edges[e.n].next_in=nodes[v.n].first_in;
139      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
[108]140
[104]141      return e;
142    }
143
[782]144    void clear() {
145      edges.clear();
146      nodes.clear();
147    }
[104]148
[946]149
[164]150    class Node {
[946]151      friend class SmartGraphBase;
[973]152      friend class SmartGraph;
[104]153
154    protected:
155      int n;
[164]156      Node(int nn) {n=nn;}
[104]157    public:
[164]158      Node() {}
[503]159      Node (Invalid) { n=-1; }
[164]160      bool operator==(const Node i) const {return n==i.n;}
161      bool operator!=(const Node i) const {return n!=i.n;}
162      bool operator<(const Node i) const {return n<i.n;}
[104]163    };
164   
165
[164]166    class Edge {
[946]167      friend class SmartGraphBase;
[973]168      friend class SmartGraph;
[185]169
[104]170    protected:
171      int n;
[905]172      Edge(int nn) {n=nn;}
[706]173    public:
[164]174      Edge() { }
[174]175      Edge (Invalid) { n=-1; }
[164]176      bool operator==(const Edge i) const {return n==i.n;}
177      bool operator!=(const Edge i) const {return n!=i.n;}
178      bool operator<(const Edge i) const {return n<i.n;}
[946]179    };
[905]180
[946]181    void first(Node& node) const {
182      node.n = nodes.size() - 1;
183    }
184
185    static void next(Node& node) {
186      --node.n;
187    }
188
189    void first(Edge& edge) const {
190      edge.n = edges.size() - 1;
191    }
192
193    static void next(Edge& edge) {
194      --edge.n;
195    }
196
197    void firstOut(Edge& edge, const Node& node) const {
198      edge.n = nodes[node.n].first_out;
199    }
200
201    void nextOut(Edge& edge) const {
202      edge.n = edges[edge.n].next_out;
203    }
204
205    void firstIn(Edge& edge, const Node& node) const {
206      edge.n = nodes[node.n].first_in;
207    }
[104]208   
[946]209    void nextIn(Edge& edge) const {
210      edge.n = edges[edge.n].next_in;
211    }
[105]212
[1284]213    Node _split(Node n, bool connect = true)
214    {
215      Node b = addNode();
216      nodes[b.n].first_out=nodes[n.n].first_out;
217      nodes[n.n].first_out=-1;
218      for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
219      if(connect) addEdge(n,b);
220      return b;
221    }
222
[104]223  };
[185]224
[1669]225  typedef ClearableGraphExtender<
226    ExtendableGraphExtender<
227    MappableGraphExtender<
228    IterableGraphExtender<
[1791]229    AlterableGraphExtender<
230    GraphExtender<SmartGraphBase> > > > > > ExtendedSmartGraphBase;
[937]231
[1791]232  /// \ingroup graphs
[1161]233
[950]234  ///A smart graph class.
[937]235
[950]236  ///This is a simple and fast graph implementation.
237  ///It is also quite memory efficient, but at the price
[974]238  ///that <b> it does support only limited (only stack-like)
239  ///node and edge deletions</b>.
[950]240  ///It conforms to
[959]241  ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
242  ///\sa concept::ExtendableGraph.
[950]243  ///
244  ///\author Alpar Juttner
[1669]245  class SmartGraph : public ExtendedSmartGraphBase {
[969]246  public:
[973]247   
[1770]248    class Snapshot;
249    friend class Snapshot;
[973]250
[1011]251  protected:
[1770]252    void restoreSnapshot(const Snapshot &s)
[973]253    {
[1457]254      while(s.edge_num<edges.size()) {
[1040]255        Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
[986]256        nodes[edges.back().target].first_in=edges.back().next_in;
257        nodes[edges.back().source].first_out=edges.back().next_out;
[973]258        edges.pop_back();
259      }
260      //nodes.resize(s.nodes_num);
[1457]261      while(s.node_num<nodes.size()) {
[1040]262        Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
[973]263        nodes.pop_back();
264      }
[1011]265    }   
266
267  public:
[1284]268
269    ///Split a node.
270   
271    ///This function splits a node. First a new node is added to the graph,
272    ///then the source of each outgoing edge of \c n is moved to this new node.
273    ///If \c connect is \c true (this is the default value), then a new edge
274    ///from \c n to the newly created node is also added.
275    ///\return The newly created node.
276    ///
277    ///\note The <tt>Edge</tt>s
278    ///referencing a moved edge remain
279    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
280    ///may be invalidated.
[1770]281    ///\warning This functionality cannot be used together with the Snapshot
[1284]282    ///feature.
283    ///\todo It could be implemented in a bit faster way.
284    Node split(Node n, bool connect = true)
285    {
[1718]286      Node b = _split(n,connect);
287      return b;
[1284]288    }
289 
290
[1011]291    ///Class to make a snapshot of the graph and to restrore to it later.
292
293    ///Class to make a snapshot of the graph and to restrore to it later.
294    ///
295    ///The newly added nodes and edges can be removed using the
296    ///restore() function.
297    ///\note After you restore a state, you cannot restore
298    ///a later state, in other word you cannot add again the edges deleted
[1770]299    ///by restore() using another Snapshot instance.
[1011]300    ///
[1770]301    class Snapshot
[1011]302    {
303      SmartGraph *g;
304    protected:
305      friend class SmartGraph;
306      unsigned int node_num;
307      unsigned int edge_num;
308    public:
[1274]309      ///Default constructor.
[1011]310     
[1274]311      ///Default constructor.
[1011]312      ///To actually make a snapshot you must call save().
313      ///
[1770]314      Snapshot() : g(0) {}
[1011]315      ///Constructor that immediately makes a snapshot
316     
317      ///This constructor immediately makes a snapshot of the graph.
318      ///\param _g The graph we make a snapshot of.
[1770]319      Snapshot(SmartGraph &_g) :g(&_g) {
[1011]320        node_num=g->nodes.size();
321        edge_num=g->edges.size();
322      }
323
324      ///Make a snapshot.
325
326      ///Make a snapshot of the graph.
327      ///
328      ///This function can be called more than once. In case of a repeated
329      ///call, the previous snapshot gets lost.
330      ///\param _g The graph we make the snapshot of.
331      void save(SmartGraph &_g)
332      {
333        g=&_g;
334        node_num=g->nodes.size();
335        edge_num=g->edges.size();
336      }
337
338      ///Undo the changes until a snapshot.
339     
340      ///Undo the changes until a snapshot created by save().
341      ///
342      ///\note After you restored a state, you cannot restore
343      ///a later state, in other word you cannot add again the edges deleted
344      ///by restore().
345      ///
346      ///\todo This function might be called undo().
347     
348      void restore()
349      {
[1770]350        g->restoreSnapshot(*this);
[1011]351      }
352    };
[973]353  };
[1034]354
355
356  /**************** Undirected List Graph ****************/
357
[1909]358  typedef ClearableUGraphExtender<
359    ExtendableUGraphExtender<
360    MappableUGraphExtender<
361    IterableUGraphExtender<
362    AlterableUGraphExtender<
363    UGraphExtender<SmartGraphBase> > > > > > ExtendedSmartUGraphBase;
[1034]364
[1909]365  /// \ingroup graphs
[1035]366  ///
[1909]367  /// \brief A smart undirected graph class.
[1035]368  ///
[1909]369  /// This is a simple and fast undirected graph implementation.
370  /// It is also quite memory efficient, but at the price
371  /// that <b> it does support only limited (only stack-like)
372  /// node and edge deletions</b>.
373  /// Except from this it conforms to
374  /// the \ref concept::UGraph "UGraph" concept.
375  /// \sa concept::UGraph.
376  ///
377  /// \todo Snapshot hasn't been implemented yet.
378  ///
379  class SmartUGraph : public ExtendedSmartUGraphBase {
[1034]380  };
381
[1820]382
[1910]383  class SmartBpUGraphBase {
[1820]384  public:
385
386    class NodeSetError : public LogicError {
387      virtual const char* exceptionName() const {
[1910]388        return "lemon::SmartBpUGraph::NodeSetError";
[1820]389      }
390    };
391
392  protected:
393
394    struct NodeT {
395      int first;
396      NodeT() {}
397      NodeT(int _first) : first(_first) {}
398    };
399
400    struct EdgeT {
[1910]401      int aNode, next_out;
402      int bNode, next_in;
[1820]403    };
404
[1910]405    std::vector<NodeT> aNodes;
406    std::vector<NodeT> bNodes;
[1820]407
408    std::vector<EdgeT> edges;
409
410  public:
411 
412    class Node {
[1910]413      friend class SmartBpUGraphBase;
[1820]414    protected:
415      int id;
416
417      Node(int _id) : id(_id) {}
418    public:
419      Node() {}
420      Node(Invalid) { id = -1; }
421      bool operator==(const Node i) const {return id==i.id;}
422      bool operator!=(const Node i) const {return id!=i.id;}
423      bool operator<(const Node i) const {return id<i.id;}
424    };
425
426    class Edge {
[1910]427      friend class SmartBpUGraphBase;
[1820]428    protected:
429      int id;
430
431      Edge(int _id) { id = _id;}
432    public:
433      Edge() {}
434      Edge (Invalid) { id = -1; }
435      bool operator==(const Edge i) const {return id==i.id;}
436      bool operator!=(const Edge i) const {return id!=i.id;}
437      bool operator<(const Edge i) const {return id<i.id;}
438    };
439
[1910]440    void firstANode(Node& node) const {
441      node.id = 2 * aNodes.size() - 2;
[1820]442      if (node.id < 0) node.id = -1;
443    }
[1910]444    void nextANode(Node& node) const {
[1820]445      node.id -= 2;
446      if (node.id < 0) node.id = -1;
447    }
448
[1910]449    void firstBNode(Node& node) const {
450      node.id = 2 * bNodes.size() - 1;
[1820]451    }
[1910]452    void nextBNode(Node& node) const {
[1820]453      node.id -= 2;
454    }
455
456    void first(Node& node) const {
[1910]457      if (aNodes.size() > 0) {
458        node.id = 2 * aNodes.size() - 2;
[1820]459      } else {
[1910]460        node.id = 2 * bNodes.size() - 1;
[1820]461      }
462    }
463    void next(Node& node) const {
464      node.id -= 2;
465      if (node.id == -2) {
[1910]466        node.id = 2 * bNodes.size() - 1;
[1820]467      }
468    }
469 
470    void first(Edge& edge) const {
471      edge.id = edges.size() - 1;
472    }
473    void next(Edge& edge) const {
474      --edge.id;
475    }
476
[1910]477    void firstOut(Edge& edge, const Node& node) const {
[1820]478      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
[1910]479      edge.id = aNodes[node.id >> 1].first;
[1820]480    }
[1910]481    void nextOut(Edge& edge) const {
482      edge.id = edges[edge.id].next_out;
[1820]483    }
484
[1910]485    void firstIn(Edge& edge, const Node& node) const {
[1820]486      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
[1910]487      edge.id = bNodes[node.id >> 1].first;
[1820]488    }
[1910]489    void nextIn(Edge& edge) const {
490      edge.id = edges[edge.id].next_in;
[1820]491    }
492
493    static int id(const Node& node) {
494      return node.id;
495    }
496    static Node nodeFromId(int id) {
497      return Node(id);
498    }
499    int maxNodeId() const {
[1910]500      return aNodes.size() > bNodes.size() ?
501        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
[1820]502    }
503 
504    static int id(const Edge& edge) {
505      return edge.id;
506    }
507    static Edge edgeFromId(int id) {
508      return Edge(id);
509    }
510    int maxEdgeId() const {
511      return edges.size();
512    }
513 
[1910]514    static int aNodeId(const Node& node) {
[1820]515      return node.id >> 1;
516    }
[1910]517    static Node fromANodeId(int id, Node) {
[1820]518      return Node(id << 1);
519    }
[1910]520    int maxANodeId() const {
521      return aNodes.size();
[1820]522    }
523
[1910]524    static int bNodeId(const Node& node) {
[1820]525      return node.id >> 1;
526    }
[1910]527    static Node fromBNodeId(int id) {
[1820]528      return Node((id << 1) + 1);
529    }
[1910]530    int maxBNodeId() const {
531      return bNodes.size();
[1820]532    }
533
[1910]534    Node aNode(const Edge& edge) const {
535      return Node(edges[edge.id].aNode);
[1820]536    }
[1910]537    Node bNode(const Edge& edge) const {
538      return Node(edges[edge.id].bNode);
[1820]539    }
540
[1910]541    static bool aNode(const Node& node) {
[1820]542      return (node.id & 1) == 0;
543    }
544
[1910]545    static bool bNode(const Node& node) {
[1820]546      return (node.id & 1) == 1;
547    }
548
[1910]549    Node addANode() {
[1820]550      NodeT nodeT;
551      nodeT.first = -1;
[1910]552      aNodes.push_back(nodeT);
553      return Node(aNodes.size() * 2 - 2);
[1820]554    }
555
[1910]556    Node addBNode() {
[1820]557      NodeT nodeT;
558      nodeT.first = -1;
[1910]559      bNodes.push_back(nodeT);
560      return Node(bNodes.size() * 2 - 1);
[1820]561    }
562
563    Edge addEdge(const Node& source, const Node& target) {
564      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
565      EdgeT edgeT;
566      if ((source.id & 1) == 0) {
[1910]567        edgeT.aNode = source.id;
568        edgeT.bNode = target.id;
[1820]569      } else {
[1910]570        edgeT.aNode = target.id;
571        edgeT.bNode = source.id;
[1820]572      }
[1910]573      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
574      aNodes[edgeT.aNode >> 1].first = edges.size();
575      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
576      bNodes[edgeT.bNode >> 1].first = edges.size();
[1820]577      edges.push_back(edgeT);
578      return Edge(edges.size() - 1);
579    }
580
581    void clear() {
[1910]582      aNodes.clear();
583      bNodes.clear();
[1820]584      edges.clear();
585    }
586
587  };
588
589
[1910]590  typedef ClearableBpUGraphExtender<
591    ExtendableBpUGraphExtender<
592    MappableBpUGraphExtender<
593    IterableBpUGraphExtender<
594    AlterableBpUGraphExtender<
595    BpUGraphExtender <
596    SmartBpUGraphBase> > > > > >
597  ExtendedSmartBpUGraphBase;
[1820]598
[1910]599  /// \ingroup graphs
600  ///
601  /// \brief A smart bipartite undirected graph class.
602  ///
603  /// This is a simple and fast bipartite undirected graph implementation.
604  /// It is also quite memory efficient, but at the price
605  /// that <b> it does not support node and edge deletions</b>.
606  /// Except from this it conforms to
607  /// the \ref concept::BpUGraph "BpUGraph" concept.
608  /// \sa concept::BpUGraph.
609  ///
610  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
[1820]611
[950]612 
[407]613  /// @} 
[921]614} //namespace lemon
[104]615
[157]616
[921]617#endif //LEMON_SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.