lemon/smart_graph.h
author alpar
Fri, 18 Nov 2005 11:17:08 +0000
changeset 1817 dc3516405f8f
parent 1770 657de7e5043c
child 1820 22099ef840d7
permissions -rw-r--r--
- Spellcheck (pathes->paths)
     1 /* -*- C++ -*-
     2  * lemon/smart_graph.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 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 
    37 namespace lemon {
    38 
    39   class SmartGraph;
    40   ///Base of SmartGraph
    41 
    42   ///Base of SmartGraph
    43   ///
    44   class SmartGraphBase {
    45 
    46     friend class SmatGraph;
    47 
    48   protected:
    49     struct NodeT 
    50     {
    51       int first_in,first_out;      
    52       NodeT() : first_in(-1), first_out(-1) {}
    53     };
    54     struct EdgeT 
    55     {
    56       int target, source, next_in, next_out;      
    57       //FIXME: is this necessary?
    58       EdgeT() : next_in(-1), next_out(-1) {}  
    59     };
    60 
    61     std::vector<NodeT> nodes;
    62 
    63     std::vector<EdgeT> edges;
    64     
    65     
    66   public:
    67 
    68     typedef SmartGraphBase Graph;
    69 
    70     class Node;
    71     class Edge;
    72 
    73     
    74   public:
    75 
    76     SmartGraphBase() : nodes(), edges() { }
    77     SmartGraphBase(const SmartGraphBase &_g) 
    78       : nodes(_g.nodes), edges(_g.edges) { }
    79     
    80     typedef True NodeNumTag;
    81     typedef True EdgeNumTag;
    82 
    83     ///Number of nodes.
    84     int nodeNum() const { return nodes.size(); }
    85     ///Number of edges.
    86     int edgeNum() const { return edges.size(); }
    87 
    88     /// Maximum node ID.
    89     
    90     /// Maximum node ID.
    91     ///\sa id(Node)
    92     int maxNodeId() const { return nodes.size()-1; }
    93     /// Maximum edge ID.
    94     
    95     /// Maximum edge ID.
    96     ///\sa id(Edge)
    97     int maxEdgeId() const { return edges.size()-1; }
    98 
    99     Node source(Edge e) const { return edges[e.n].source; }
   100     Node target(Edge e) const { return edges[e.n].target; }
   101 
   102     /// Node ID.
   103     
   104     /// The ID of a valid Node is a nonnegative integer not greater than
   105     /// \ref maxNodeId(). The range of the ID's is not surely continuous
   106     /// and the greatest node ID can be actually less then \ref maxNodeId().
   107     ///
   108     /// The ID of the \ref INVALID node is -1.
   109     ///\return The ID of the node \c v. 
   110     static int id(Node v) { return v.n; }
   111     /// Edge ID.
   112     
   113     /// The ID of a valid Edge is a nonnegative integer not greater than
   114     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
   115     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
   116     ///
   117     /// The ID of the \ref INVALID edge is -1.
   118     ///\return The ID of the edge \c e. 
   119     static int id(Edge e) { return e.n; }
   120 
   121     static Node nodeFromId(int id) { return Node(id);}
   122 
   123     static Edge edgeFromId(int id) { return Edge(id);}
   124 
   125     Node addNode() {
   126       Node n; n.n=nodes.size();
   127       nodes.push_back(NodeT()); //FIXME: Hmmm...
   128       return n;
   129     }
   130     
   131     Edge addEdge(Node u, Node v) {
   132       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
   133       edges[e.n].source=u.n; edges[e.n].target=v.n;
   134       edges[e.n].next_out=nodes[u.n].first_out;
   135       edges[e.n].next_in=nodes[v.n].first_in;
   136       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
   137 
   138       return e;
   139     }
   140 
   141     void clear() {
   142       edges.clear();
   143       nodes.clear();
   144     }
   145 
   146 
   147     class Node {
   148       friend class SmartGraphBase;
   149       friend class SmartGraph;
   150 
   151     protected:
   152       int n;
   153       Node(int nn) {n=nn;}
   154     public:
   155       Node() {}
   156       Node (Invalid) { n=-1; }
   157       bool operator==(const Node i) const {return n==i.n;}
   158       bool operator!=(const Node i) const {return n!=i.n;}
   159       bool operator<(const Node i) const {return n<i.n;}
   160     };
   161     
   162 
   163     class Edge {
   164       friend class SmartGraphBase;
   165       friend class SmartGraph;
   166 
   167     protected:
   168       int n;
   169       Edge(int nn) {n=nn;}
   170     public:
   171       Edge() { }
   172       Edge (Invalid) { n=-1; }
   173       bool operator==(const Edge i) const {return n==i.n;}
   174       bool operator!=(const Edge i) const {return n!=i.n;}
   175       bool operator<(const Edge i) const {return n<i.n;}
   176     };
   177 
   178     void first(Node& node) const {
   179       node.n = nodes.size() - 1;
   180     }
   181 
   182     static void next(Node& node) {
   183       --node.n;
   184     }
   185 
   186     void first(Edge& edge) const {
   187       edge.n = edges.size() - 1;
   188     }
   189 
   190     static void next(Edge& edge) {
   191       --edge.n;
   192     }
   193 
   194     void firstOut(Edge& edge, const Node& node) const {
   195       edge.n = nodes[node.n].first_out;
   196     }
   197 
   198     void nextOut(Edge& edge) const {
   199       edge.n = edges[edge.n].next_out;
   200     }
   201 
   202     void firstIn(Edge& edge, const Node& node) const {
   203       edge.n = nodes[node.n].first_in;
   204     }
   205     
   206     void nextIn(Edge& edge) const {
   207       edge.n = edges[edge.n].next_in;
   208     }
   209 
   210     Node _split(Node n, bool connect = true)
   211     {
   212       Node b = addNode();
   213       nodes[b.n].first_out=nodes[n.n].first_out;
   214       nodes[n.n].first_out=-1;
   215       for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
   216       if(connect) addEdge(n,b);
   217       return b;
   218     }
   219 
   220   };
   221 
   222   typedef ClearableGraphExtender<
   223     ExtendableGraphExtender<
   224     MappableGraphExtender<
   225     IterableGraphExtender<
   226     AlterableGraphExtender<
   227     GraphExtender<SmartGraphBase> > > > > > ExtendedSmartGraphBase;
   228 
   229   /// \ingroup graphs
   230 
   231   ///A smart graph class.
   232 
   233   ///This is a simple and fast graph implementation.
   234   ///It is also quite memory efficient, but at the price
   235   ///that <b> it does support only limited (only stack-like)
   236   ///node and edge deletions</b>.
   237   ///It conforms to 
   238   ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
   239   ///\sa concept::ExtendableGraph.
   240   ///
   241   ///\author Alpar Juttner
   242   class SmartGraph : public ExtendedSmartGraphBase {
   243   public:
   244     
   245     class Snapshot;
   246     friend class Snapshot;
   247 
   248   protected:
   249     void restoreSnapshot(const Snapshot &s)
   250     {
   251       while(s.edge_num<edges.size()) {
   252 	Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
   253 	nodes[edges.back().target].first_in=edges.back().next_in;
   254 	nodes[edges.back().source].first_out=edges.back().next_out;
   255 	edges.pop_back();
   256       }
   257       //nodes.resize(s.nodes_num);
   258       while(s.node_num<nodes.size()) {
   259 	Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
   260 	nodes.pop_back();
   261       }
   262     }    
   263 
   264   public:
   265 
   266     ///Split a node.
   267     
   268     ///This function splits a node. First a new node is added to the graph,
   269     ///then the source of each outgoing edge of \c n is moved to this new node.
   270     ///If \c connect is \c true (this is the default value), then a new edge
   271     ///from \c n to the newly created node is also added.
   272     ///\return The newly created node.
   273     ///
   274     ///\note The <tt>Edge</tt>s
   275     ///referencing a moved edge remain
   276     ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
   277     ///may be invalidated.
   278     ///\warning This functionality cannot be used together with the Snapshot
   279     ///feature.
   280     ///\todo It could be implemented in a bit faster way.
   281     Node split(Node n, bool connect = true) 
   282     {
   283       Node b = _split(n,connect);
   284       return b;
   285     }
   286   
   287 
   288     ///Class to make a snapshot of the graph and to restrore to it later.
   289 
   290     ///Class to make a snapshot of the graph and to restrore to it later.
   291     ///
   292     ///The newly added nodes and edges can be removed using the
   293     ///restore() function.
   294     ///\note After you restore a state, you cannot restore
   295     ///a later state, in other word you cannot add again the edges deleted
   296     ///by restore() using another Snapshot instance.
   297     ///
   298     class Snapshot 
   299     {
   300       SmartGraph *g;
   301     protected:
   302       friend class SmartGraph;
   303       unsigned int node_num;
   304       unsigned int edge_num;
   305     public:
   306       ///Default constructor.
   307       
   308       ///Default constructor.
   309       ///To actually make a snapshot you must call save().
   310       ///
   311       Snapshot() : g(0) {}
   312       ///Constructor that immediately makes a snapshot
   313       
   314       ///This constructor immediately makes a snapshot of the graph.
   315       ///\param _g The graph we make a snapshot of.
   316       Snapshot(SmartGraph &_g) :g(&_g) {
   317 	node_num=g->nodes.size();
   318 	edge_num=g->edges.size();
   319       }
   320 
   321       ///Make a snapshot.
   322 
   323       ///Make a snapshot of the graph.
   324       ///
   325       ///This function can be called more than once. In case of a repeated
   326       ///call, the previous snapshot gets lost.
   327       ///\param _g The graph we make the snapshot of.
   328       void save(SmartGraph &_g) 
   329       {
   330 	g=&_g;
   331 	node_num=g->nodes.size();
   332 	edge_num=g->edges.size();
   333       }
   334 
   335       ///Undo the changes until a snapshot.
   336       
   337       ///Undo the changes until a snapshot created by save().
   338       ///
   339       ///\note After you restored a state, you cannot restore
   340       ///a later state, in other word you cannot add again the edges deleted
   341       ///by restore().
   342       ///
   343       ///\todo This function might be called undo().
   344       
   345       void restore()
   346       {
   347 	g->restoreSnapshot(*this);
   348       }
   349     };
   350   };
   351 
   352 
   353   /**************** Undirected List Graph ****************/
   354 
   355   typedef ClearableUndirGraphExtender<
   356     ExtendableUndirGraphExtender<
   357     MappableUndirGraphExtender<
   358     IterableUndirGraphExtender<
   359     AlterableUndirGraphExtender<
   360     UndirGraphExtender<SmartGraphBase> > > > > > ExtendedUndirSmartGraphBase;
   361 
   362   ///A smart undirected graph class.
   363 
   364   ///This is a simple and fast undirected graph implementation.
   365   ///It is also quite memory efficient, but at the price
   366   ///that <b> it does support only limited (only stack-like)
   367   ///node and edge deletions</b>.
   368   ///Except from this it conforms to 
   369   ///the \ref concept::UndirGraph "UndirGraph" concept.
   370   ///\sa concept::UndirGraph.
   371   ///
   372   ///\todo Snapshot hasn't been implemented yet.
   373   ///
   374   class UndirSmartGraph : public ExtendedUndirSmartGraphBase {
   375   };
   376 
   377   
   378   /// @}  
   379 } //namespace lemon
   380 
   381 
   382 #endif //LEMON_SMART_GRAPH_H