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