COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/full_graph.h @ 2111:ea1fa1bc3f6d

Last change on this file since 2111:ea1fa1bc3f6d was 2111:ea1fa1bc3f6d, checked in by Balazs Dezso, 13 years ago

Removing concepts for extendable and erasable graphs
Renaming StaticGraph? to Graph

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