COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/full_graph.h @ 1956:a055123339d5

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

Unified copyright notices

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