193 |
193 |
194 typedef AlterableGraphExtender<FullGraphBase> |
194 typedef AlterableGraphExtender<FullGraphBase> |
195 AlterableFullGraphBase; |
195 AlterableFullGraphBase; |
196 typedef IterableGraphExtender<AlterableFullGraphBase> |
196 typedef IterableGraphExtender<AlterableFullGraphBase> |
197 IterableFullGraphBase; |
197 IterableFullGraphBase; |
198 typedef MappableGraphExtender< |
198 typedef StaticMappableGraphExtender< |
199 IterableGraphExtender< |
199 IterableGraphExtender< |
200 AlterableGraphExtender<FullGraphBase> > > ExtendedFullGraphBase; |
200 AlterableGraphExtender<FullGraphBase> > > ExtendedFullGraphBase; |
201 |
201 |
202 /// \ingroup graphs |
202 /// \ingroup graphs |
203 /// |
203 /// |
296 /// |
296 /// |
297 /// If \c prev is \ref INVALID (this is the default value), then |
297 /// If \c prev is \ref INVALID (this is the default value), then |
298 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
298 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
299 /// the next edge from \c u to \c v after \c prev. |
299 /// the next edge from \c u to \c v after \c prev. |
300 /// \return The found edge or INVALID if there is no such an edge. |
300 /// \return The found edge or INVALID if there is no such an edge. |
301 Edge findEdge(Node u,Node v, Edge prev = INVALID) |
301 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { |
302 { |
302 if (prev.id != -1 || u.id <= v.id) return -1; |
303 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID; |
303 return Edge(u.id * (u.id - 1) / 2 + v.id); |
304 } |
304 } |
|
305 |
|
306 typedef True FindEdgeTag; |
305 |
307 |
306 |
308 |
307 class Node { |
309 class Node { |
308 friend class UndirFullGraphBase; |
310 friend class UndirFullGraphBase; |
309 |
311 |
326 protected: |
328 protected: |
327 int id; // _nodeNum * target + source; |
329 int id; // _nodeNum * target + source; |
328 |
330 |
329 Edge(int _id) : id(_id) {} |
331 Edge(int _id) : id(_id) {} |
330 |
332 |
331 Edge(const UndirFullGraphBase& _graph, int source, int target) |
|
332 : id(_graph._nodeNum * target+source) {} |
|
333 public: |
333 public: |
334 Edge() { } |
334 Edge() { } |
335 Edge (Invalid) { id = -1; } |
335 Edge (Invalid) { id = -1; } |
336 bool operator==(const Edge edge) const {return id == edge.id;} |
336 bool operator==(const Edge edge) const {return id == edge.id;} |
337 bool operator!=(const Edge edge) const {return id != edge.id;} |
337 bool operator!=(const Edge edge) const {return id != edge.id;} |
338 bool operator<(const Edge edge) const {return id < edge.id;} |
338 bool operator<(const Edge edge) const {return id < edge.id;} |
339 }; |
339 }; |
340 |
340 |
341 void first(Node& node) const { |
341 void first(Node& node) const { |
342 node.id = _nodeNum-1; |
342 node.id = _nodeNum - 1; |
343 } |
343 } |
344 |
344 |
345 static void next(Node& node) { |
345 static void next(Node& node) { |
346 --node.id; |
346 --node.id; |
347 } |
347 } |
348 |
348 |
349 void first(Edge& edge) const { |
349 void first(Edge& edge) const { |
350 edge.id = _edgeNum-1; |
350 edge.id = _edgeNum - 1; |
351 } |
351 } |
352 |
352 |
353 static void next(Edge& edge) { |
353 static void next(Edge& edge) { |
354 --edge.id; |
354 --edge.id; |
355 } |
355 } |
356 |
356 |
357 void firstOut(Edge& edge, const Node& node) const { |
357 void firstOut(Edge& edge, const Node& node) const { |
358 edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1; |
358 int src = node.id; |
|
359 int trg = 0; |
|
360 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); |
359 } |
361 } |
360 |
362 |
361 /// \todo with specialized iterators we can make faster iterating |
363 /// \todo with specialized iterators we can make faster iterating |
362 void nextOut(Edge& e) const { |
364 void nextOut(Edge& edge) const { |
363 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
365 int src = source(edge).id; |
364 int target = e.id - (source) * (source - 1) / 2; |
366 int trg = target(edge).id; |
365 ++target; |
367 ++trg; |
366 e.id = target < source ? source * (source - 1) / 2 + target : -1; |
368 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); |
367 } |
369 } |
368 |
370 |
369 void firstIn(Edge& edge, const Node& node) const { |
371 void firstIn(Edge& edge, const Node& node) const { |
370 edge.id = node.id * (node.id + 1) / 2 - 1; |
372 int src = node.id + 1; |
371 } |
373 int trg = node.id; |
372 |
374 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); |
373 void nextIn(Edge& e) const { |
375 } |
374 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
376 |
375 int target = e.id - (source) * (source - 1) / 2; ++target; |
377 void nextIn(Edge& edge) const { |
376 ++source; |
378 int src = source(edge).id; |
377 e.id = source < _nodeNum ? source * (source - 1) / 2 + target : -1; |
379 int trg = target(edge).id; |
|
380 ++src; |
|
381 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); |
378 } |
382 } |
379 |
383 |
380 }; |
384 }; |
381 |
385 |
382 typedef MappableUndirGraphExtender< |
386 typedef StaticMappableUndirGraphExtender< |
383 IterableUndirGraphExtender< |
387 IterableUndirGraphExtender< |
384 AlterableUndirGraphExtender< |
388 AlterableUndirGraphExtender< |
385 UndirGraphExtender<UndirFullGraphBase> > > > ExtendedUndirFullGraphBase; |
389 UndirGraphExtender<UndirFullGraphBase> > > > ExtendedUndirFullGraphBase; |
386 |
390 |
387 /// \ingroup graphs |
391 /// \ingroup graphs |