lemon/smart_graph.h
author deba
Tue, 24 Jan 2006 16:07:38 +0000
changeset 1901 723b2b81d900
parent 1820 22099ef840d7
child 1909 2d806130e700
permissions -rw-r--r--
Lemon Graph Format uses label instead of id named map.
     1 /* -*- C++ -*-
     2  * lemon/smart_graph.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_SMART_GRAPH_H
    18 #define LEMON_SMART_GRAPH_H
    19 
    20 ///\ingroup graphs
    21 ///\file
    22 ///\brief SmartGraph and UndirSmartGraph classes.
    23 
    24 #include <vector>
    25 
    26 #include <lemon/invalid.h>
    27 
    28 #include <lemon/bits/clearable_graph_extender.h>
    29 #include <lemon/bits/extendable_graph_extender.h>
    30 #include <lemon/bits/iterable_graph_extender.h>
    31 #include <lemon/bits/alteration_notifier.h>
    32 #include <lemon/bits/default_map.h>
    33 #include <lemon/bits/graph_extender.h>
    34 
    35 #include <lemon/utility.h>
    36 #include <lemon/error.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     static Node nodeFromId(int id) { return Node(id);}
   123 
   124     static Edge edgeFromId(int id) { return Edge(id);}
   125 
   126     Node addNode() {
   127       Node n; n.n=nodes.size();
   128       nodes.push_back(NodeT()); //FIXME: Hmmm...
   129       return n;
   130     }
   131     
   132     Edge addEdge(Node u, Node v) {
   133       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
   134       edges[e.n].source=u.n; edges[e.n].target=v.n;
   135       edges[e.n].next_out=nodes[u.n].first_out;
   136       edges[e.n].next_in=nodes[v.n].first_in;
   137       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
   138 
   139       return e;
   140     }
   141 
   142     void clear() {
   143       edges.clear();
   144       nodes.clear();
   145     }
   146 
   147 
   148     class Node {
   149       friend class SmartGraphBase;
   150       friend class SmartGraph;
   151 
   152     protected:
   153       int n;
   154       Node(int nn) {n=nn;}
   155     public:
   156       Node() {}
   157       Node (Invalid) { n=-1; }
   158       bool operator==(const Node i) const {return n==i.n;}
   159       bool operator!=(const Node i) const {return n!=i.n;}
   160       bool operator<(const Node i) const {return n<i.n;}
   161     };
   162     
   163 
   164     class Edge {
   165       friend class SmartGraphBase;
   166       friend class SmartGraph;
   167 
   168     protected:
   169       int n;
   170       Edge(int nn) {n=nn;}
   171     public:
   172       Edge() { }
   173       Edge (Invalid) { n=-1; }
   174       bool operator==(const Edge i) const {return n==i.n;}
   175       bool operator!=(const Edge i) const {return n!=i.n;}
   176       bool operator<(const Edge i) const {return n<i.n;}
   177     };
   178 
   179     void first(Node& node) const {
   180       node.n = nodes.size() - 1;
   181     }
   182 
   183     static void next(Node& node) {
   184       --node.n;
   185     }
   186 
   187     void first(Edge& edge) const {
   188       edge.n = edges.size() - 1;
   189     }
   190 
   191     static void next(Edge& edge) {
   192       --edge.n;
   193     }
   194 
   195     void firstOut(Edge& edge, const Node& node) const {
   196       edge.n = nodes[node.n].first_out;
   197     }
   198 
   199     void nextOut(Edge& edge) const {
   200       edge.n = edges[edge.n].next_out;
   201     }
   202 
   203     void firstIn(Edge& edge, const Node& node) const {
   204       edge.n = nodes[node.n].first_in;
   205     }
   206     
   207     void nextIn(Edge& edge) const {
   208       edge.n = edges[edge.n].next_in;
   209     }
   210 
   211     Node _split(Node n, bool connect = true)
   212     {
   213       Node b = addNode();
   214       nodes[b.n].first_out=nodes[n.n].first_out;
   215       nodes[n.n].first_out=-1;
   216       for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
   217       if(connect) addEdge(n,b);
   218       return b;
   219     }
   220 
   221   };
   222 
   223   typedef ClearableGraphExtender<
   224     ExtendableGraphExtender<
   225     MappableGraphExtender<
   226     IterableGraphExtender<
   227     AlterableGraphExtender<
   228     GraphExtender<SmartGraphBase> > > > > > ExtendedSmartGraphBase;
   229 
   230   /// \ingroup graphs
   231 
   232   ///A smart graph class.
   233 
   234   ///This is a simple and fast graph implementation.
   235   ///It is also quite memory efficient, but at the price
   236   ///that <b> it does support only limited (only stack-like)
   237   ///node and edge deletions</b>.
   238   ///It conforms to 
   239   ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
   240   ///\sa concept::ExtendableGraph.
   241   ///
   242   ///\author Alpar Juttner
   243   class SmartGraph : public ExtendedSmartGraphBase {
   244   public:
   245     
   246     class Snapshot;
   247     friend class Snapshot;
   248 
   249   protected:
   250     void restoreSnapshot(const Snapshot &s)
   251     {
   252       while(s.edge_num<edges.size()) {
   253 	Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
   254 	nodes[edges.back().target].first_in=edges.back().next_in;
   255 	nodes[edges.back().source].first_out=edges.back().next_out;
   256 	edges.pop_back();
   257       }
   258       //nodes.resize(s.nodes_num);
   259       while(s.node_num<nodes.size()) {
   260 	Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
   261 	nodes.pop_back();
   262       }
   263     }    
   264 
   265   public:
   266 
   267     ///Split a node.
   268     
   269     ///This function splits a node. First a new node is added to the graph,
   270     ///then the source of each outgoing edge of \c n is moved to this new node.
   271     ///If \c connect is \c true (this is the default value), then a new edge
   272     ///from \c n to the newly created node is also added.
   273     ///\return The newly created node.
   274     ///
   275     ///\note The <tt>Edge</tt>s
   276     ///referencing a moved edge remain
   277     ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
   278     ///may be invalidated.
   279     ///\warning This functionality cannot be used together with the Snapshot
   280     ///feature.
   281     ///\todo It could be implemented in a bit faster way.
   282     Node split(Node n, bool connect = true) 
   283     {
   284       Node b = _split(n,connect);
   285       return b;
   286     }
   287   
   288 
   289     ///Class to make a snapshot of the graph and to restrore to it later.
   290 
   291     ///Class to make a snapshot of the graph and to restrore to it later.
   292     ///
   293     ///The newly added nodes and edges can be removed using the
   294     ///restore() function.
   295     ///\note After you restore a state, you cannot restore
   296     ///a later state, in other word you cannot add again the edges deleted
   297     ///by restore() using another Snapshot instance.
   298     ///
   299     class Snapshot 
   300     {
   301       SmartGraph *g;
   302     protected:
   303       friend class SmartGraph;
   304       unsigned int node_num;
   305       unsigned int edge_num;
   306     public:
   307       ///Default constructor.
   308       
   309       ///Default constructor.
   310       ///To actually make a snapshot you must call save().
   311       ///
   312       Snapshot() : g(0) {}
   313       ///Constructor that immediately makes a snapshot
   314       
   315       ///This constructor immediately makes a snapshot of the graph.
   316       ///\param _g The graph we make a snapshot of.
   317       Snapshot(SmartGraph &_g) :g(&_g) {
   318 	node_num=g->nodes.size();
   319 	edge_num=g->edges.size();
   320       }
   321 
   322       ///Make a snapshot.
   323 
   324       ///Make a snapshot of the graph.
   325       ///
   326       ///This function can be called more than once. In case of a repeated
   327       ///call, the previous snapshot gets lost.
   328       ///\param _g The graph we make the snapshot of.
   329       void save(SmartGraph &_g) 
   330       {
   331 	g=&_g;
   332 	node_num=g->nodes.size();
   333 	edge_num=g->edges.size();
   334       }
   335 
   336       ///Undo the changes until a snapshot.
   337       
   338       ///Undo the changes until a snapshot created by save().
   339       ///
   340       ///\note After you restored a state, you cannot restore
   341       ///a later state, in other word you cannot add again the edges deleted
   342       ///by restore().
   343       ///
   344       ///\todo This function might be called undo().
   345       
   346       void restore()
   347       {
   348 	g->restoreSnapshot(*this);
   349       }
   350     };
   351   };
   352 
   353 
   354   /**************** Undirected List Graph ****************/
   355 
   356   typedef ClearableUndirGraphExtender<
   357     ExtendableUndirGraphExtender<
   358     MappableUndirGraphExtender<
   359     IterableUndirGraphExtender<
   360     AlterableUndirGraphExtender<
   361     UndirGraphExtender<SmartGraphBase> > > > > > ExtendedUndirSmartGraphBase;
   362 
   363   ///A smart undirected graph class.
   364 
   365   ///This is a simple and fast undirected graph implementation.
   366   ///It is also quite memory efficient, but at the price
   367   ///that <b> it does support only limited (only stack-like)
   368   ///node and edge deletions</b>.
   369   ///Except from this it conforms to 
   370   ///the \ref concept::UndirGraph "UndirGraph" concept.
   371   ///\sa concept::UndirGraph.
   372   ///
   373   ///\todo Snapshot hasn't been implemented yet.
   374   ///
   375   class UndirSmartGraph : public ExtendedUndirSmartGraphBase {
   376   };
   377 
   378 
   379   class SmartUndirBipartiteGraphBase {
   380   public:
   381 
   382     class NodeSetError : public LogicError {
   383       virtual const char* exceptionName() const { 
   384 	return "lemon::FullUndirBipartiteGraph::NodeSetError";
   385       }
   386     };
   387 
   388   protected:
   389 
   390     struct NodeT {
   391       int first;
   392       NodeT() {}
   393       NodeT(int _first) : first(_first) {}
   394     };
   395 
   396     struct EdgeT {
   397       int upper, next_down;
   398       int lower, next_up;
   399     };
   400 
   401     std::vector<NodeT> upperNodes;
   402     std::vector<NodeT> lowerNodes;
   403 
   404     std::vector<EdgeT> edges;
   405 
   406   public:
   407   
   408     class Node {
   409       friend class SmartUndirBipartiteGraphBase;
   410     protected:
   411       int id;
   412 
   413       Node(int _id) : id(_id) {}
   414     public:
   415       Node() {}
   416       Node(Invalid) { id = -1; }
   417       bool operator==(const Node i) const {return id==i.id;}
   418       bool operator!=(const Node i) const {return id!=i.id;}
   419       bool operator<(const Node i) const {return id<i.id;}
   420     };
   421 
   422     class Edge {
   423       friend class SmartUndirBipartiteGraphBase;
   424     protected:
   425       int id;
   426 
   427       Edge(int _id) { id = _id;}
   428     public:
   429       Edge() {}
   430       Edge (Invalid) { id = -1; }
   431       bool operator==(const Edge i) const {return id==i.id;}
   432       bool operator!=(const Edge i) const {return id!=i.id;}
   433       bool operator<(const Edge i) const {return id<i.id;}
   434     };
   435 
   436     void firstUpper(Node& node) const {
   437       node.id = 2 * upperNodes.size() - 2;
   438       if (node.id < 0) node.id = -1; 
   439     }
   440     void nextUpper(Node& node) const {
   441       node.id -= 2;
   442       if (node.id < 0) node.id = -1; 
   443     }
   444 
   445     void firstLower(Node& node) const {
   446       node.id = 2 * lowerNodes.size() - 1;
   447     }
   448     void nextLower(Node& node) const {
   449       node.id -= 2;
   450     }
   451 
   452     void first(Node& node) const {
   453       if (upperNodes.size() > 0) {
   454 	node.id = 2 * upperNodes.size() - 2;
   455       } else {
   456 	node.id = 2 * lowerNodes.size() - 1;
   457       }
   458     }
   459     void next(Node& node) const {
   460       node.id -= 2;
   461       if (node.id == -2) {
   462 	node.id = 2 * lowerNodes.size() - 1;
   463       }
   464     }
   465   
   466     void first(Edge& edge) const {
   467       edge.id = edges.size() - 1;
   468     }
   469     void next(Edge& edge) const {
   470       --edge.id;
   471     }
   472 
   473     void firstDown(Edge& edge, const Node& node) const {
   474       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
   475       edge.id = upperNodes[node.id >> 1].first;
   476     }
   477     void nextDown(Edge& edge) const {
   478       edge.id = edges[edge.id].next_down;
   479     }
   480 
   481     void firstUp(Edge& edge, const Node& node) const {
   482       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
   483       edge.id = lowerNodes[node.id >> 1].first;
   484     }
   485     void nextUp(Edge& edge) const {
   486       edge.id = edges[edge.id].next_up;
   487     }
   488 
   489     static int id(const Node& node) {
   490       return node.id;
   491     }
   492     static Node nodeFromId(int id) {
   493       return Node(id);
   494     }
   495     int maxNodeId() const {
   496       return upperNodes.size() > lowerNodes.size() ?
   497 	upperNodes.size() * 2 - 2 : lowerNodes.size() * 2 - 1;
   498     }
   499   
   500     static int id(const Edge& edge) {
   501       return edge.id;
   502     }
   503     static Edge edgeFromId(int id) {
   504       return Edge(id);
   505     }
   506     int maxEdgeId() const {
   507       return edges.size();
   508     }
   509   
   510     static int upperId(const Node& node) {
   511       return node.id >> 1;
   512     }
   513     static Node fromUpperId(int id, Node) {
   514       return Node(id << 1);
   515     }
   516     int maxUpperId() const {
   517       return upperNodes.size();
   518     }
   519 
   520     static int lowerId(const Node& node) {
   521       return node.id >> 1;
   522     }
   523     static Node fromLowerId(int id) {
   524       return Node((id << 1) + 1);
   525     }
   526     int maxLowerId() const {
   527       return lowerNodes.size();
   528     }
   529 
   530     Node upperNode(const Edge& edge) const {
   531       return Node(edges[edge.id].upper);
   532     }
   533     Node lowerNode(const Edge& edge) const {
   534       return Node(edges[edge.id].lower);
   535     }
   536 
   537     static bool upper(const Node& node) {
   538       return (node.id & 1) == 0;
   539     }
   540 
   541     static bool lower(const Node& node) {
   542       return (node.id & 1) == 1;
   543     }
   544 
   545     Node addUpperNode() {
   546       NodeT nodeT;
   547       nodeT.first = -1;
   548       upperNodes.push_back(nodeT);
   549       return Node(upperNodes.size() * 2 - 2);
   550     }
   551 
   552     Node addLowerNode() {
   553       NodeT nodeT;
   554       nodeT.first = -1;
   555       lowerNodes.push_back(nodeT);
   556       return Node(lowerNodes.size() * 2 - 1);
   557     }
   558 
   559     Edge addEdge(const Node& source, const Node& target) {
   560       LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
   561       EdgeT edgeT;
   562       if ((source.id & 1) == 0) {
   563 	edgeT.upper = source.id;
   564 	edgeT.lower = target.id;
   565       } else {
   566 	edgeT.upper = target.id;
   567 	edgeT.lower = source.id;
   568       }
   569       edgeT.next_down = upperNodes[edgeT.upper >> 1].first;
   570       upperNodes[edgeT.upper >> 1].first = edges.size();
   571       edgeT.next_up = lowerNodes[edgeT.lower >> 1].first;
   572       lowerNodes[edgeT.lower >> 1].first = edges.size();
   573       edges.push_back(edgeT);
   574       return Edge(edges.size() - 1);
   575     }
   576 
   577     void clear() {
   578       upperNodes.clear();
   579       lowerNodes.clear();
   580       edges.clear();
   581     }
   582 
   583   };
   584 
   585 
   586   typedef ClearableUndirBipartiteGraphExtender<
   587     ExtendableUndirBipartiteGraphExtender<
   588     MappableUndirBipartiteGraphExtender<
   589     IterableUndirBipartiteGraphExtender<
   590     AlterableUndirBipartiteGraphExtender<
   591     UndirBipartiteGraphExtender <
   592     SmartUndirBipartiteGraphBase> > > > > >
   593   ExtendedSmartUndirBipartiteGraphBase;
   594 
   595 
   596   class SmartUndirBipartiteGraph : 
   597     public ExtendedSmartUndirBipartiteGraphBase {
   598   };
   599 
   600   
   601   /// @}  
   602 } //namespace lemon
   603 
   604 
   605 #endif //LEMON_SMART_GRAPH_H