lemon-0.x: src/lemon/smart_graph.h@68beae6758a7

     1 /* -*- C++ -*-

     2  * src/lemon/smart_graph.h - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     5  * (Egervary Combinatorial Optimization Research Group, 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  */

    17 #ifndef LEMON_SMART_GRAPH_H

    18 #define LEMON_SMART_GRAPH_H

    20 ///\ingroup graphs

    21 ///\file

    22 ///\brief SmartGraph and SymSmartGraph classes.

    24 #include <vector>

    26 #include <lemon/invalid.h>

    28 #include <lemon/clearable_graph_extender.h>

    29 #include <lemon/extendable_graph_extender.h>

    30 #include <lemon/iterable_graph_extender.h>

    31 #include <lemon/alteration_observer_registry.h>

    32 #include <lemon/default_map.h>

    34 #include <lemon/utility.h>

    36 namespace lemon {

    38   /// \addtogroup graphs

    39   /// @{

    41   class SmartGraph;

    42   ///Base of SmartGraph

    44   ///Base of SmartGraph

    45   ///

    46   class SmartGraphBase {

    48     friend class SmatGraph;

    50   protected:

    51     struct NodeT

    52     {

    53       int first_in,first_out;

    54       NodeT() : first_in(-1), first_out(-1) {}

    55     };

    56     struct EdgeT

    57     {

    58       int target, source, next_in, next_out;

    59       //FIXME: is this necessary?

    60       EdgeT() : next_in(-1), next_out(-1) {}

    61     };

    63     std::vector<NodeT> nodes;

    65     std::vector<EdgeT> edges;

    68   public:

    70     typedef SmartGraphBase Graph;

    72     class Node;

    73     class Edge;

    76   public:

    78     SmartGraphBase() : nodes(), edges() { }

    79     SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { }

    81     typedef True NodeNumTag;

    82     typedef True EdgeNumTag;

    84     ///Number of nodes.

    85     int nodeNum() const { return nodes.size(); }

    86     ///Number of edges.

    87     int edgeNum() const { return edges.size(); }

    89     /// Maximum node ID.

    91     /// Maximum node ID.

    92     ///\sa id(Node)

    93     int maxId(Node = INVALID) const { return nodes.size()-1; }

    94     /// Maximum edge ID.

    96     /// Maximum edge ID.

    97     ///\sa id(Edge)

    98     int maxId(Edge = INVALID) const { return edges.size()-1; }

   100     Node source(Edge e) const { return edges[e.n].source; }

   101     Node target(Edge e) const { return edges[e.n].target; }

   103     /// Node ID.

   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.

   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; }

   122     Node addNode() {

   123       Node n; n.n=nodes.size();

   124       nodes.push_back(NodeT()); //FIXME: Hmmm...

   125       return n;

   126     }

   128     Edge addEdge(Node u, Node v) {

   129       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...

   130       edges[e.n].source=u.n; edges[e.n].target=v.n;

   131       edges[e.n].next_out=nodes[u.n].first_out;

   132       edges[e.n].next_in=nodes[v.n].first_in;

   133       nodes[u.n].first_out=nodes[v.n].first_in=e.n;

   135       return e;

   136     }

   138     void clear() {

   139       edges.clear();

   140       nodes.clear();

   141     }

   144     class Node {

   145       friend class SmartGraphBase;

   146       friend class SmartGraph;

   148     protected:

   149       int n;

   150       ///\todo It should be removed (or at least define a setToId() instead).

   151       ///

   152       Node(int nn) {n=nn;}

   153     public:

   154       Node() {}

   155       Node (Invalid) { n=-1; }

   156       bool operator==(const Node i) const {return n==i.n;}

   157       bool operator!=(const Node i) const {return n!=i.n;}

   158       bool operator<(const Node i) const {return n<i.n;}

   159     };

   162     class Edge {

   163       friend class SmartGraphBase;

   164       friend class SmartGraph;

   166     protected:

   167       int n;

   168       ///\todo It should be removed (or at least define a setToId() instead).

   169       ///

   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     };

   179     void first(Node& node) const {

   180       node.n = nodes.size() - 1;

   181     }

   183     static void next(Node& node) {

   184       --node.n;

   185     }

   187     void first(Edge& edge) const {

   188       edge.n = edges.size() - 1;

   189     }

   191     static void next(Edge& edge) {

   192       --edge.n;

   193     }

   195     void firstOut(Edge& edge, const Node& node) const {

   196       edge.n = nodes[node.n].first_out;

   197     }

   199     void nextOut(Edge& edge) const {

   200       edge.n = edges[edge.n].next_out;

   201     }

   203     void firstIn(Edge& edge, const Node& node) const {

   204       edge.n = nodes[node.n].first_in;

   205     }

   207     void nextIn(Edge& edge) const {

   208       edge.n = edges[edge.n].next_in;

   209     }

   211     Edge _findEdge(Node u,Node v, Edge prev = INVALID)

   212     {

   213       int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;

   214       while(e!=-1 && edges[e].source!=v.n) e = edges[e].next_out;

   215       prev.n=e;

   216       return prev;

   217     }

   219   };

   221   typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase;

   222   typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase;

   223   typedef DefaultMappableGraphExtender<IterableSmartGraphBase> MappableSmartGraphBase;

   224   typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase;

   225   typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase;

   227   ///A smart graph class.

   229   ///This is a simple and fast graph implementation.

   230   ///It is also quite memory efficient, but at the price

   231   ///that <b> it does support only limited (only stack-like)

   232   ///node and edge deletions</b>.

   233   ///It conforms to

   234   ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.

   235   ///\sa concept::ExtendableGraph.

   236   ///

   237   ///\todo Some member functions could be \c static.

   238   ///

   239   ///\author Alpar Juttner

   240   class SmartGraph : public ClearableSmartGraphBase {

   241   public:

   242     /// Finds an edge between two nodes.

   244     /// Finds an edge from node \c u to node \c v.

   245     ///

   246     /// If \c prev is \ref INVALID (this is the default value), then

   247     /// it finds the first edge from \c u to \c v. Otherwise it looks for

   248     /// the next edge from \c u to \c v after \c prev.

   249     /// \return The found edge or \ref INVALID if there is no such an edge.

   250     ///

   251     /// Thus you can iterate through each edge from \c u to \c v as it follows.

   252     /// \code

   253     /// for(Edge e=G.findEdge(u,v);e!=INVALID;e=G.findEdge(u,v,e)) {

   254     ///   ...

   255     /// }

   256     /// \endcode

   257     /// \todo Possibly it should be a global function.

   258     Edge findEdge(Node u,Node v, Edge prev = INVALID)

   259     {

   260       return _findEdge(u,v,prev);

   261     }

   263     class SnapShot;

   264     friend class SnapShot;

   266   protected:

   267     void restoreSnapShot(const SnapShot &s)

   268     {

   269       while(s.edge_num>edges.size()) {

   270 	edge_observers.erase(Edge(edges.size()-1));

   271 	nodes[edges.back().target].first_in=edges.back().next_in;

   272 	nodes[edges.back().source].first_out=edges.back().next_out;

   273 	edges.pop_back();

   274       }

   275       //nodes.resize(s.nodes_num);

   276       while(s.node_num>nodes.size()) {

   277 	node_observers.erase(Node(nodes.size()-1));

   278 	nodes.pop_back();

   279       }

   280     }

   282   public:

   283     ///Class to make a snapshot of the graph and to restrore to it later.

   285     ///Class to make a snapshot of the graph and to restrore to it later.

   286     ///

   287     ///The newly added nodes and edges can be removed using the

   288     ///restore() function.

   289     ///\note After you restore a state, you cannot restore

   290     ///a later state, in other word you cannot add again the edges deleted

   291     ///by restore() using another SnapShot instance.

   292     ///

   293     ///\ingroup graphs

   294     class SnapShot

   295     {

   296       SmartGraph *g;

   297     protected:

   298       friend class SmartGraph;

   299       unsigned int node_num;

   300       unsigned int edge_num;

   301     public:

   302       ///Default constructur.

   304       ///Default constructur.

   305       ///To actually make a snapshot you must call save().

   306       ///

   307       SnapShot() : g(0) {}

   308       ///Constructor that immediately makes a snapshot

   310       ///This constructor immediately makes a snapshot of the graph.

   311       ///\param _g The graph we make a snapshot of.

   312       SnapShot(SmartGraph &_g) :g(&_g) {

   313 	node_num=g->nodes.size();

   314 	edge_num=g->edges.size();

   315       }

   317       ///Make a snapshot.

   319       ///Make a snapshot of the graph.

   320       ///

   321       ///This function can be called more than once. In case of a repeated

   322       ///call, the previous snapshot gets lost.

   323       ///\param _g The graph we make the snapshot of.

   324       void save(SmartGraph &_g)

   325       {

   326 	g=&_g;

   327 	node_num=g->nodes.size();

   328 	edge_num=g->edges.size();

   329       }

   331       ///Undo the changes until a snapshot.

   333       ///Undo the changes until a snapshot created by save().

   334       ///

   335       ///\param s an internal stucture given back by save()

   336       ///\note After you restored a state, you cannot restore

   337       ///a later state, in other word you cannot add again the edges deleted

   338       ///by restore().

   339       ///

   340       ///\todo This function might be called undo().

   342       void restore()

   343       {

   344 	g->restoreSnapShot(*this);

   345       }

   346     };

   347   };

   349   /// @}

   350 } //namespace lemon

   353 #endif //LEMON_SMART_GRAPH_H

author	ladanyi
	Mon, 22 Nov 2004 14:39:40 +0000
changeset 1018	68beae6758a7
parent 986	e997802b855c
child 1034	be6ee857b72d
permissions	-rw-r--r--