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