COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 1978:ef2d00e46897

Last change on this file since 1978:ef2d00e46897 was 1956:a055123339d5, checked in by Alpar Juttner, 18 years ago

Unified copyright notices

File size: 15.4 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/invalid.h>
29
30#include <lemon/bits/clearable_graph_extender.h>
31#include <lemon/bits/extendable_graph_extender.h>
32#include <lemon/bits/iterable_graph_extender.h>
33#include <lemon/bits/alteration_notifier.h>
34#include <lemon/bits/default_map.h>
35#include <lemon/bits/graph_extender.h>
36
37#include <lemon/utility.h>
38#include <lemon/error.h>
39
40namespace lemon {
41
42  class SmartGraph;
43  ///Base of SmartGraph
44
45  ///Base of SmartGraph
46  ///
47  class SmartGraphBase {
48
49    friend class SmatGraph;
50
51  protected:
52    struct NodeT
53    {
54      int first_in,first_out;     
55      NodeT() : first_in(-1), first_out(-1) {}
56    };
57    struct EdgeT
58    {
59      int target, source, next_in, next_out;     
60      //FIXME: is this necessary?
61      EdgeT() : next_in(-1), next_out(-1) {} 
62    };
63
64    std::vector<NodeT> nodes;
65
66    std::vector<EdgeT> edges;
67   
68   
69  public:
70
71    typedef SmartGraphBase Graph;
72
73    class Node;
74    class Edge;
75
76   
77  public:
78
79    SmartGraphBase() : nodes(), edges() { }
80    SmartGraphBase(const SmartGraphBase &_g)
81      : nodes(_g.nodes), edges(_g.edges) { }
82   
83    typedef True NodeNumTag;
84    typedef True EdgeNumTag;
85
86    ///Number of nodes.
87    int nodeNum() const { return nodes.size(); }
88    ///Number of edges.
89    int edgeNum() const { return edges.size(); }
90
91    /// Maximum node ID.
92   
93    /// Maximum node ID.
94    ///\sa id(Node)
95    int maxNodeId() const { return nodes.size()-1; }
96    /// Maximum edge ID.
97   
98    /// Maximum edge ID.
99    ///\sa id(Edge)
100    int maxEdgeId() const { return edges.size()-1; }
101
102    Node source(Edge e) const { return edges[e.n].source; }
103    Node target(Edge e) const { return edges[e.n].target; }
104
105    /// Node ID.
106   
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.
115   
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; }
123
124    static Node nodeFromId(int id) { return Node(id);}
125
126    static Edge edgeFromId(int id) { return Edge(id);}
127
128    Node addNode() {
129      Node n; n.n=nodes.size();
130      nodes.push_back(NodeT()); //FIXME: Hmmm...
131      return n;
132    }
133   
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;
140
141      return e;
142    }
143
144    void clear() {
145      edges.clear();
146      nodes.clear();
147    }
148
149
150    class Node {
151      friend class SmartGraphBase;
152      friend class SmartGraph;
153
154    protected:
155      int n;
156      Node(int nn) {n=nn;}
157    public:
158      Node() {}
159      Node (Invalid) { n=-1; }
160      bool operator==(const Node i) const {return n==i.n;}
161      bool operator!=(const Node i) const {return n!=i.n;}
162      bool operator<(const Node i) const {return n<i.n;}
163    };
164   
165
166    class Edge {
167      friend class SmartGraphBase;
168      friend class SmartGraph;
169
170    protected:
171      int n;
172      Edge(int nn) {n=nn;}
173    public:
174      Edge() { }
175      Edge (Invalid) { n=-1; }
176      bool operator==(const Edge i) const {return n==i.n;}
177      bool operator!=(const Edge i) const {return n!=i.n;}
178      bool operator<(const Edge i) const {return n<i.n;}
179    };
180
181    void first(Node& node) const {
182      node.n = nodes.size() - 1;
183    }
184
185    static void next(Node& node) {
186      --node.n;
187    }
188
189    void first(Edge& edge) const {
190      edge.n = edges.size() - 1;
191    }
192
193    static void next(Edge& edge) {
194      --edge.n;
195    }
196
197    void firstOut(Edge& edge, const Node& node) const {
198      edge.n = nodes[node.n].first_out;
199    }
200
201    void nextOut(Edge& edge) const {
202      edge.n = edges[edge.n].next_out;
203    }
204
205    void firstIn(Edge& edge, const Node& node) const {
206      edge.n = nodes[node.n].first_in;
207    }
208   
209    void nextIn(Edge& edge) const {
210      edge.n = edges[edge.n].next_in;
211    }
212
213    Node _split(Node n, bool connect = true)
214    {
215      Node b = addNode();
216      nodes[b.n].first_out=nodes[n.n].first_out;
217      nodes[n.n].first_out=-1;
218      for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
219      if(connect) addEdge(n,b);
220      return b;
221    }
222
223  };
224
225  typedef ClearableGraphExtender<
226    ExtendableGraphExtender<
227    MappableGraphExtender<
228    IterableGraphExtender<
229    AlterableGraphExtender<
230    GraphExtender<SmartGraphBase> > > > > > ExtendedSmartGraphBase;
231
232  /// \ingroup graphs
233
234  ///A smart graph class.
235
236  ///This is a simple and fast graph implementation.
237  ///It is also quite memory efficient, but at the price
238  ///that <b> it does support only limited (only stack-like)
239  ///node and edge deletions</b>.
240  ///It conforms to
241  ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
242  ///\sa concept::ExtendableGraph.
243  ///
244  ///\author Alpar Juttner
245  class SmartGraph : public ExtendedSmartGraphBase {
246  public:
247   
248    class Snapshot;
249    friend class Snapshot;
250
251  protected:
252    void restoreSnapshot(const Snapshot &s)
253    {
254      while(s.edge_num<edges.size()) {
255        Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
256        nodes[edges.back().target].first_in=edges.back().next_in;
257        nodes[edges.back().source].first_out=edges.back().next_out;
258        edges.pop_back();
259      }
260      //nodes.resize(s.nodes_num);
261      while(s.node_num<nodes.size()) {
262        Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
263        nodes.pop_back();
264      }
265    }   
266
267  public:
268
269    ///Split a node.
270   
271    ///This function splits a node. First a new node is added to the graph,
272    ///then the source of each outgoing edge of \c n is moved to this new node.
273    ///If \c connect is \c true (this is the default value), then a new edge
274    ///from \c n to the newly created node is also added.
275    ///\return The newly created node.
276    ///
277    ///\note The <tt>Edge</tt>s
278    ///referencing a moved edge remain
279    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
280    ///may be invalidated.
281    ///\warning This functionality cannot be used together with the Snapshot
282    ///feature.
283    ///\todo It could be implemented in a bit faster way.
284    Node split(Node n, bool connect = true)
285    {
286      Node b = _split(n,connect);
287      return b;
288    }
289 
290
291    ///Class to make a snapshot of the graph and to restrore to it later.
292
293    ///Class to make a snapshot of the graph and to restrore to it later.
294    ///
295    ///The newly added nodes and edges can be removed using the
296    ///restore() function.
297    ///\note After you restore a state, you cannot restore
298    ///a later state, in other word you cannot add again the edges deleted
299    ///by restore() using another Snapshot instance.
300    ///
301    class Snapshot
302    {
303      SmartGraph *g;
304    protected:
305      friend class SmartGraph;
306      unsigned int node_num;
307      unsigned int edge_num;
308    public:
309      ///Default constructor.
310     
311      ///Default constructor.
312      ///To actually make a snapshot you must call save().
313      ///
314      Snapshot() : g(0) {}
315      ///Constructor that immediately makes a snapshot
316     
317      ///This constructor immediately makes a snapshot of the graph.
318      ///\param _g The graph we make a snapshot of.
319      Snapshot(SmartGraph &_g) :g(&_g) {
320        node_num=g->nodes.size();
321        edge_num=g->edges.size();
322      }
323
324      ///Make a snapshot.
325
326      ///Make a snapshot of the graph.
327      ///
328      ///This function can be called more than once. In case of a repeated
329      ///call, the previous snapshot gets lost.
330      ///\param _g The graph we make the snapshot of.
331      void save(SmartGraph &_g)
332      {
333        g=&_g;
334        node_num=g->nodes.size();
335        edge_num=g->edges.size();
336      }
337
338      ///Undo the changes until a snapshot.
339     
340      ///Undo the changes until a snapshot created by save().
341      ///
342      ///\note After you restored a state, you cannot restore
343      ///a later state, in other word you cannot add again the edges deleted
344      ///by restore().
345      ///
346      ///\todo This function might be called undo().
347     
348      void restore()
349      {
350        g->restoreSnapshot(*this);
351      }
352    };
353  };
354
355
356  /**************** Undirected List Graph ****************/
357
358  typedef ClearableUGraphExtender<
359    ExtendableUGraphExtender<
360    MappableUGraphExtender<
361    IterableUGraphExtender<
362    AlterableUGraphExtender<
363    UGraphExtender<SmartGraphBase> > > > > > ExtendedSmartUGraphBase;
364
365  /// \ingroup graphs
366  ///
367  /// \brief A smart undirected graph class.
368  ///
369  /// This is a simple and fast undirected graph implementation.
370  /// It is also quite memory efficient, but at the price
371  /// that <b> it does support only limited (only stack-like)
372  /// node and edge deletions</b>.
373  /// Except from this it conforms to
374  /// the \ref concept::UGraph "UGraph" concept.
375  /// \sa concept::UGraph.
376  ///
377  /// \todo Snapshot hasn't been implemented yet.
378  ///
379  class SmartUGraph : public ExtendedSmartUGraphBase {
380  };
381
382
383  class SmartBpUGraphBase {
384  public:
385
386    class NodeSetError : public LogicError {
387      virtual const char* exceptionName() const {
388        return "lemon::SmartBpUGraph::NodeSetError";
389      }
390    };
391
392  protected:
393
394    struct NodeT {
395      int first;
396      NodeT() {}
397      NodeT(int _first) : first(_first) {}
398    };
399
400    struct EdgeT {
401      int aNode, next_out;
402      int bNode, next_in;
403    };
404
405    std::vector<NodeT> aNodes;
406    std::vector<NodeT> bNodes;
407
408    std::vector<EdgeT> edges;
409
410  public:
411 
412    class Node {
413      friend class SmartBpUGraphBase;
414    protected:
415      int id;
416
417      Node(int _id) : id(_id) {}
418    public:
419      Node() {}
420      Node(Invalid) { id = -1; }
421      bool operator==(const Node i) const {return id==i.id;}
422      bool operator!=(const Node i) const {return id!=i.id;}
423      bool operator<(const Node i) const {return id<i.id;}
424    };
425
426    class Edge {
427      friend class SmartBpUGraphBase;
428    protected:
429      int id;
430
431      Edge(int _id) { id = _id;}
432    public:
433      Edge() {}
434      Edge (Invalid) { id = -1; }
435      bool operator==(const Edge i) const {return id==i.id;}
436      bool operator!=(const Edge i) const {return id!=i.id;}
437      bool operator<(const Edge i) const {return id<i.id;}
438    };
439
440    void firstANode(Node& node) const {
441      node.id = 2 * aNodes.size() - 2;
442      if (node.id < 0) node.id = -1;
443    }
444    void nextANode(Node& node) const {
445      node.id -= 2;
446      if (node.id < 0) node.id = -1;
447    }
448
449    void firstBNode(Node& node) const {
450      node.id = 2 * bNodes.size() - 1;
451    }
452    void nextBNode(Node& node) const {
453      node.id -= 2;
454    }
455
456    void first(Node& node) const {
457      if (aNodes.size() > 0) {
458        node.id = 2 * aNodes.size() - 2;
459      } else {
460        node.id = 2 * bNodes.size() - 1;
461      }
462    }
463    void next(Node& node) const {
464      node.id -= 2;
465      if (node.id == -2) {
466        node.id = 2 * bNodes.size() - 1;
467      }
468    }
469 
470    void first(Edge& edge) const {
471      edge.id = edges.size() - 1;
472    }
473    void next(Edge& edge) const {
474      --edge.id;
475    }
476
477    void firstOut(Edge& edge, const Node& node) const {
478      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
479      edge.id = aNodes[node.id >> 1].first;
480    }
481    void nextOut(Edge& edge) const {
482      edge.id = edges[edge.id].next_out;
483    }
484
485    void firstIn(Edge& edge, const Node& node) const {
486      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
487      edge.id = bNodes[node.id >> 1].first;
488    }
489    void nextIn(Edge& edge) const {
490      edge.id = edges[edge.id].next_in;
491    }
492
493    static int id(const Node& node) {
494      return node.id;
495    }
496    static Node nodeFromId(int id) {
497      return Node(id);
498    }
499    int maxNodeId() const {
500      return aNodes.size() > bNodes.size() ?
501        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
502    }
503 
504    static int id(const Edge& edge) {
505      return edge.id;
506    }
507    static Edge edgeFromId(int id) {
508      return Edge(id);
509    }
510    int maxEdgeId() const {
511      return edges.size();
512    }
513 
514    static int aNodeId(const Node& node) {
515      return node.id >> 1;
516    }
517    static Node fromANodeId(int id, Node) {
518      return Node(id << 1);
519    }
520    int maxANodeId() const {
521      return aNodes.size();
522    }
523
524    static int bNodeId(const Node& node) {
525      return node.id >> 1;
526    }
527    static Node fromBNodeId(int id) {
528      return Node((id << 1) + 1);
529    }
530    int maxBNodeId() const {
531      return bNodes.size();
532    }
533
534    Node aNode(const Edge& edge) const {
535      return Node(edges[edge.id].aNode);
536    }
537    Node bNode(const Edge& edge) const {
538      return Node(edges[edge.id].bNode);
539    }
540
541    static bool aNode(const Node& node) {
542      return (node.id & 1) == 0;
543    }
544
545    static bool bNode(const Node& node) {
546      return (node.id & 1) == 1;
547    }
548
549    Node addANode() {
550      NodeT nodeT;
551      nodeT.first = -1;
552      aNodes.push_back(nodeT);
553      return Node(aNodes.size() * 2 - 2);
554    }
555
556    Node addBNode() {
557      NodeT nodeT;
558      nodeT.first = -1;
559      bNodes.push_back(nodeT);
560      return Node(bNodes.size() * 2 - 1);
561    }
562
563    Edge addEdge(const Node& source, const Node& target) {
564      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
565      EdgeT edgeT;
566      if ((source.id & 1) == 0) {
567        edgeT.aNode = source.id;
568        edgeT.bNode = target.id;
569      } else {
570        edgeT.aNode = target.id;
571        edgeT.bNode = source.id;
572      }
573      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
574      aNodes[edgeT.aNode >> 1].first = edges.size();
575      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
576      bNodes[edgeT.bNode >> 1].first = edges.size();
577      edges.push_back(edgeT);
578      return Edge(edges.size() - 1);
579    }
580
581    void clear() {
582      aNodes.clear();
583      bNodes.clear();
584      edges.clear();
585    }
586
587  };
588
589
590  typedef ClearableBpUGraphExtender<
591    ExtendableBpUGraphExtender<
592    MappableBpUGraphExtender<
593    IterableBpUGraphExtender<
594    AlterableBpUGraphExtender<
595    BpUGraphExtender <
596    SmartBpUGraphBase> > > > > >
597  ExtendedSmartBpUGraphBase;
598
599  /// \ingroup graphs
600  ///
601  /// \brief A smart bipartite undirected graph class.
602  ///
603  /// This is a simple and fast bipartite undirected graph implementation.
604  /// It is also quite memory efficient, but at the price
605  /// that <b> it does not support node and edge deletions</b>.
606  /// Except from this it conforms to
607  /// the \ref concept::BpUGraph "BpUGraph" concept.
608  /// \sa concept::BpUGraph.
609  ///
610  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
611
612 
613  /// @} 
614} //namespace lemon
615
616
617#endif //LEMON_SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.