COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 2059:ebf3b2962554

Last change on this file since 2059:ebf3b2962554 was 2031:080d51024ac5, checked in by Balazs Dezso, 18 years ago

Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.

Some bugfix in the adaptors

New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.

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