COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/full_graph.h @ 1986:9b56cca61e2e

Last change on this file since 1986:9b56cca61e2e was 1986:9b56cca61e2e, checked in by Balazs Dezso, 14 years ago

An additional simplier interface for static size graphs.
Node operator()(int) for getting node by index
int index(Node node) for getting index by node

File size: 17.7 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_FULL_GRAPH_H
20#define LEMON_FULL_GRAPH_H
21
22#include <cmath>
23
24
25#include <lemon/bits/graph_extender.h>
26
27
28#include <lemon/invalid.h>
29#include <lemon/utility.h>
30
31
32///\ingroup graphs
33///\file
34///\brief FullGraph and FullUGraph classes.
35
36
37namespace lemon {
38
39  /// \brief Base of the FullGrpah.
40  ///
41  /// Base of the FullGrpah.
42  class FullGraphBase {
43    int _nodeNum;
44    int _edgeNum;
45  public:
46
47    typedef FullGraphBase Graph;
48
49    class Node;
50    class Edge;
51
52  public:
53
54    FullGraphBase() {}
55
56
57    ///Creates a full graph with \c n nodes.
58    void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
59   
60    typedef True NodeNumTag;
61    typedef True EdgeNumTag;
62
63    /// \brief Returns the node with the given index.
64    ///
65    /// Returns the node with the given index. Because it is a
66    /// static size graph the node's of the graph can be indiced
67    /// by the range from 0 to \e nodeNum()-1 and the index of
68    /// the node can accessed by the \e index() member.
69    Node operator()(int index) const { return Node(index); }
70
71    /// \brief Returns the index of the node.
72    ///
73    /// Returns the index of the node. Because it is a
74    /// static size graph the node's of the graph can be indiced
75    /// by the range from 0 to \e nodeNum()-1 and the index of
76    /// the node can accessed by the \e index() member.
77    int index(const Node& node) const { return node.id; }
78
79    ///Number of nodes.
80    int nodeNum() const { return _nodeNum; }
81    ///Number of edges.
82    int edgeNum() const { return _edgeNum; }
83
84    /// Maximum node ID.
85   
86    /// Maximum node ID.
87    ///\sa id(Node)
88    int maxNodeId() const { return _nodeNum-1; }
89    /// Maximum edge ID.
90   
91    /// Maximum edge ID.
92    ///\sa id(Edge)
93    int maxEdgeId() const { return _edgeNum-1; }
94
95    Node source(Edge e) const { return e.id % _nodeNum; }
96    Node target(Edge e) const { return e.id / _nodeNum; }
97
98
99    /// Node ID.
100   
101    /// The ID of a valid Node is a nonnegative integer not greater than
102    /// \ref maxNodeId(). The range of the ID's is not surely continuous
103    /// and the greatest node ID can be actually less then \ref maxNodeId().
104    ///
105    /// The ID of the \ref INVALID node is -1.
106    ///\return The ID of the node \c v.
107
108    static int id(Node v) { return v.id; }
109    /// Edge ID.
110   
111    /// The ID of a valid Edge is a nonnegative integer not greater than
112    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
113    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
114    ///
115    /// The ID of the \ref INVALID edge is -1.
116    ///\return The ID of the edge \c e.
117    static int id(Edge e) { return e.id; }
118
119    static Node nodeFromId(int id) { return Node(id);}
120   
121    static Edge edgeFromId(int id) { return Edge(id);}
122
123    typedef True FindEdgeTag;
124
125    /// Finds an edge between two nodes.
126   
127    /// Finds an edge from node \c u to node \c v.
128    ///
129    /// If \c prev is \ref INVALID (this is the default value), then
130    /// It finds the first edge from \c u to \c v. Otherwise it looks for
131    /// the next edge from \c u to \c v after \c prev.
132    /// \return The found edge or INVALID if there is no such an edge.
133    Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
134      return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
135    }
136   
137     
138    class Node {
139      friend class FullGraphBase;
140
141    protected:
142      int id;
143      Node(int _id) : id(_id) {}
144    public:
145      Node() {}
146      Node (Invalid) : id(-1) {}
147      bool operator==(const Node node) const {return id == node.id;}
148      bool operator!=(const Node node) const {return id != node.id;}
149      bool operator<(const Node node) const {return id < node.id;}
150    };
151   
152
153
154    class Edge {
155      friend class FullGraphBase;
156     
157    protected:
158      int id;  // _nodeNum * target + source;
159
160      Edge(int _id) : id(_id) {}
161
162      Edge(const FullGraphBase& _graph, int source, int target)
163        : id(_graph._nodeNum * target+source) {}
164    public:
165      Edge() { }
166      Edge (Invalid) { id = -1; }
167      bool operator==(const Edge edge) const {return id == edge.id;}
168      bool operator!=(const Edge edge) const {return id != edge.id;}
169      bool operator<(const Edge edge) const {return id < edge.id;}
170    };
171
172    void first(Node& node) const {
173      node.id = _nodeNum-1;
174    }
175
176    static void next(Node& node) {
177      --node.id;
178    }
179
180    void first(Edge& edge) const {
181      edge.id = _edgeNum-1;
182    }
183
184    static void next(Edge& edge) {
185      --edge.id;
186    }
187
188    void firstOut(Edge& edge, const Node& node) const {
189      edge.id = _edgeNum + node.id - _nodeNum;
190    }
191
192    void nextOut(Edge& edge) const {
193      edge.id -= _nodeNum;
194      if (edge.id < 0) edge.id = -1;
195    }
196
197    void firstIn(Edge& edge, const Node& node) const {
198      edge.id = node.id * _nodeNum;
199    }
200   
201    void nextIn(Edge& edge) const {
202      ++edge.id;
203      if (edge.id % _nodeNum == 0) edge.id = -1;
204    }
205
206  };
207
208  typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
209
210  /// \ingroup graphs
211  ///
212  /// \brief A full graph class.
213  ///
214  /// This is a simple and fast directed full graph implementation.
215  /// It is completely static, so you can neither add nor delete either
216  /// edges or nodes.
217  /// Thus it conforms to
218  /// the \ref concept::StaticGraph "StaticGraph" concept
219  /// \sa concept::StaticGraph.
220  ///
221  /// \sa FullGraphBase
222  /// \sa FullUGraph
223  ///
224  /// \author Alpar Juttner
225  class FullGraph : public ExtendedFullGraphBase {
226  public:
227
228    typedef ExtendedFullGraphBase Parent;
229
230    /// \brief Constructor
231    ///
232    FullGraph(int n) { construct(n); }
233
234    /// \brief Resize the graph
235    ///
236    /// Resize the graph. The function will fully destroy and build the graph.
237    /// This cause that the maps of the graph will reallocated
238    /// automatically and the previous values will be lost.
239    void resize(int n) {
240      Parent::getNotifier(Edge()).clear();
241      Parent::getNotifier(Node()).clear();
242      construct(n);
243      Parent::getNotifier(Node()).build();
244      Parent::getNotifier(Edge()).build();
245    }
246  };
247
248
249  /// \brief Base of the FullUGrpah.
250  ///
251  /// Base of the FullUGrpah.
252  class FullUGraphBase {
253    int _nodeNum;
254    int _edgeNum;
255  public:
256
257    typedef FullUGraphBase Graph;
258
259    class Node;
260    class Edge;
261
262  public:
263
264    FullUGraphBase() {}
265
266
267    ///Creates a full graph with \c n nodes.
268    void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
269
270    /// \brief Returns the node with the given index.
271    ///
272    /// Returns the node with the given index. Because it is a
273    /// static size graph the node's of the graph can be indiced
274    /// by the range from 0 to \e nodeNum()-1 and the index of
275    /// the node can accessed by the \e index() member.
276    Node operator()(int index) const { return Node(index); }
277
278    /// \brief Returns the index of the node.
279    ///
280    /// Returns the index of the node. Because it is a
281    /// static size graph the node's of the graph can be indiced
282    /// by the range from 0 to \e nodeNum()-1 and the index of
283    /// the node can accessed by the \e index() member.
284    int index(const Node& node) const { return node.id; }
285
286    typedef True NodeNumTag;
287    typedef True EdgeNumTag;
288
289    ///Number of nodes.
290    int nodeNum() const { return _nodeNum; }
291    ///Number of edges.
292    int edgeNum() const { return _edgeNum; }
293
294    /// Maximum node ID.
295   
296    /// Maximum node ID.
297    ///\sa id(Node)
298    int maxNodeId() const { return _nodeNum-1; }
299    /// Maximum edge ID.
300   
301    /// Maximum edge ID.
302    ///\sa id(Edge)
303    int maxEdgeId() const { return _edgeNum-1; }
304
305    Node source(Edge e) const {
306      /// \todo we may do it faster
307      return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
308    }
309
310    Node target(Edge e) const {
311      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
312      return Node(e.id - (source) * (source - 1) / 2);
313    }
314
315
316    /// \brief Node ID.
317    ///
318    /// The ID of a valid Node is a nonnegative integer not greater than
319    /// \ref maxNodeId(). The range of the ID's is not surely continuous
320    /// and the greatest node ID can be actually less then \ref maxNodeId().
321    ///
322    /// The ID of the \ref INVALID node is -1.
323    /// \return The ID of the node \c v.
324
325    static int id(Node v) { return v.id; }
326
327    /// \brief Edge ID.
328    ///
329    /// The ID of a valid Edge is a nonnegative integer not greater than
330    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
331    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
332    ///
333    /// The ID of the \ref INVALID edge is -1.
334    ///\return The ID of the edge \c e.
335    static int id(Edge e) { return e.id; }
336
337    /// \brief Finds an edge between two nodes.
338    ///
339    /// Finds an edge from node \c u to node \c v.
340    ///
341    /// If \c prev is \ref INVALID (this is the default value), then
342    /// It finds the first edge from \c u to \c v. Otherwise it looks for
343    /// the next edge from \c u to \c v after \c prev.
344    /// \return The found edge or INVALID if there is no such an edge.
345    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
346      if (prev.id != -1 || u.id <= v.id) return Edge(-1);
347      return Edge(u.id * (u.id - 1) / 2 + v.id);
348    }
349
350    typedef True FindEdgeTag;
351   
352     
353    class Node {
354      friend class FullUGraphBase;
355
356    protected:
357      int id;
358      Node(int _id) { id = _id;}
359    public:
360      Node() {}
361      Node (Invalid) { id = -1; }
362      bool operator==(const Node node) const {return id == node.id;}
363      bool operator!=(const Node node) const {return id != node.id;}
364      bool operator<(const Node node) const {return id < node.id;}
365    };
366   
367
368
369    class Edge {
370      friend class FullUGraphBase;
371     
372    protected:
373      int id;  // _nodeNum * target + source;
374
375      Edge(int _id) : id(_id) {}
376
377    public:
378      Edge() { }
379      Edge (Invalid) { id = -1; }
380      bool operator==(const Edge edge) const {return id == edge.id;}
381      bool operator!=(const Edge edge) const {return id != edge.id;}
382      bool operator<(const Edge edge) const {return id < edge.id;}
383    };
384
385    void first(Node& node) const {
386      node.id = _nodeNum - 1;
387    }
388
389    static void next(Node& node) {
390      --node.id;
391    }
392
393    void first(Edge& edge) const {
394      edge.id = _edgeNum - 1;
395    }
396
397    static void next(Edge& edge) {
398      --edge.id;
399    }
400
401    void firstOut(Edge& edge, const Node& node) const {     
402      int src = node.id;
403      int trg = 0;
404      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
405    }
406
407    /// \todo with specialized iterators we can make faster iterating
408    void nextOut(Edge& edge) const {
409      int src = source(edge).id;
410      int trg = target(edge).id;
411      ++trg;
412      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
413    }
414
415    void firstIn(Edge& edge, const Node& node) const {
416      int src = node.id + 1;
417      int trg = node.id;
418      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
419    }
420   
421    void nextIn(Edge& edge) const {
422      int src = source(edge).id;
423      int trg = target(edge).id;
424      ++src;
425      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
426    }
427
428  };
429
430  typedef UGraphExtender<UGraphBaseExtender<FullUGraphBase> >
431  ExtendedFullUGraphBase;
432
433  /// \ingroup graphs
434  ///
435  /// \brief An undirected full graph class.
436  ///
437  /// This is a simple and fast undirected full graph implementation.
438  /// It is completely static, so you can neither add nor delete either
439  /// edges or nodes.
440  ///
441  /// The main difference beetween the \e FullGraph and \e FullUGraph class
442  /// is that this class conforms to the undirected graph concept and
443  /// it does not contain the loop edges.
444  ///
445  /// \sa FullUGraphBase
446  /// \sa FullGraph
447  ///
448  /// \author Balazs Dezso
449  class FullUGraph : public ExtendedFullUGraphBase {
450  public:
451
452    typedef ExtendedFullUGraphBase Parent;
453
454    /// \brief Constructor
455    FullUGraph(int n) { construct(n); }
456
457    /// \brief Resize the graph
458    ///
459    /// Resize the graph. The function will fully destroy and build the graph.
460    /// This cause that the maps of the graph will reallocated
461    /// automatically and the previous values will be lost.
462    void resize(int n) {
463      Parent::getNotifier(Edge()).clear();
464      Parent::getNotifier(UEdge()).clear();
465      Parent::getNotifier(Node()).clear();
466      construct(n);
467      Parent::getNotifier(Node()).build();
468      Parent::getNotifier(UEdge()).build();
469      Parent::getNotifier(Edge()).build();
470    }
471  };
472
473
474  class FullBpUGraphBase {
475  protected:
476
477    int _aNodeNum;
478    int _bNodeNum;
479
480    int _edgeNum;
481
482  public:
483
484    class NodeSetError : public LogicError {
485      virtual const char* exceptionName() const {
486        return "lemon::FullBpUGraph::NodeSetError";
487      }
488    };
489 
490    class Node {
491      friend class FullBpUGraphBase;
492    protected:
493      int id;
494
495      Node(int _id) : id(_id) {}
496    public:
497      Node() {}
498      Node(Invalid) { id = -1; }
499      bool operator==(const Node i) const {return id==i.id;}
500      bool operator!=(const Node i) const {return id!=i.id;}
501      bool operator<(const Node i) const {return id<i.id;}
502    };
503
504    class Edge {
505      friend class FullBpUGraphBase;
506    protected:
507      int id;
508
509      Edge(int _id) { id = _id;}
510    public:
511      Edge() {}
512      Edge (Invalid) { id = -1; }
513      bool operator==(const Edge i) const {return id==i.id;}
514      bool operator!=(const Edge i) const {return id!=i.id;}
515      bool operator<(const Edge i) const {return id<i.id;}
516    };
517
518    void construct(int aNodeNum, int bNodeNum) {
519      _aNodeNum = aNodeNum;
520      _bNodeNum = bNodeNum;
521      _edgeNum = aNodeNum * bNodeNum;
522    }
523
524    void firstANode(Node& node) const {
525      node.id = 2 * _aNodeNum - 2;
526      if (node.id < 0) node.id = -1;
527    }
528    void nextANode(Node& node) const {
529      node.id -= 2;
530      if (node.id < 0) node.id = -1;
531    }
532
533    void firstBNode(Node& node) const {
534      node.id = 2 * _bNodeNum - 1;
535    }
536    void nextBNode(Node& node) const {
537      node.id -= 2;
538    }
539
540    void first(Node& node) const {
541      if (_aNodeNum > 0) {
542        node.id = 2 * _aNodeNum - 2;
543      } else {
544        node.id = 2 * _bNodeNum - 1;
545      }
546    }
547    void next(Node& node) const {
548      node.id -= 2;
549      if (node.id == -2) {
550        node.id = 2 * _bNodeNum - 1;
551      }
552    }
553 
554    void first(Edge& edge) const {
555      edge.id = _edgeNum - 1;
556    }
557    void next(Edge& edge) const {
558      --edge.id;
559    }
560
561    void firstOut(Edge& edge, const Node& node) const {
562      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
563      edge.id = (node.id >> 1) * _bNodeNum;
564    }
565    void nextOut(Edge& edge) const {
566      ++(edge.id);
567      if (edge.id % _bNodeNum == 0) edge.id = -1;
568    }
569
570    void firstIn(Edge& edge, const Node& node) const {
571      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
572      edge.id = (node.id >> 1);
573    }
574    void nextIn(Edge& edge) const {
575      edge.id += _bNodeNum;
576      if (edge.id >= _edgeNum) edge.id = -1;
577    }
578
579    static int id(const Node& node) {
580      return node.id;
581    }
582    static Node nodeFromId(int id) {
583      return Node(id);
584    }
585    int maxNodeId() const {
586      return _aNodeNum > _bNodeNum ?
587        _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
588    }
589 
590    static int id(const Edge& edge) {
591      return edge.id;
592    }
593    static Edge edgeFromId(int id) {
594      return Edge(id);
595    }
596    int maxEdgeId() const {
597      return _edgeNum - 1;
598    }
599 
600    static int aNodeId(const Node& node) {
601      return node.id >> 1;
602    }
603    static Node fromANodeId(int id, Node) {
604      return Node(id << 1);
605    }
606    int maxANodeId() const {
607      return _aNodeNum;
608    }
609
610    static int bNodeId(const Node& node) {
611      return node.id >> 1;
612    }
613    static Node fromBNodeId(int id) {
614      return Node((id << 1) + 1);
615    }
616    int maxBNodeId() const {
617      return _bNodeNum;
618    }
619
620    Node aNode(const Edge& edge) const {
621      return Node((edge.id / _bNodeNum) << 1);
622    }
623    Node bNode(const Edge& edge) const {
624      return Node(((edge.id % _bNodeNum) << 1) + 1);
625    }
626
627    static bool aNode(const Node& node) {
628      return (node.id & 1) == 0;
629    }
630
631    static bool bNode(const Node& node) {
632      return (node.id & 1) == 1;
633    }
634
635    static Node aNode(int index) {
636      return Node(index << 1);
637    }
638
639    static Node bNode(int index) {
640      return Node((index << 1) + 1);
641    }
642
643  };
644
645
646  typedef BpUGraphExtender< BpUGraphBaseExtender<
647    FullBpUGraphBase> > ExtendedFullBpUGraphBase;
648
649
650  /// \ingroup graphs
651  ///
652  /// \brief An undirected full bipartite graph class.
653  ///
654  /// This is a simple and fast bipartite undirected full graph implementation.
655  /// It is completely static, so you can neither add nor delete either
656  /// edges or nodes.
657  ///
658  /// \sa FullUGraphBase
659  /// \sa FullGraph
660  ///
661  /// \author Balazs Dezso
662  class FullBpUGraph :
663    public ExtendedFullBpUGraphBase {
664  public:
665
666    typedef ExtendedFullBpUGraphBase Parent;
667
668    FullBpUGraph(int aNodeNum, int bNodeNum) {
669      Parent::construct(aNodeNum, bNodeNum);
670    }
671    /// \brief Resize the graph
672    ///
673    void resize(int n, int m) {
674      Parent::getNotifier(Edge()).clear();
675      Parent::getNotifier(UEdge()).clear();
676      Parent::getNotifier(Node()).clear();
677      construct(n, m);
678      Parent::getNotifier(Node()).build();
679      Parent::getNotifier(UEdge()).build();
680      Parent::getNotifier(Edge()).build();
681    }
682  };
683
684} //namespace lemon
685
686
687#endif //LEMON_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.