134 |
134 |
135 class Edge { |
135 class Edge { |
136 friend class FullGraphBase; |
136 friend class FullGraphBase; |
137 |
137 |
138 protected: |
138 protected: |
139 int id; // NodeNum * head + tail; |
139 int id; // NodeNum * target + source; |
140 |
140 |
141 Edge(int _id) : id(_id) {} |
141 Edge(int _id) : id(_id) {} |
142 |
142 |
143 Edge(const FullGraphBase& _graph, int tail, int head) |
143 Edge(const FullGraphBase& _graph, int source, int target) |
144 : id(_graph.NodeNum * head+tail) {} |
144 : id(_graph.NodeNum * target+source) {} |
145 public: |
145 public: |
146 Edge() { } |
146 Edge() { } |
147 Edge (Invalid) { id = -1; } |
147 Edge (Invalid) { id = -1; } |
148 bool operator==(const Edge edge) const {return id == edge.id;} |
148 bool operator==(const Edge edge) const {return id == edge.id;} |
149 bool operator!=(const Edge edge) const {return id != edge.id;} |
149 bool operator!=(const Edge edge) const {return id != edge.id;} |
248 |
248 |
249 /// Maximum edge ID. |
249 /// Maximum edge ID. |
250 ///\sa id(Edge) |
250 ///\sa id(Edge) |
251 int maxId(Edge = INVALID) const { return EdgeNum-1; } |
251 int maxId(Edge = INVALID) const { return EdgeNum-1; } |
252 |
252 |
253 Node tail(Edge e) const { |
253 Node source(Edge e) const { |
254 /// \todo we may do it faster |
254 /// \todo we may do it faster |
255 return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2; |
255 return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2; |
256 } |
256 } |
257 |
257 |
258 Node head(Edge e) const { |
258 Node target(Edge e) const { |
259 int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
259 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
260 return e.id - (tail) * (tail - 1) / 2; |
260 return e.id - (source) * (source - 1) / 2; |
261 } |
261 } |
262 |
262 |
263 |
263 |
264 /// Node ID. |
264 /// Node ID. |
265 |
265 |
313 |
313 |
314 class Edge { |
314 class Edge { |
315 friend class UndirFullGraphBase; |
315 friend class UndirFullGraphBase; |
316 |
316 |
317 protected: |
317 protected: |
318 int id; // NodeNum * head + tail; |
318 int id; // NodeNum * target + source; |
319 |
319 |
320 Edge(int _id) : id(_id) {} |
320 Edge(int _id) : id(_id) {} |
321 |
321 |
322 Edge(const UndirFullGraphBase& _graph, int tail, int head) |
322 Edge(const UndirFullGraphBase& _graph, int source, int target) |
323 : id(_graph.NodeNum * head+tail) {} |
323 : id(_graph.NodeNum * target+source) {} |
324 public: |
324 public: |
325 Edge() { } |
325 Edge() { } |
326 Edge (Invalid) { id = -1; } |
326 Edge (Invalid) { id = -1; } |
327 bool operator==(const Edge edge) const {return id == edge.id;} |
327 bool operator==(const Edge edge) const {return id == edge.id;} |
328 bool operator!=(const Edge edge) const {return id != edge.id;} |
328 bool operator!=(const Edge edge) const {return id != edge.id;} |
349 edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1; |
349 edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1; |
350 } |
350 } |
351 |
351 |
352 /// \todo with specialized iterators we can make faster iterating |
352 /// \todo with specialized iterators we can make faster iterating |
353 void nextOut(Edge& e) const { |
353 void nextOut(Edge& e) const { |
354 int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
354 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
355 int head = e.id - (tail) * (tail - 1) / 2; |
355 int target = e.id - (source) * (source - 1) / 2; |
356 ++head; |
356 ++target; |
357 e.id = head < tail ? tail * (tail - 1) / 2 + head : -1; |
357 e.id = target < source ? source * (source - 1) / 2 + target : -1; |
358 } |
358 } |
359 |
359 |
360 void firstIn(Edge& edge, const Node& node) const { |
360 void firstIn(Edge& edge, const Node& node) const { |
361 edge.id = node.id * (node.id + 1) / 2 - 1; |
361 edge.id = node.id * (node.id + 1) / 2 - 1; |
362 } |
362 } |
363 |
363 |
364 void nextIn(Edge& e) const { |
364 void nextIn(Edge& e) const { |
365 int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
365 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
366 int head = e.id - (tail) * (tail - 1) / 2; ++head; |
366 int target = e.id - (source) * (source - 1) / 2; ++target; |
367 ++tail; |
367 ++source; |
368 e.id = tail < NodeNum ? tail * (tail - 1) / 2 + head : -1; |
368 e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1; |
369 } |
369 } |
370 |
370 |
371 }; |
371 }; |
372 |
372 |
373 /// \todo UndirFullGraph from the UndirFullGraphBase |
373 /// \todo UndirFullGraph from the UndirFullGraphBase |