lemon-0.x: src/lemon/smart_graph.h@4b0468de3a31

     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_notifier.h>

    32 #include <lemon/default_map.h>

    34 #include <lemon/undir_graph_extender.h>

    36 #include <lemon/utility.h>

    38 namespace lemon {

    40   /// \addtogroup graphs

    41   /// @{

    43   class SmartGraph;

    44   ///Base of SmartGraph

    46   ///Base of SmartGraph

    47   ///

    48   class SmartGraphBase {

    50     friend class SmatGraph;

    52   protected:

    53     struct NodeT

    54     {

    55       int first_in,first_out;

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

    57     };

    58     struct EdgeT

    59     {

    60       int target, source, next_in, next_out;

    61       //FIXME: is this necessary?

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

    63     };

    65     std::vector<NodeT> nodes;

    67     std::vector<EdgeT> edges;

    70   public:

    72     typedef SmartGraphBase Graph;

    74     class Node;

    75     class Edge;

    78   public:

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

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

    83     typedef True NodeNumTag;

    84     typedef True EdgeNumTag;

    86     ///Number of nodes.

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

    88     ///Number of edges.

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

    91     /// Maximum node ID.

    93     /// Maximum node ID.

    94     ///\sa id(Node)

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

    96     /// Maximum edge ID.

    98     /// Maximum edge ID.

    99     ///\sa id(Edge)

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

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

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

   105     /// Node ID.

   107     /// The ID of a valid Node is a nonnegative integer not greater than

   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().

   110     ///

   111     /// The ID of the \ref INVALID node is -1.

   112     ///\return The ID of the node \c v.

   113     static int id(Node v) { return v.n; }

   114     /// Edge ID.

   116     /// The ID of a valid Edge is a nonnegative integer not greater than

   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().

   119     ///

   120     /// The ID of the \ref INVALID edge is -1.

   121     ///\return The ID of the edge \c e.

   122     static int id(Edge e) { return e.n; }

   124     static Node fromId(int id, Node) { return Node(id);}

   126     static Edge fromId(int id, Edge) { return Edge(id);}

   128     Node addNode() {

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

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

   131       return n;

   132     }

   134     Edge addEdge(Node u, Node v) {

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

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

   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;

   141       return e;

   142     }

   144     void clear() {

   145       edges.clear();

   146       nodes.clear();

   147     }

   150     class Node {

   151       friend class SmartGraphBase;

   152       friend class SmartGraph;

   154     protected:

   155       int n;

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

   157       ///

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

   159     public:

   160       Node() {}

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

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

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

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

   165     };

   168     class Edge {

   169       friend class SmartGraphBase;

   170       friend class SmartGraph;

   172     protected:

   173       int n;

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

   175       ///

   176       Edge(int nn) {n=nn;}

   177     public:

   178       Edge() { }

   179       Edge (Invalid) { n=-1; }

   180       bool operator==(const Edge i) const {return n==i.n;}

   181       bool operator!=(const Edge i) const {return n!=i.n;}

   182       bool operator<(const Edge i) const {return n<i.n;}

   183     };

   185     void first(Node& node) const {

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

   187     }

   189     static void next(Node& node) {

   190       --node.n;

   191     }

   193     void first(Edge& edge) const {

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

   195     }

   197     static void next(Edge& edge) {

   198       --edge.n;

   199     }

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

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

   203     }

   205     void nextOut(Edge& edge) const {

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

   207     }

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

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

   211     }

   213     void nextIn(Edge& edge) const {

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

   215     }

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

   218     {

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

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

   221       prev.n=e;

   222       return prev;

   223     }

   225   };

   227   typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase;

   228   typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase;

   229   typedef DefaultMappableGraphExtender<IterableSmartGraphBase> MappableSmartGraphBase;

   230   typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase;

   231   typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase;

   233   ///A smart graph class.

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

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

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

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

   239   ///It conforms to

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

   241   ///\sa concept::ExtendableGraph.

   242   ///

   243   ///\author Alpar Juttner

   244   class SmartGraph : public ClearableSmartGraphBase {

   245   public:

   246     /// Finds an edge between two nodes.

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

   249     ///

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

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

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

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

   254     ///

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

   256     /// \code

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

   258     ///   ...

   259     /// }

   260     /// \endcode

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

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

   263     {

   264       return _findEdge(u,v,prev);

   265     }

   267     class SnapShot;

   268     friend class SnapShot;

   270   protected:

   271     void restoreSnapShot(const SnapShot &s)

   272     {

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

   274 	Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));

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

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

   277 	edges.pop_back();

   278       }

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

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

   281 	Parent::getNotifier(Node()).erase(Node(nodes.size()-1));

   282 	nodes.pop_back();

   283       }

   284     }

   286   public:

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

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

   290     ///

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

   292     ///restore() function.

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

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

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

   296     ///

   297     class SnapShot

   298     {

   299       SmartGraph *g;

   300     protected:

   301       friend class SmartGraph;

   302       unsigned int node_num;

   303       unsigned int edge_num;

   304     public:

   305       ///Default constructur.

   307       ///Default constructur.

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

   309       ///

   310       SnapShot() : g(0) {}

   311       ///Constructor that immediately makes a snapshot

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

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

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

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

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

   318       }

   320       ///Make a snapshot.

   322       ///Make a snapshot of the graph.

   323       ///

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

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

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

   327       void save(SmartGraph &_g)

   328       {

   329 	g=&_g;

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

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

   332       }

   334       ///Undo the changes until a snapshot.

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

   337       ///

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

   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().

   345       void restore()

   346       {

   347 	g->restoreSnapShot(*this);

   348       }

   349     };

   350   };

   353   /**************** Undirected List Graph ****************/

   355   typedef ClearableUndirGraphExtender<

   356     ExtendableUndirGraphExtender<

   357     MappableUndirGraphExtender<

   358     IterableUndirGraphExtender<

   359     AlterableUndirGraphExtender<

   360     UndirGraphExtender<SmartGraphBase> > > > > > UndirSmartGraphBase;

   362   ///A smart undirected graph class.

   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 UndirSmartGraphBase {

   375   };

   378   /// @}

   379 } //namespace lemon

   382 #endif //LEMON_SMART_GRAPH_H

author	marci
	Thu, 17 Feb 2005 15:14:13 +0000
changeset 1153	4b0468de3a31
parent 1082	e9eae612f01c
child 1161	1c9658d51c8d
permissions	-rw-r--r--