296 // operator bool() { return Edge::operator bool(); } |
294 // operator bool() { return Edge::operator bool(); } |
297 }; |
295 }; |
298 |
296 |
299 }; |
297 }; |
300 |
298 |
|
299 |
|
300 |
|
301 class SymSmartGraph : public SmartGraph { |
|
302 typedef SmartGraph Parent; |
|
303 public: |
|
304 |
|
305 typedef SymSmartGraph Graph; |
|
306 |
|
307 typedef SmartGraph::Node Node; |
|
308 typedef SmartGraph::NodeIt NodeIt; |
|
309 |
|
310 class SymEdge; |
|
311 class SymEdgeIt; |
|
312 |
|
313 class Edge; |
|
314 class EdgeIt; |
|
315 class OutEdgeIt; |
|
316 class InEdgeIt; |
|
317 |
|
318 template <typename Value> |
|
319 class NodeMap : public Parent::NodeMap<Value> { |
|
320 public: |
|
321 NodeMap(const SymSmartGraph& g) |
|
322 : SymSmartGraph::Parent::NodeMap<Value>(g) {} |
|
323 NodeMap(const SymSmartGraph& g, Value v) |
|
324 : SymSmartGraph::Parent::NodeMap<Value>(g, v) {} |
|
325 template<typename TT> |
|
326 NodeMap(const NodeMap<TT>& copy) |
|
327 : SymSmartGraph::Parent::NodeMap<Value>(copy) { } |
|
328 }; |
|
329 |
|
330 template <typename Value> |
|
331 class SymEdgeMap : public Parent::EdgeMap<Value> { |
|
332 public: |
|
333 typedef SymEdge KeyType; |
|
334 |
|
335 SymEdgeMap(const SymSmartGraph& g) |
|
336 : SymSmartGraph::Parent::EdgeMap<Value>(g) {} |
|
337 SymEdgeMap(const SymSmartGraph& g, Value v) |
|
338 : SymSmartGraph::Parent::EdgeMap<Value>(g, v) {} |
|
339 template<typename TT> |
|
340 SymEdgeMap(const SymEdgeMap<TT>& copy) |
|
341 : SymSmartGraph::Parent::EdgeMap<Value>(copy) { } |
|
342 |
|
343 }; |
|
344 |
|
345 // Create edge map registry. |
|
346 CREATE_EDGE_MAP_REGISTRY; |
|
347 // Create edge maps. |
|
348 CREATE_EDGE_MAP(ArrayMap); |
|
349 |
|
350 class Edge { |
|
351 friend class SymSmartGraph; |
|
352 friend class SymSmartGraph::EdgeIt; |
|
353 friend class SymSmartGraph::OutEdgeIt; |
|
354 friend class SymSmartGraph::InEdgeIt; |
|
355 |
|
356 protected: |
|
357 int id; |
|
358 |
|
359 Edge(int pid) { id = pid; } |
|
360 |
|
361 public: |
|
362 /// An Edge with id \c n. |
|
363 |
|
364 Edge() { } |
|
365 Edge (Invalid) { id = -1; } |
|
366 |
|
367 operator SymEdge(){ return SymEdge(id >> 1);} |
|
368 |
|
369 bool operator==(const Edge i) const {return id == i.id;} |
|
370 bool operator!=(const Edge i) const {return id != i.id;} |
|
371 bool operator<(const Edge i) const {return id < i.id;} |
|
372 // ///Validity check |
|
373 // operator bool() { return n!=-1; } |
|
374 }; |
|
375 |
|
376 class SymEdge : public SmartGraph::Edge { |
|
377 friend class SymSmartGraph; |
|
378 friend class SymSmartGraph::Edge; |
|
379 typedef SmartGraph::Edge Parent; |
|
380 |
|
381 protected: |
|
382 SymEdge(int pid) : Parent(pid) {} |
|
383 public: |
|
384 |
|
385 SymEdge() { } |
|
386 SymEdge(const SmartGraph::Edge& i) : Parent(i) {} |
|
387 SymEdge (Invalid) : Parent(INVALID) {} |
|
388 |
|
389 }; |
|
390 |
|
391 class OutEdgeIt { |
|
392 Parent::OutEdgeIt out; |
|
393 Parent::InEdgeIt in; |
|
394 public: |
|
395 OutEdgeIt() {} |
|
396 OutEdgeIt(const SymSmartGraph& g, Edge e) { |
|
397 if (e.id & 1 == 0) { |
|
398 out = Parent::OutEdgeIt(g, SymEdge(e)); |
|
399 in = Parent::InEdgeIt(g, g.tail(e)); |
|
400 } else { |
|
401 out = Parent::OutEdgeIt(INVALID); |
|
402 in = Parent::InEdgeIt(g, SymEdge(e)); |
|
403 } |
|
404 } |
|
405 OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } |
|
406 |
|
407 OutEdgeIt(const SymSmartGraph& g, const Node v) |
|
408 : out(g, v), in(g, v) {} |
|
409 OutEdgeIt &operator++() { |
|
410 if (out != INVALID) { |
|
411 ++out; |
|
412 } else { |
|
413 ++in; |
|
414 } |
|
415 return *this; |
|
416 } |
|
417 |
|
418 operator Edge() const { |
|
419 if (out == INVALID && in == INVALID) return INVALID; |
|
420 return out != INVALID ? forward(out) : backward(in); |
|
421 } |
|
422 |
|
423 bool operator==(const Edge i) const {return Edge(*this) == i;} |
|
424 bool operator!=(const Edge i) const {return Edge(*this) != i;} |
|
425 bool operator<(const Edge i) const {return Edge(*this) < i;} |
|
426 }; |
|
427 |
|
428 class InEdgeIt { |
|
429 Parent::OutEdgeIt out; |
|
430 Parent::InEdgeIt in; |
|
431 public: |
|
432 InEdgeIt() {} |
|
433 InEdgeIt(const SymSmartGraph& g, Edge e) { |
|
434 if (e.id & 1 == 0) { |
|
435 out = Parent::OutEdgeIt(g, SymEdge(e)); |
|
436 in = Parent::InEdgeIt(g, g.tail(e)); |
|
437 } else { |
|
438 out = Parent::OutEdgeIt(INVALID); |
|
439 in = Parent::InEdgeIt(g, SymEdge(e)); |
|
440 } |
|
441 } |
|
442 InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } |
|
443 |
|
444 InEdgeIt(const SymSmartGraph& g, const Node v) |
|
445 : out(g, v), in(g, v) {} |
|
446 |
|
447 InEdgeIt &operator++() { |
|
448 if (out != INVALID) { |
|
449 ++out; |
|
450 } else { |
|
451 ++in; |
|
452 } |
|
453 return *this; |
|
454 } |
|
455 |
|
456 operator Edge() const { |
|
457 if (out == INVALID && in == INVALID) return INVALID; |
|
458 return out != INVALID ? backward(out) : forward(in); |
|
459 } |
|
460 |
|
461 bool operator==(const Edge i) const {return Edge(*this) == i;} |
|
462 bool operator!=(const Edge i) const {return Edge(*this) != i;} |
|
463 bool operator<(const Edge i) const {return Edge(*this) < i;} |
|
464 }; |
|
465 |
|
466 class SymEdgeIt : public Parent::EdgeIt { |
|
467 |
|
468 public: |
|
469 SymEdgeIt() {} |
|
470 |
|
471 SymEdgeIt(const SymSmartGraph& g) |
|
472 : SymSmartGraph::Parent::EdgeIt(g) {} |
|
473 |
|
474 SymEdgeIt(const SymSmartGraph& g, SymEdge e) |
|
475 : SymSmartGraph::Parent::EdgeIt(g, e) {} |
|
476 |
|
477 SymEdgeIt(Invalid i) |
|
478 : SymSmartGraph::Parent::EdgeIt(INVALID) {} |
|
479 |
|
480 SymEdgeIt& operator++() { |
|
481 SymSmartGraph::Parent::EdgeIt::operator++(); |
|
482 return *this; |
|
483 } |
|
484 |
|
485 operator SymEdge() const { |
|
486 return SymEdge |
|
487 (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this)); |
|
488 } |
|
489 bool operator==(const SymEdge i) const {return SymEdge(*this) == i;} |
|
490 bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;} |
|
491 bool operator<(const SymEdge i) const {return SymEdge(*this) < i;} |
|
492 }; |
|
493 |
|
494 class EdgeIt { |
|
495 SymEdgeIt it; |
|
496 bool fw; |
|
497 public: |
|
498 EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {} |
|
499 EdgeIt (Invalid i) : it(i) { } |
|
500 EdgeIt(const SymSmartGraph& g, Edge e) |
|
501 : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { } |
|
502 EdgeIt() { } |
|
503 EdgeIt& operator++() { |
|
504 fw = !fw; |
|
505 if (fw) ++it; |
|
506 return *this; |
|
507 } |
|
508 operator Edge() const { |
|
509 if (it == INVALID) return INVALID; |
|
510 return fw ? forward(it) : backward(it); |
|
511 } |
|
512 bool operator==(const Edge i) const {return Edge(*this) == i;} |
|
513 bool operator!=(const Edge i) const {return Edge(*this) != i;} |
|
514 bool operator<(const Edge i) const {return Edge(*this) < i;} |
|
515 |
|
516 }; |
|
517 |
|
518 ///Number of nodes. |
|
519 int nodeNum() const { return Parent::nodeNum(); } |
|
520 ///Number of edges. |
|
521 int edgeNum() const { return 2*Parent::edgeNum(); } |
|
522 ///Number of symmetric edges. |
|
523 int symEdgeNum() const { return Parent::edgeNum(); } |
|
524 |
|
525 /// Maximum node ID. |
|
526 |
|
527 /// Maximum node ID. |
|
528 ///\sa id(Node) |
|
529 int maxNodeId() const { return Parent::maxNodeId(); } |
|
530 /// Maximum edge ID. |
|
531 |
|
532 /// Maximum edge ID. |
|
533 ///\sa id(Edge) |
|
534 int maxEdgeId() const { return 2*Parent::maxEdgeId(); } |
|
535 /// Maximum symmetric edge ID. |
|
536 |
|
537 /// Maximum symmetric edge ID. |
|
538 ///\sa id(SymEdge) |
|
539 int maxSymEdgeId() const { return Parent::maxEdgeId(); } |
|
540 |
|
541 |
|
542 Node tail(Edge e) const { |
|
543 return e.id & 1 == 0 ? |
|
544 Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e)); |
|
545 } |
|
546 |
|
547 Node head(Edge e) const { |
|
548 return e.id & 1 == 0 ? |
|
549 Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e)); |
|
550 } |
|
551 |
|
552 Node tail(SymEdge e) const { |
|
553 return Parent::tail(e); |
|
554 } |
|
555 |
|
556 Node head(SymEdge e) const { |
|
557 return Parent::head(e); |
|
558 } |
|
559 |
|
560 NodeIt& first(NodeIt& v) const { |
|
561 v=NodeIt(*this); return v; } |
|
562 EdgeIt& first(EdgeIt& e) const { |
|
563 e=EdgeIt(*this); return e; } |
|
564 SymEdgeIt& first(SymEdgeIt& e) const { |
|
565 e=SymEdgeIt(*this); return e; } |
|
566 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
|
567 e=OutEdgeIt(*this,v); return e; } |
|
568 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
|
569 e=InEdgeIt(*this,v); return e; } |
|
570 |
|
571 /// Node ID. |
|
572 |
|
573 /// The ID of a valid Node is a nonnegative integer not greater than |
|
574 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
|
575 /// and the greatest node ID can be actually less then \ref maxNodeId(). |
|
576 /// |
|
577 /// The ID of the \ref INVALID node is -1. |
|
578 ///\return The ID of the node \c v. |
|
579 static int id(Node v) { return Parent::id(v); } |
|
580 /// Edge ID. |
|
581 |
|
582 /// The ID of a valid Edge is a nonnegative integer not greater than |
|
583 /// \ref maxEdgeId(). The range of the ID's is not surely continuous |
|
584 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). |
|
585 /// |
|
586 /// The ID of the \ref INVALID edge is -1. |
|
587 ///\return The ID of the edge \c e. |
|
588 static int id(Edge e) { return e.id; } |
|
589 |
|
590 /// The ID of a valid SymEdge is a nonnegative integer not greater than |
|
591 /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous |
|
592 /// and the greatest edge ID can be actually less then \ref maxSymEdgeId(). |
|
593 /// |
|
594 /// The ID of the \ref INVALID symmetric edge is -1. |
|
595 ///\return The ID of the edge \c e. |
|
596 static int id(SymEdge e) { return Parent::id(e); } |
|
597 |
|
598 /// Adds a new node to the graph. |
|
599 |
|
600 /// \warning It adds the new node to the front of the list. |
|
601 /// (i.e. the lastly added node becomes the first.) |
|
602 Node addNode() { |
|
603 return Parent::addNode(); |
|
604 } |
|
605 |
|
606 SymEdge addEdge(Node u, Node v) { |
|
607 SymEdge se = Parent::addEdge(u, v); |
|
608 edge_maps.add(forward(se)); |
|
609 edge_maps.add(backward(se)); |
|
610 return se; |
|
611 } |
|
612 |
|
613 /// Finds an edge between two nodes. |
|
614 |
|
615 /// Finds an edge from node \c u to node \c v. |
|
616 /// |
|
617 /// If \c prev is \ref INVALID (this is the default value), then |
|
618 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
|
619 /// the next edge from \c u to \c v after \c prev. |
|
620 /// \return The found edge or INVALID if there is no such an edge. |
|
621 Edge findEdge(Node u, Node v, Edge prev = INVALID) |
|
622 { |
|
623 if (prev == INVALID || id(prev) & 1 == 0) { |
|
624 SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); |
|
625 if (se != INVALID) return forward(se); |
|
626 } else { |
|
627 SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); |
|
628 if (se != INVALID) return backward(se); |
|
629 } |
|
630 return INVALID; |
|
631 } |
|
632 |
|
633 /// Finds an symmetric edge between two nodes. |
|
634 |
|
635 /// Finds an symmetric edge from node \c u to node \c v. |
|
636 /// |
|
637 /// If \c prev is \ref INVALID (this is the default value), then |
|
638 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
|
639 /// the next edge from \c u to \c v after \c prev. |
|
640 /// \return The found edge or INVALID if there is no such an edge. |
|
641 |
|
642 // SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID) |
|
643 // { |
|
644 // if (prev == INVALID || id(prev) & 1 == 0) { |
|
645 // SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); |
|
646 // if (se != INVALID) return se; |
|
647 // } else { |
|
648 // SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); |
|
649 // if (se != INVALID) return se; |
|
650 // } |
|
651 // return INVALID; |
|
652 // } |
|
653 |
|
654 public: |
|
655 |
|
656 void clear() { |
|
657 edge_maps.clear(); |
|
658 Parent::clear(); |
|
659 } |
|
660 |
|
661 static Edge opposite(Edge e) { |
|
662 return Edge(id(e) ^ 1); |
|
663 } |
|
664 |
|
665 static Edge forward(SymEdge e) { |
|
666 return Edge(id(e) << 1); |
|
667 } |
|
668 |
|
669 static Edge backward(SymEdge e) { |
|
670 return Edge((id(e) << 1) & 1); |
|
671 } |
|
672 |
|
673 }; |
301 ///Graph for bidirectional edges. |
674 ///Graph for bidirectional edges. |
302 |
675 |
303 ///The purpose of this graph structure is to handle graphs |
676 ///The purpose of this graph structure is to handle graphs |
304 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair |
677 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair |
305 ///of oppositely directed edges. |
678 ///of oppositely directed edges. |