equal
deleted
inserted
replaced
21 |
21 |
22 |
22 |
23 #include <lemon/bits/iterable_graph_extender.h> |
23 #include <lemon/bits/iterable_graph_extender.h> |
24 #include <lemon/bits/alteration_notifier.h> |
24 #include <lemon/bits/alteration_notifier.h> |
25 #include <lemon/bits/static_map.h> |
25 #include <lemon/bits/static_map.h> |
26 |
26 #include <lemon/bits/graph_extender.h> |
27 #include <lemon/bits/undir_graph_extender.h> |
|
28 |
27 |
29 #include <lemon/invalid.h> |
28 #include <lemon/invalid.h> |
30 #include <lemon/utility.h> |
29 #include <lemon/utility.h> |
31 |
30 |
32 |
31 |
68 |
67 |
69 /// Maximum node ID. |
68 /// Maximum node ID. |
70 |
69 |
71 /// Maximum node ID. |
70 /// Maximum node ID. |
72 ///\sa id(Node) |
71 ///\sa id(Node) |
73 int maxId(Node = INVALID) const { return _nodeNum-1; } |
72 int maxNodeId() const { return _nodeNum-1; } |
74 /// Maximum edge ID. |
73 /// Maximum edge ID. |
75 |
74 |
76 /// Maximum edge ID. |
75 /// Maximum edge ID. |
77 ///\sa id(Edge) |
76 ///\sa id(Edge) |
78 int maxId(Edge = INVALID) const { return _edgeNum-1; } |
77 int maxEdgeId() const { return _edgeNum-1; } |
79 |
78 |
80 Node source(Edge e) const { return e.id % _nodeNum; } |
79 Node source(Edge e) const { return e.id % _nodeNum; } |
81 Node target(Edge e) const { return e.id / _nodeNum; } |
80 Node target(Edge e) const { return e.id / _nodeNum; } |
82 |
81 |
83 |
82 |
99 /// |
98 /// |
100 /// The ID of the \ref INVALID edge is -1. |
99 /// The ID of the \ref INVALID edge is -1. |
101 ///\return The ID of the edge \c e. |
100 ///\return The ID of the edge \c e. |
102 static int id(Edge e) { return e.id; } |
101 static int id(Edge e) { return e.id; } |
103 |
102 |
104 static Node fromId(int id, Node) { return Node(id);} |
103 static Node nodeFromId(int id) { return Node(id);} |
105 |
104 |
106 static Edge fromId(int id, Edge) { return Edge(id);} |
105 static Edge edgeFromId(int id) { return Edge(id);} |
107 |
106 |
108 typedef True FindEdgeTag; |
107 typedef True FindEdgeTag; |
109 |
108 |
110 /// Finds an edge between two nodes. |
109 /// Finds an edge between two nodes. |
111 |
110 |
188 if (edge.id % _nodeNum == 0) edge.id = -1; |
187 if (edge.id % _nodeNum == 0) edge.id = -1; |
189 } |
188 } |
190 |
189 |
191 }; |
190 }; |
192 |
191 |
193 |
|
194 typedef AlterableGraphExtender<FullGraphBase> |
|
195 AlterableFullGraphBase; |
|
196 typedef IterableGraphExtender<AlterableFullGraphBase> |
|
197 IterableFullGraphBase; |
|
198 typedef StaticMappableGraphExtender< |
192 typedef StaticMappableGraphExtender< |
199 IterableGraphExtender< |
193 IterableGraphExtender< |
200 AlterableGraphExtender<FullGraphBase> > > ExtendedFullGraphBase; |
194 AlterableGraphExtender< |
|
195 GraphExtender<FullGraphBase> > > > ExtendedFullGraphBase; |
201 |
196 |
202 /// \ingroup graphs |
197 /// \ingroup graphs |
203 /// |
198 /// |
204 /// \brief A full graph class. |
199 /// \brief A full graph class. |
205 /// |
200 /// |
215 public: |
210 public: |
216 |
211 |
217 FullGraph(int n) { construct(n); } |
212 FullGraph(int n) { construct(n); } |
218 }; |
213 }; |
219 |
214 |
220 ///@} |
|
221 |
215 |
222 class UndirFullGraphBase { |
216 class UndirFullGraphBase { |
223 int _nodeNum; |
217 int _nodeNum; |
224 int _edgeNum; |
218 int _edgeNum; |
225 public: |
219 public: |
250 |
244 |
251 /// Maximum node ID. |
245 /// Maximum node ID. |
252 |
246 |
253 /// Maximum node ID. |
247 /// Maximum node ID. |
254 ///\sa id(Node) |
248 ///\sa id(Node) |
255 int maxId(Node = INVALID) const { return _nodeNum-1; } |
249 int maxNodeId() const { return _nodeNum-1; } |
256 /// Maximum edge ID. |
250 /// Maximum edge ID. |
257 |
251 |
258 /// Maximum edge ID. |
252 /// Maximum edge ID. |
259 ///\sa id(Edge) |
253 ///\sa id(Edge) |
260 int maxId(Edge = INVALID) const { return _edgeNum-1; } |
254 int maxEdgeId() const { return _edgeNum-1; } |
261 |
255 |
262 Node source(Edge e) const { |
256 Node source(Edge e) const { |
263 /// \todo we may do it faster |
257 /// \todo we may do it faster |
264 return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2); |
258 return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2); |
265 } |
259 } |