COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/full_graph.h @ 822:88226d9fe821

Last change on this file since 822:88226d9fe821 was 822:88226d9fe821, checked in by Balazs Dezso, 16 years ago

The MapFactories? have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

Some macros and comments has been changed.

File size: 6.5 KB
Line 
1// -*- c++ -*-
2
3#ifndef HUGO_FULL_GRAPH_H
4#define HUGO_FULL_GRAPH_H
5
6///\ingroup graphs
7///\file
8///\brief FullGraph and SymFullGraph classes.
9
10#include <vector>
11#include <climits>
12
13#include <hugo/invalid.h>
14
15#include <hugo/map_registry.h>
16#include <hugo/default_map.h>
17
18#include <hugo/map_defines.h>
19
20namespace hugo {
21
22/// \addtogroup graphs
23/// @{
24
25  ///A full graph class.
26
27  ///This is a simple and fast directed full graph implementation.
28  ///It is completely static, so you can neither add nor delete either
29  ///edges or nodes.
30  ///Otherwise it conforms to the graph interface documented under
31  ///the description of \ref GraphSkeleton.
32  ///\sa \ref GraphSkeleton.
33  ///\todo What about loops?
34  ///\todo Don't we need SymEdgeMap?
35  ///
36  ///\author Alpar Juttner
37  class FullGraph {
38    int NodeNum;
39    int EdgeNum;
40  public:
41
42    typedef FullGraph Graph;
43
44    class Node;
45    class Edge;
46
47    class NodeIt;
48    class EdgeIt;
49    class OutEdgeIt;
50    class InEdgeIt;
51   
52
53    /// Creating map registries.
54    CREATE_MAP_REGISTRIES;
55    /// Creating node and edge maps.
56    CREATE_MAPS(DefaultMap);
57   
58  public:
59
60    ///Creates a full graph with \c n nodes.
61    FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
62    ///
63    FullGraph(const FullGraph &_g)
64      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
65   
66    ///Number of nodes.
67    int nodeNum() const { return NodeNum; }
68    ///Number of edges.
69    int edgeNum() const { return EdgeNum; }
70
71    /// Maximum node ID.
72   
73    /// Maximum node ID.
74    ///\sa id(Node)
75    int maxNodeId() const { return NodeNum-1; }
76    /// Maximum edge ID.
77   
78    /// Maximum edge ID.
79    ///\sa id(Edge)
80    int maxEdgeId() const { return EdgeNum-1; }
81
82    Node tail(Edge e) const { return e.n%NodeNum; }
83    Node head(Edge e) const { return e.n/NodeNum; }
84
85    NodeIt& first(NodeIt& v) const {
86      v=NodeIt(*this); return v; }
87    EdgeIt& first(EdgeIt& e) const {
88      e=EdgeIt(*this); return e; }
89    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
90      e=OutEdgeIt(*this,v); return e; }
91    InEdgeIt& first(InEdgeIt& e, const Node v) const {
92      e=InEdgeIt(*this,v); return e; }
93
94    /// Node ID.
95   
96    /// The ID of a valid Node is a nonnegative integer not greater than
97    /// \ref maxNodeId(). The range of the ID's is not surely continuous
98    /// and the greatest node ID can be actually less then \ref maxNodeId().
99    ///
100    /// The ID of the \ref INVALID node is -1.
101    ///\return The ID of the node \c v.
102    static int id(Node v) { return v.n; }
103    /// Edge ID.
104   
105    /// The ID of a valid Edge is a nonnegative integer not greater than
106    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
107    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
108    ///
109    /// The ID of the \ref INVALID edge is -1.
110    ///\return The ID of the edge \c e.
111    static int id(Edge e) { return e.n; }
112
113    /// Finds an edge between two nodes.
114   
115    /// Finds an edge from node \c u to node \c v.
116    ///
117    /// If \c prev is \ref INVALID (this is the default value), then
118    /// It finds the first edge from \c u to \c v. Otherwise it looks for
119    /// the next edge from \c u to \c v after \c prev.
120    /// \return The found edge or INVALID if there is no such an edge.
121    Edge findEdge(Node u,Node v, Edge prev = INVALID)
122    {
123      return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
124    }
125   
126     
127    class Node {
128      friend class FullGraph;
129      template <typename T> friend class NodeMap;
130
131      friend class Edge;
132      friend class OutEdgeIt;
133      friend class InEdgeIt;
134      friend class SymEdge;
135
136    protected:
137      int n;
138      friend int FullGraph::id(Node v);
139      Node(int nn) {n=nn;}
140    public:
141      Node() {}
142      Node (Invalid) { n=-1; }
143      bool operator==(const Node i) const {return n==i.n;}
144      bool operator!=(const Node i) const {return n!=i.n;}
145      bool operator<(const Node i) const {return n<i.n;}
146    };
147   
148    class NodeIt : public Node {
149      const FullGraph *G;
150      friend class FullGraph;
151    public:
152      NodeIt() : Node() { }
153      NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
154      NodeIt(Invalid i) : Node(i) { }
155      NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
156      ///\todo Undocumented conversion Node -\> NodeIt.
157      NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
158    };
159
160    class Edge {
161      friend class FullGraph;
162      template <typename T> friend class EdgeMap;
163     
164      friend class Node;
165      friend class NodeIt;
166    protected:
167      int n; //NodeNum*head+tail;
168      friend int FullGraph::id(Edge e);
169
170      Edge(int nn) : n(nn) {}
171      Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
172    public:
173      Edge() { }
174      Edge (Invalid) { n=-1; }
175      bool operator==(const Edge i) const {return n==i.n;}
176      bool operator!=(const Edge i) const {return n!=i.n;}
177      bool operator<(const Edge i) const {return n<i.n;}
178      ///\bug This is a workaround until somebody tells me how to
179      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
180      int &idref() {return n;}
181      const int &idref() const {return n;}
182    };
183   
184    class EdgeIt : public Edge {
185      friend class FullGraph;
186    public:
187      EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
188      EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
189      EdgeIt (Invalid i) : Edge(i) { }
190      EdgeIt() : Edge() { }
191      EdgeIt& operator++() { --n; return *this; }
192
193      ///\bug This is a workaround until somebody tells me how to
194      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
195      int &idref() {return n;}
196    };
197   
198    class OutEdgeIt : public Edge {
199      const FullGraph *G;
200      friend class FullGraph;
201    public:
202      OutEdgeIt() : Edge() { }
203      OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
204      OutEdgeIt (Invalid i) : Edge(i) { }
205
206      OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
207     
208      OutEdgeIt& operator++()
209      { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
210
211    };
212   
213    class InEdgeIt : public Edge {
214      const FullGraph *G;
215      friend class FullGraph;
216    public:
217      InEdgeIt() : Edge() { }
218      InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
219      InEdgeIt (Invalid i) : Edge(i) { }
220      InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
221      InEdgeIt& operator++()
222      { if(!((++n)%G->NodeNum)) n=-1; return *this; }
223    };
224
225  };
226
227  /// @} 
228
229} //namespace hugo
230
231
232
233
234#endif //HUGO_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.