COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 2115:4cd528a30ec1

Last change on this file since 2115:4cd528a30ec1 was 2115:4cd528a30ec1, checked in by Balazs Dezso, 13 years ago

Splitted graph files

File size: 9.2 KB
RevLine 
[906]1/* -*- C++ -*-
2 *
[1956]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
[1359]7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[906]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 */
[105]18
[921]19#ifndef LEMON_SMART_GRAPH_H
20#define LEMON_SMART_GRAPH_H
[104]21
[491]22///\ingroup graphs
[242]23///\file
[2115]24///\brief SmartGraph class.
[242]25
[104]26#include <vector>
27
[1993]28#include <lemon/bits/invalid.h>
[157]29
[1791]30#include <lemon/bits/graph_extender.h>
[1034]31
[1993]32#include <lemon/bits/utility.h>
[782]33
[1979]34#include <lemon/bits/graph_extender.h>
35
[921]36namespace lemon {
[104]37
[973]38  class SmartGraph;
[969]39  ///Base of SmartGraph
40
41  ///Base of SmartGraph
42  ///
[946]43  class SmartGraphBase {
[104]44
[973]45    friend class SmatGraph;
46
47  protected:
[104]48    struct NodeT
49    {
50      int first_in,first_out;     
[157]51      NodeT() : first_in(-1), first_out(-1) {}
[104]52    };
53    struct EdgeT
54    {
[986]55      int target, source, next_in, next_out;     
[104]56      //FIXME: is this necessary?
[157]57      EdgeT() : next_in(-1), next_out(-1) {} 
[104]58    };
59
60    std::vector<NodeT> nodes;
[129]61
[104]62    std::vector<EdgeT> edges;
63   
[185]64   
[104]65  public:
[782]66
[946]67    typedef SmartGraphBase Graph;
[104]68
[164]69    class Node;
70    class Edge;
[108]71
[104]72   
73  public:
74
[946]75    SmartGraphBase() : nodes(), edges() { }
[1718]76    SmartGraphBase(const SmartGraphBase &_g)
77      : nodes(_g.nodes), edges(_g.edges) { }
[104]78   
[977]79    typedef True NodeNumTag;
80    typedef True EdgeNumTag;
81
[813]82    ///Number of nodes.
83    int nodeNum() const { return nodes.size(); }
84    ///Number of edges.
85    int edgeNum() const { return edges.size(); }
[104]86
[813]87    /// Maximum node ID.
88   
89    /// Maximum node ID.
90    ///\sa id(Node)
[1791]91    int maxNodeId() const { return nodes.size()-1; }
[813]92    /// Maximum edge ID.
93   
94    /// Maximum edge ID.
95    ///\sa id(Edge)
[1791]96    int maxEdgeId() const { return edges.size()-1; }
[108]97
[986]98    Node source(Edge e) const { return edges[e.n].source; }
99    Node target(Edge e) const { return edges[e.n].target; }
[104]100
[813]101    /// Node ID.
102   
103    /// The ID of a valid Node is a nonnegative integer not greater than
[1791]104    /// \ref maxNodeId(). The range of the ID's is not surely continuous
105    /// and the greatest node ID can be actually less then \ref maxNodeId().
[813]106    ///
107    /// The ID of the \ref INVALID node is -1.
108    ///\return The ID of the node \c v.
[713]109    static int id(Node v) { return v.n; }
[813]110    /// Edge ID.
111   
112    /// The ID of a valid Edge is a nonnegative integer not greater than
[1791]113    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
114    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
[813]115    ///
116    /// The ID of the \ref INVALID edge is -1.
117    ///\return The ID of the edge \c e.
[713]118    static int id(Edge e) { return e.n; }
[104]119
[2076]120    /// \brief Returns the node from its \c id.
121    ///
122    /// Returns the node from its \c id. If there is not node
123    /// with the given id the effect of the function is undefinied.
[1791]124    static Node nodeFromId(int id) { return Node(id);}
[1106]125
[2076]126    /// \brief Returns the edge from its \c id.
127    ///
128    /// Returns the edge from its \c id. If there is not edge
129    /// with the given id the effect of the function is undefinied.
[1791]130    static Edge edgeFromId(int id) { return Edge(id);}
[1106]131
[164]132    Node addNode() {
133      Node n; n.n=nodes.size();
[104]134      nodes.push_back(NodeT()); //FIXME: Hmmm...
135      return n;
136    }
[108]137   
[164]138    Edge addEdge(Node u, Node v) {
139      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
[986]140      edges[e.n].source=u.n; edges[e.n].target=v.n;
[104]141      edges[e.n].next_out=nodes[u.n].first_out;
142      edges[e.n].next_in=nodes[v.n].first_in;
143      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
[108]144
[104]145      return e;
146    }
147
[782]148    void clear() {
149      edges.clear();
150      nodes.clear();
151    }
[104]152
[946]153
[164]154    class Node {
[946]155      friend class SmartGraphBase;
[973]156      friend class SmartGraph;
[104]157
158    protected:
159      int n;
[164]160      Node(int nn) {n=nn;}
[104]161    public:
[164]162      Node() {}
[503]163      Node (Invalid) { n=-1; }
[164]164      bool operator==(const Node i) const {return n==i.n;}
165      bool operator!=(const Node i) const {return n!=i.n;}
166      bool operator<(const Node i) const {return n<i.n;}
[104]167    };
168   
169
[164]170    class Edge {
[946]171      friend class SmartGraphBase;
[973]172      friend class SmartGraph;
[185]173
[104]174    protected:
175      int n;
[905]176      Edge(int nn) {n=nn;}
[706]177    public:
[164]178      Edge() { }
[174]179      Edge (Invalid) { n=-1; }
[164]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;}
[946]183    };
[905]184
[946]185    void first(Node& node) const {
186      node.n = nodes.size() - 1;
187    }
188
189    static void next(Node& node) {
190      --node.n;
191    }
192
193    void first(Edge& edge) const {
194      edge.n = edges.size() - 1;
195    }
196
197    static void next(Edge& edge) {
198      --edge.n;
199    }
200
201    void firstOut(Edge& edge, const Node& node) const {
202      edge.n = nodes[node.n].first_out;
203    }
204
205    void nextOut(Edge& edge) const {
206      edge.n = edges[edge.n].next_out;
207    }
208
209    void firstIn(Edge& edge, const Node& node) const {
210      edge.n = nodes[node.n].first_in;
211    }
[104]212   
[946]213    void nextIn(Edge& edge) const {
214      edge.n = edges[edge.n].next_in;
215    }
[105]216
[1284]217    Node _split(Node n, bool connect = true)
218    {
219      Node b = addNode();
220      nodes[b.n].first_out=nodes[n.n].first_out;
221      nodes[n.n].first_out=-1;
222      for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
223      if(connect) addEdge(n,b);
224      return b;
225    }
226
[104]227  };
[185]228
[1979]229  typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
[937]230
[1791]231  /// \ingroup graphs
[1161]232
[950]233  ///A smart graph class.
[937]234
[950]235  ///This is a simple and fast graph implementation.
236  ///It is also quite memory efficient, but at the price
[974]237  ///that <b> it does support only limited (only stack-like)
238  ///node and edge deletions</b>.
[950]239  ///It conforms to
[2111]240  ///the \ref concept::Graph "Graph" concept.
241  ///\sa concept::Graph.
[950]242  ///
243  ///\author Alpar Juttner
[1669]244  class SmartGraph : public ExtendedSmartGraphBase {
[969]245  public:
[1979]246
247    typedef ExtendedSmartGraphBase Parent;
248
[1770]249    class Snapshot;
250    friend class Snapshot;
[973]251
[1011]252  protected:
[1770]253    void restoreSnapshot(const Snapshot &s)
[973]254    {
[1457]255      while(s.edge_num<edges.size()) {
[1040]256        Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
[986]257        nodes[edges.back().target].first_in=edges.back().next_in;
258        nodes[edges.back().source].first_out=edges.back().next_out;
[973]259        edges.pop_back();
260      }
261      //nodes.resize(s.nodes_num);
[1457]262      while(s.node_num<nodes.size()) {
[1040]263        Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
[973]264        nodes.pop_back();
265      }
[1011]266    }   
267
268  public:
[1284]269
270    ///Split a node.
271   
272    ///This function splits a node. First a new node is added to the graph,
273    ///then the source of each outgoing edge of \c n is moved to this new node.
274    ///If \c connect is \c true (this is the default value), then a new edge
275    ///from \c n to the newly created node is also added.
276    ///\return The newly created node.
277    ///
278    ///\note The <tt>Edge</tt>s
279    ///referencing a moved edge remain
280    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
281    ///may be invalidated.
[1770]282    ///\warning This functionality cannot be used together with the Snapshot
[1284]283    ///feature.
284    ///\todo It could be implemented in a bit faster way.
285    Node split(Node n, bool connect = true)
286    {
[1718]287      Node b = _split(n,connect);
288      return b;
[1284]289    }
290 
291
[1011]292    ///Class to make a snapshot of the graph and to restrore to it later.
293
294    ///Class to make a snapshot of the graph and to restrore to it later.
295    ///
296    ///The newly added nodes and edges can be removed using the
297    ///restore() function.
298    ///\note After you restore a state, you cannot restore
299    ///a later state, in other word you cannot add again the edges deleted
[1770]300    ///by restore() using another Snapshot instance.
[1011]301    ///
[1770]302    class Snapshot
[1011]303    {
304      SmartGraph *g;
305    protected:
306      friend class SmartGraph;
307      unsigned int node_num;
308      unsigned int edge_num;
309    public:
[1274]310      ///Default constructor.
[1011]311     
[1274]312      ///Default constructor.
[1011]313      ///To actually make a snapshot you must call save().
314      ///
[1770]315      Snapshot() : g(0) {}
[1011]316      ///Constructor that immediately makes a snapshot
317     
318      ///This constructor immediately makes a snapshot of the graph.
319      ///\param _g The graph we make a snapshot of.
[1770]320      Snapshot(SmartGraph &_g) :g(&_g) {
[1011]321        node_num=g->nodes.size();
322        edge_num=g->edges.size();
323      }
324
325      ///Make a snapshot.
326
327      ///Make a snapshot of the graph.
328      ///
329      ///This function can be called more than once. In case of a repeated
330      ///call, the previous snapshot gets lost.
331      ///\param _g The graph we make the snapshot of.
332      void save(SmartGraph &_g)
333      {
334        g=&_g;
335        node_num=g->nodes.size();
336        edge_num=g->edges.size();
337      }
338
339      ///Undo the changes until a snapshot.
340     
341      ///Undo the changes until a snapshot created by save().
342      ///
343      ///\note After you restored a state, you cannot restore
344      ///a later state, in other word you cannot add again the edges deleted
345      ///by restore().
346      ///
347      ///\todo This function might be called undo().
348     
349      void restore()
350      {
[1770]351        g->restoreSnapshot(*this);
[1011]352      }
353    };
[973]354  };
[1034]355
356
[921]357} //namespace lemon
[104]358
[157]359
[921]360#endif //LEMON_SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.