COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 1998:2ba916d7aae3

Last change on this file since 1998:2ba916d7aae3 was 1995:c1fc2c14a3ae, checked in by Balazs Dezso, 14 years ago

Bugfix in bpugraph

File size: 14.8 KB
Line 
1/* -*- C++ -*-
2 *
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
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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 */
18
19#ifndef LEMON_SMART_GRAPH_H
20#define LEMON_SMART_GRAPH_H
21
22///\ingroup graphs
23///\file
24///\brief SmartGraph and SmartUGraph classes.
25
26#include <vector>
27
28#include <lemon/bits/invalid.h>
29
30#include <lemon/bits/graph_extender.h>
31
32#include <lemon/bits/utility.h>
33#include <lemon/error.h>
34
35#include <lemon/bits/graph_extender.h>
36
37namespace 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 GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
223
224  /// \ingroup graphs
225
226  ///A smart graph class.
227
228  ///This is a simple and fast graph implementation.
229  ///It is also quite memory efficient, but at the price
230  ///that <b> it does support only limited (only stack-like)
231  ///node and edge deletions</b>.
232  ///It conforms to
233  ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
234  ///\sa concept::ExtendableGraph.
235  ///
236  ///\author Alpar Juttner
237  class SmartGraph : public ExtendedSmartGraphBase {
238  public:
239
240    typedef ExtendedSmartGraphBase Parent;
241
242    class Snapshot;
243    friend class Snapshot;
244
245  protected:
246    void restoreSnapshot(const Snapshot &s)
247    {
248      while(s.edge_num<edges.size()) {
249        Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
250        nodes[edges.back().target].first_in=edges.back().next_in;
251        nodes[edges.back().source].first_out=edges.back().next_out;
252        edges.pop_back();
253      }
254      //nodes.resize(s.nodes_num);
255      while(s.node_num<nodes.size()) {
256        Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
257        nodes.pop_back();
258      }
259    }   
260
261  public:
262
263    ///Split a node.
264   
265    ///This function splits a node. First a new node is added to the graph,
266    ///then the source of each outgoing edge of \c n is moved to this new node.
267    ///If \c connect is \c true (this is the default value), then a new edge
268    ///from \c n to the newly created node is also added.
269    ///\return The newly created node.
270    ///
271    ///\note The <tt>Edge</tt>s
272    ///referencing a moved edge remain
273    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
274    ///may be invalidated.
275    ///\warning This functionality cannot be used together with the Snapshot
276    ///feature.
277    ///\todo It could be implemented in a bit faster way.
278    Node split(Node n, bool connect = true)
279    {
280      Node b = _split(n,connect);
281      return b;
282    }
283 
284
285    ///Class to make a snapshot of the graph and to restrore to it later.
286
287    ///Class to make a snapshot of the graph and to restrore to it later.
288    ///
289    ///The newly added nodes and edges can be removed using the
290    ///restore() function.
291    ///\note After you restore a state, you cannot restore
292    ///a later state, in other word you cannot add again the edges deleted
293    ///by restore() using another Snapshot instance.
294    ///
295    class Snapshot
296    {
297      SmartGraph *g;
298    protected:
299      friend class SmartGraph;
300      unsigned int node_num;
301      unsigned int edge_num;
302    public:
303      ///Default constructor.
304     
305      ///Default constructor.
306      ///To actually make a snapshot you must call save().
307      ///
308      Snapshot() : g(0) {}
309      ///Constructor that immediately makes a snapshot
310     
311      ///This constructor immediately makes a snapshot of the graph.
312      ///\param _g The graph we make a snapshot of.
313      Snapshot(SmartGraph &_g) :g(&_g) {
314        node_num=g->nodes.size();
315        edge_num=g->edges.size();
316      }
317
318      ///Make a snapshot.
319
320      ///Make a snapshot of the graph.
321      ///
322      ///This function can be called more than once. In case of a repeated
323      ///call, the previous snapshot gets lost.
324      ///\param _g The graph we make the snapshot of.
325      void save(SmartGraph &_g)
326      {
327        g=&_g;
328        node_num=g->nodes.size();
329        edge_num=g->edges.size();
330      }
331
332      ///Undo the changes until a snapshot.
333     
334      ///Undo the changes until a snapshot created by save().
335      ///
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().
341     
342      void restore()
343      {
344        g->restoreSnapshot(*this);
345      }
346    };
347  };
348
349
350  /**************** Undirected List Graph ****************/
351
352  typedef UGraphExtender<UGraphBaseExtender<SmartGraphBase> >
353  ExtendedSmartUGraphBase;
354
355  /// \ingroup graphs
356  ///
357  /// \brief A smart undirected graph class.
358  ///
359  /// This is a simple and fast undirected graph implementation.
360  /// It is also quite memory efficient, but at the price
361  /// that <b> it does support only limited (only stack-like)
362  /// node and edge deletions</b>.
363  /// Except from this it conforms to
364  /// the \ref concept::UGraph "UGraph" concept.
365  /// \sa concept::UGraph.
366  ///
367  /// \todo Snapshot hasn't been implemented yet.
368  ///
369  class SmartUGraph : public ExtendedSmartUGraphBase {
370  };
371
372
373  class SmartBpUGraphBase {
374  public:
375
376    class NodeSetError : public LogicError {
377      virtual const char* exceptionName() const {
378        return "lemon::SmartBpUGraph::NodeSetError";
379      }
380    };
381
382  protected:
383
384    struct NodeT {
385      int first;
386      NodeT() {}
387      NodeT(int _first) : first(_first) {}
388    };
389
390    struct EdgeT {
391      int aNode, next_out;
392      int bNode, next_in;
393    };
394
395    std::vector<NodeT> aNodes;
396    std::vector<NodeT> bNodes;
397
398    std::vector<EdgeT> edges;
399
400  public:
401 
402    class Node {
403      friend class SmartBpUGraphBase;
404    protected:
405      int id;
406
407      Node(int _id) : id(_id) {}
408    public:
409      Node() {}
410      Node(Invalid) { id = -1; }
411      bool operator==(const Node i) const {return id==i.id;}
412      bool operator!=(const Node i) const {return id!=i.id;}
413      bool operator<(const Node i) const {return id<i.id;}
414    };
415
416    class Edge {
417      friend class SmartBpUGraphBase;
418    protected:
419      int id;
420
421      Edge(int _id) { id = _id;}
422    public:
423      Edge() {}
424      Edge (Invalid) { id = -1; }
425      bool operator==(const Edge i) const {return id==i.id;}
426      bool operator!=(const Edge i) const {return id!=i.id;}
427      bool operator<(const Edge i) const {return id<i.id;}
428    };
429
430    void firstANode(Node& node) const {
431      node.id = 2 * aNodes.size() - 2;
432      if (node.id < 0) node.id = -1;
433    }
434    void nextANode(Node& node) const {
435      node.id -= 2;
436      if (node.id < 0) node.id = -1;
437    }
438
439    void firstBNode(Node& node) const {
440      node.id = 2 * bNodes.size() - 1;
441    }
442    void nextBNode(Node& node) const {
443      node.id -= 2;
444    }
445
446    void first(Node& node) const {
447      if (aNodes.size() > 0) {
448        node.id = 2 * aNodes.size() - 2;
449      } else {
450        node.id = 2 * bNodes.size() - 1;
451      }
452    }
453    void next(Node& node) const {
454      node.id -= 2;
455      if (node.id == -2) {
456        node.id = 2 * bNodes.size() - 1;
457      }
458    }
459 
460    void first(Edge& edge) const {
461      edge.id = edges.size() - 1;
462    }
463    void next(Edge& edge) const {
464      --edge.id;
465    }
466
467    void firstOut(Edge& edge, const Node& node) const {
468      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
469      edge.id = aNodes[node.id >> 1].first;
470    }
471    void nextOut(Edge& edge) const {
472      edge.id = edges[edge.id].next_out;
473    }
474
475    void firstIn(Edge& edge, const Node& node) const {
476      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
477      edge.id = bNodes[node.id >> 1].first;
478    }
479    void nextIn(Edge& edge) const {
480      edge.id = edges[edge.id].next_in;
481    }
482
483    static int id(const Node& node) {
484      return node.id;
485    }
486    static Node nodeFromId(int id) {
487      return Node(id);
488    }
489    int maxNodeId() const {
490      return aNodes.size() > bNodes.size() ?
491        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
492    }
493 
494    static int id(const Edge& edge) {
495      return edge.id;
496    }
497    static Edge edgeFromId(int id) {
498      return Edge(id);
499    }
500    int maxEdgeId() const {
501      return edges.size();
502    }
503 
504    static int aNodeId(const Node& node) {
505      return node.id >> 1;
506    }
507    static Node fromANodeId(int id) {
508      return Node(id << 1);
509    }
510    int maxANodeId() const {
511      return aNodes.size();
512    }
513
514    static int bNodeId(const Node& node) {
515      return node.id >> 1;
516    }
517    static Node fromBNodeId(int id) {
518      return Node((id << 1) + 1);
519    }
520    int maxBNodeId() const {
521      return bNodes.size();
522    }
523
524    Node aNode(const Edge& edge) const {
525      return Node(edges[edge.id].aNode);
526    }
527    Node bNode(const Edge& edge) const {
528      return Node(edges[edge.id].bNode);
529    }
530
531    static bool aNode(const Node& node) {
532      return (node.id & 1) == 0;
533    }
534
535    static bool bNode(const Node& node) {
536      return (node.id & 1) == 1;
537    }
538
539    Node addANode() {
540      NodeT nodeT;
541      nodeT.first = -1;
542      aNodes.push_back(nodeT);
543      return Node(aNodes.size() * 2 - 2);
544    }
545
546    Node addBNode() {
547      NodeT nodeT;
548      nodeT.first = -1;
549      bNodes.push_back(nodeT);
550      return Node(bNodes.size() * 2 - 1);
551    }
552
553    Edge addEdge(const Node& source, const Node& target) {
554      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
555      EdgeT edgeT;
556      if ((source.id & 1) == 0) {
557        edgeT.aNode = source.id;
558        edgeT.bNode = target.id;
559      } else {
560        edgeT.aNode = target.id;
561        edgeT.bNode = source.id;
562      }
563      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
564      aNodes[edgeT.aNode >> 1].first = edges.size();
565      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
566      bNodes[edgeT.bNode >> 1].first = edges.size();
567      edges.push_back(edgeT);
568      return Edge(edges.size() - 1);
569    }
570
571    void clear() {
572      aNodes.clear();
573      bNodes.clear();
574      edges.clear();
575    }
576
577  };
578
579
580  typedef BpUGraphExtender< BpUGraphBaseExtender<
581    SmartBpUGraphBase> > ExtendedSmartBpUGraphBase;
582
583  /// \ingroup graphs
584  ///
585  /// \brief A smart bipartite undirected graph class.
586  ///
587  /// This is a simple and fast bipartite undirected graph implementation.
588  /// It is also quite memory efficient, but at the price
589  /// that <b> it does not support node and edge deletions</b>.
590  /// Except from this it conforms to
591  /// the \ref concept::BpUGraph "BpUGraph" concept.
592  /// \sa concept::BpUGraph.
593  ///
594  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
595
596 
597  /// @} 
598} //namespace lemon
599
600
601#endif //LEMON_SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.