49 |
51 |
50 FullGraphBase() {} |
52 FullGraphBase() {} |
51 |
53 |
52 |
54 |
53 ///Creates a full graph with \c n nodes. |
55 ///Creates a full graph with \c n nodes. |
54 void construct(int n) { NodeNum = n; EdgeNum = n * n; } |
56 void construct(int n) { _nodeNum = n; _edgeNum = n * n; } |
55 /// |
57 /// |
56 // FullGraphBase(const FullGraphBase &_g) |
58 // FullGraphBase(const FullGraphBase &_g) |
57 // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { } |
59 // : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { } |
58 |
60 |
59 typedef True NodeNumTag; |
61 typedef True NodeNumTag; |
60 typedef True EdgeNumTag; |
62 typedef True EdgeNumTag; |
61 |
63 |
62 ///Number of nodes. |
64 ///Number of nodes. |
63 int nodeNum() const { return NodeNum; } |
65 int nodeNum() const { return _nodeNum; } |
64 ///Number of edges. |
66 ///Number of edges. |
65 int edgeNum() const { return EdgeNum; } |
67 int edgeNum() const { return _edgeNum; } |
66 |
68 |
67 /// Maximum node ID. |
69 /// Maximum node ID. |
68 |
70 |
69 /// Maximum node ID. |
71 /// Maximum node ID. |
70 ///\sa id(Node) |
72 ///\sa id(Node) |
71 int maxId(Node = INVALID) const { return NodeNum-1; } |
73 int maxId(Node = INVALID) const { return _nodeNum-1; } |
72 /// Maximum edge ID. |
74 /// Maximum edge ID. |
73 |
75 |
74 /// Maximum edge ID. |
76 /// Maximum edge ID. |
75 ///\sa id(Edge) |
77 ///\sa id(Edge) |
76 int maxId(Edge = INVALID) const { return EdgeNum-1; } |
78 int maxId(Edge = INVALID) const { return _edgeNum-1; } |
77 |
79 |
78 Node source(Edge e) const { return e.id % NodeNum; } |
80 Node source(Edge e) const { return e.id % _nodeNum; } |
79 Node target(Edge e) const { return e.id / NodeNum; } |
81 Node target(Edge e) const { return e.id / _nodeNum; } |
80 |
82 |
81 |
83 |
82 /// Node ID. |
84 /// Node ID. |
83 |
85 |
84 /// The ID of a valid Node is a nonnegative integer not greater than |
86 /// The ID of a valid Node is a nonnegative integer not greater than |
100 static int id(Edge e) { return e.id; } |
102 static int id(Edge e) { return e.id; } |
101 |
103 |
102 static Node fromId(int id, Node) { return Node(id);} |
104 static Node fromId(int id, Node) { return Node(id);} |
103 |
105 |
104 static Edge fromId(int id, Edge) { return Edge(id);} |
106 static Edge fromId(int id, Edge) { return Edge(id);} |
|
107 |
|
108 typedef True FindEdgeTag; |
105 |
109 |
106 /// Finds an edge between two nodes. |
110 /// Finds an edge between two nodes. |
107 |
111 |
108 /// Finds an edge from node \c u to node \c v. |
112 /// Finds an edge from node \c u to node \c v. |
109 /// |
113 /// |
110 /// If \c prev is \ref INVALID (this is the default value), then |
114 /// If \c prev is \ref INVALID (this is the default value), then |
111 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
115 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
112 /// the next edge from \c u to \c v after \c prev. |
116 /// the next edge from \c u to \c v after \c prev. |
113 /// \return The found edge or INVALID if there is no such an edge. |
117 /// \return The found edge or INVALID if there is no such an edge. |
114 Edge findEdge(Node u,Node v, Edge prev = INVALID) |
118 Edge findEdge(Node u,Node v, Edge prev = INVALID) const { |
115 { |
|
116 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID; |
119 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID; |
117 } |
120 } |
118 |
121 |
119 |
122 |
120 class Node { |
123 class Node { |
135 |
138 |
136 class Edge { |
139 class Edge { |
137 friend class FullGraphBase; |
140 friend class FullGraphBase; |
138 |
141 |
139 protected: |
142 protected: |
140 int id; // NodeNum * target + source; |
143 int id; // _nodeNum * target + source; |
141 |
144 |
142 Edge(int _id) : id(_id) {} |
145 Edge(int _id) : id(_id) {} |
143 |
146 |
144 Edge(const FullGraphBase& _graph, int source, int target) |
147 Edge(const FullGraphBase& _graph, int source, int target) |
145 : id(_graph.NodeNum * target+source) {} |
148 : id(_graph._nodeNum * target+source) {} |
146 public: |
149 public: |
147 Edge() { } |
150 Edge() { } |
148 Edge (Invalid) { id = -1; } |
151 Edge (Invalid) { id = -1; } |
149 bool operator==(const Edge edge) const {return id == edge.id;} |
152 bool operator==(const Edge edge) const {return id == edge.id;} |
150 bool operator!=(const Edge edge) const {return id != edge.id;} |
153 bool operator!=(const Edge edge) const {return id != edge.id;} |
151 bool operator<(const Edge edge) const {return id < edge.id;} |
154 bool operator<(const Edge edge) const {return id < edge.id;} |
152 }; |
155 }; |
153 |
156 |
154 void first(Node& node) const { |
157 void first(Node& node) const { |
155 node.id = NodeNum-1; |
158 node.id = _nodeNum-1; |
156 } |
159 } |
157 |
160 |
158 static void next(Node& node) { |
161 static void next(Node& node) { |
159 --node.id; |
162 --node.id; |
160 } |
163 } |
161 |
164 |
162 void first(Edge& edge) const { |
165 void first(Edge& edge) const { |
163 edge.id = EdgeNum-1; |
166 edge.id = _edgeNum-1; |
164 } |
167 } |
165 |
168 |
166 static void next(Edge& edge) { |
169 static void next(Edge& edge) { |
167 --edge.id; |
170 --edge.id; |
168 } |
171 } |
169 |
172 |
170 void firstOut(Edge& edge, const Node& node) const { |
173 void firstOut(Edge& edge, const Node& node) const { |
171 edge.id = EdgeNum + node.id - NodeNum; |
174 edge.id = _edgeNum + node.id - _nodeNum; |
172 } |
175 } |
173 |
176 |
174 void nextOut(Edge& edge) const { |
177 void nextOut(Edge& edge) const { |
175 edge.id -= NodeNum; |
178 edge.id -= _nodeNum; |
176 if (edge.id < 0) edge.id = -1; |
179 if (edge.id < 0) edge.id = -1; |
177 } |
180 } |
178 |
181 |
179 void firstIn(Edge& edge, const Node& node) const { |
182 void firstIn(Edge& edge, const Node& node) const { |
180 edge.id = node.id * NodeNum; |
183 edge.id = node.id * _nodeNum; |
181 } |
184 } |
182 |
185 |
183 void nextIn(Edge& edge) const { |
186 void nextIn(Edge& edge) const { |
184 ++edge.id; |
187 ++edge.id; |
185 if (edge.id % NodeNum == 0) edge.id = -1; |
188 if (edge.id % _nodeNum == 0) edge.id = -1; |
186 } |
189 } |
187 |
190 |
188 }; |
191 }; |
189 |
192 |
190 |
193 |
191 typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase; |
194 typedef AlterableGraphExtender<FullGraphBase> |
192 typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase; |
195 AlterableFullGraphBase; |
193 typedef DefaultMappableGraphExtender<IterableFullGraphBase> MappableFullGraphBase; |
196 typedef IterableGraphExtender<AlterableFullGraphBase> |
194 |
197 IterableFullGraphBase; |
195 /// \addtogroup graphs |
198 typedef DefaultMappableGraphExtender<IterableFullGraphBase> |
196 /// @{ |
199 MappableFullGraphBase; |
197 |
200 |
198 ///A full graph class. |
201 /// \ingroup graphs |
199 |
202 /// |
200 ///This is a simple and fast directed full graph implementation. |
203 /// \brief A full graph class. |
201 ///It is completely static, so you can neither add nor delete either |
204 /// |
202 ///edges or nodes. |
205 /// This is a simple and fast directed full graph implementation. |
203 ///Thus it conforms to |
206 /// It is completely static, so you can neither add nor delete either |
204 ///the \ref concept::StaticGraph "StaticGraph" concept |
207 /// edges or nodes. |
205 ///\sa concept::StaticGraph. |
208 /// Thus it conforms to |
206 /// |
209 /// the \ref concept::StaticGraph "StaticGraph" concept |
207 ///\author Alpar Juttner |
210 /// \sa concept::StaticGraph. |
|
211 /// |
|
212 /// \author Alpar Juttner |
208 class FullGraph : public MappableFullGraphBase { |
213 class FullGraph : public MappableFullGraphBase { |
209 public: |
214 public: |
210 |
215 |
211 FullGraph(int n) { construct(n); } |
216 FullGraph(int n) { construct(n); } |
212 }; |
217 }; |
213 |
218 |
214 ///@} |
219 ///@} |
215 |
220 |
216 // Base graph class for UndirFullGraph. |
|
217 class UndirFullGraphBase { |
221 class UndirFullGraphBase { |
218 int NodeNum; |
222 int _nodeNum; |
219 int EdgeNum; |
223 int _edgeNum; |
220 public: |
224 public: |
221 |
225 |
222 typedef UndirFullGraphBase Graph; |
226 typedef UndirFullGraphBase Graph; |
223 |
227 |
224 class Node; |
228 class Node; |
228 |
232 |
229 UndirFullGraphBase() {} |
233 UndirFullGraphBase() {} |
230 |
234 |
231 |
235 |
232 ///Creates a full graph with \c n nodes. |
236 ///Creates a full graph with \c n nodes. |
233 void construct(int n) { NodeNum = n; EdgeNum = n * (n - 1) / 2; } |
237 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; } |
234 /// |
238 /// |
235 // FullGraphBase(const FullGraphBase &_g) |
239 // FullGraphBase(const FullGraphBase &_g) |
236 // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { } |
240 // : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { } |
237 |
241 |
238 typedef True NodeNumTag; |
242 typedef True NodeNumTag; |
239 typedef True EdgeNumTag; |
243 typedef True EdgeNumTag; |
240 |
244 |
241 ///Number of nodes. |
245 ///Number of nodes. |
242 int nodeNum() const { return NodeNum; } |
246 int nodeNum() const { return _nodeNum; } |
243 ///Number of edges. |
247 ///Number of edges. |
244 int edgeNum() const { return EdgeNum; } |
248 int edgeNum() const { return _edgeNum; } |
245 |
249 |
246 /// Maximum node ID. |
250 /// Maximum node ID. |
247 |
251 |
248 /// Maximum node ID. |
252 /// Maximum node ID. |
249 ///\sa id(Node) |
253 ///\sa id(Node) |
250 int maxId(Node = INVALID) const { return NodeNum-1; } |
254 int maxId(Node = INVALID) const { return _nodeNum-1; } |
251 /// Maximum edge ID. |
255 /// Maximum edge ID. |
252 |
256 |
253 /// Maximum edge ID. |
257 /// Maximum edge ID. |
254 ///\sa id(Edge) |
258 ///\sa id(Edge) |
255 int maxId(Edge = INVALID) const { return EdgeNum-1; } |
259 int maxId(Edge = INVALID) const { return _edgeNum-1; } |
256 |
260 |
257 Node source(Edge e) const { |
261 Node source(Edge e) const { |
258 /// \todo we may do it faster |
262 /// \todo we may do it faster |
259 return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2; |
263 return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2; |
260 } |
264 } |
317 |
321 |
318 class Edge { |
322 class Edge { |
319 friend class UndirFullGraphBase; |
323 friend class UndirFullGraphBase; |
320 |
324 |
321 protected: |
325 protected: |
322 int id; // NodeNum * target + source; |
326 int id; // _nodeNum * target + source; |
323 |
327 |
324 Edge(int _id) : id(_id) {} |
328 Edge(int _id) : id(_id) {} |
325 |
329 |
326 Edge(const UndirFullGraphBase& _graph, int source, int target) |
330 Edge(const UndirFullGraphBase& _graph, int source, int target) |
327 : id(_graph.NodeNum * target+source) {} |
331 : id(_graph._nodeNum * target+source) {} |
328 public: |
332 public: |
329 Edge() { } |
333 Edge() { } |
330 Edge (Invalid) { id = -1; } |
334 Edge (Invalid) { id = -1; } |
331 bool operator==(const Edge edge) const {return id == edge.id;} |
335 bool operator==(const Edge edge) const {return id == edge.id;} |
332 bool operator!=(const Edge edge) const {return id != edge.id;} |
336 bool operator!=(const Edge edge) const {return id != edge.id;} |
333 bool operator<(const Edge edge) const {return id < edge.id;} |
337 bool operator<(const Edge edge) const {return id < edge.id;} |
334 }; |
338 }; |
335 |
339 |
336 void first(Node& node) const { |
340 void first(Node& node) const { |
337 node.id = NodeNum-1; |
341 node.id = _nodeNum-1; |
338 } |
342 } |
339 |
343 |
340 static void next(Node& node) { |
344 static void next(Node& node) { |
341 --node.id; |
345 --node.id; |
342 } |
346 } |
343 |
347 |
344 void first(Edge& edge) const { |
348 void first(Edge& edge) const { |
345 edge.id = EdgeNum-1; |
349 edge.id = _edgeNum-1; |
346 } |
350 } |
347 |
351 |
348 static void next(Edge& edge) { |
352 static void next(Edge& edge) { |
349 --edge.id; |
353 --edge.id; |
350 } |
354 } |
367 |
371 |
368 void nextIn(Edge& e) const { |
372 void nextIn(Edge& e) const { |
369 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
373 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
370 int target = e.id - (source) * (source - 1) / 2; ++target; |
374 int target = e.id - (source) * (source - 1) / 2; ++target; |
371 ++source; |
375 ++source; |
372 e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1; |
376 e.id = source < _nodeNum ? source * (source - 1) / 2 + target : -1; |
373 } |
377 } |
374 |
378 |
375 }; |
379 }; |
376 |
380 |
377 /// \addtogroup graphs |
381 typedef UndirGraphExtender<UndirFullGraphBase> |
378 /// @{ |
382 UndirUndirFullGraphBase; |
379 |
383 typedef AlterableUndirGraphExtender<UndirUndirFullGraphBase> |
380 |
384 AlterableUndirFullGraphBase; |
381 /// \todo UndirFullGraph from the UndirFullGraphBase |
385 typedef IterableUndirGraphExtender<AlterableUndirFullGraphBase> |
382 |
386 IterableUndirFullGraphBase; |
383 |
387 typedef MappableUndirGraphExtender<IterableUndirFullGraphBase> |
384 /// @} |
388 MappableUndirFullGraphBase; |
|
389 |
|
390 /// \ingroup graphs |
|
391 /// |
|
392 /// \brief An undirected full graph class. |
|
393 /// |
|
394 /// This is a simple and fast directed full graph implementation. |
|
395 /// It is completely static, so you can neither add nor delete either |
|
396 /// edges or nodes. |
|
397 /// |
|
398 /// The main difference beetween the \e FullGraph and \e UndirFullGraph class |
|
399 /// is that this class conforms to the undirected graph concept and |
|
400 /// it does not contain the hook edges. |
|
401 /// |
|
402 /// \sa FullGraph |
|
403 /// |
|
404 /// \author Balazs Dezso |
|
405 class UndirFullGraph : public MappableUndirFullGraphBase { |
|
406 public: |
|
407 UndirFullGraph(int n) { construct(n); } |
|
408 }; |
385 |
409 |
386 } //namespace lemon |
410 } //namespace lemon |
387 |
411 |
388 |
412 |
389 #endif //LEMON_FULL_GRAPH_H |
413 #endif //LEMON_FULL_GRAPH_H |