Changeset 919:6153d9cf78c6 in lemon-0.x for src
- Timestamp:
- 09/29/04 16:02:14 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1230
- Location:
- src
- Files:
-
- 1 added
- 3 deleted
- 11 edited
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/Makefile.am
r909 r919 19 19 map_bits.h \ 20 20 maps.h \ 21 min_cost_flow.h 21 min_cost_flow.h \ 22 22 suurballe.h \ 23 23 preflow.h \ 24 24 path.h \ 25 25 smart_graph.h \ 26 sym_map.h \ 26 27 time_measure.h \ 27 28 unionfind.h \ … … 31 32 noinst_HEADERS = \ 32 33 skeletons/graph.h \ 33 skeletons/sym_graph.h \34 34 skeletons/maps.h \ 35 35 skeletons/path.h -
src/hugo/default_map.h
r909 r919 60 60 template <typename TT> \ 61 61 DefaultMap(const DefaultMap<MapRegistry, TT>& copy) \ 62 : Parent(*copy.getGraph()) { \ 62 : { \ 63 Parent::MapBase::operator= \ 64 (static_cast<const typename Parent::MapBase&>(copy)); \ 63 65 if (Parent::getGraph()) { \ 64 66 for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\ 67 Parent::add(it); \ 65 68 Parent::operator[](it) = copy[it]; \ 66 69 } \ -
src/hugo/list_graph.h
r916 r919 30 30 #include <hugo/array_map.h> 31 31 32 #include <hugo/sym_map.h> 33 32 34 #include <hugo/map_defines.h> 33 35 … … 103 105 first_free_edge(_g.first_free_edge) {} 104 106 105 /// \bug In the vector can be hole if a node is erased from the graph.106 107 ///Number of nodes. 107 108 int nodeNum() const { return nodes.size(); } … … 438 439 ///\todo this date structure need some reconsiderations. Maybe it 439 440 ///should be implemented independently from ListGraph. 440 /*441 441 442 class SymListGraph : public ListGraph 442 443 { … … 483 484 ListGraph::erase(e); 484 485 } 485 };*/486 487 class SymListGraph : public ListGraph {488 typedef ListGraph Parent;489 public:490 491 typedef SymListGraph Graph;492 493 typedef ListGraph::Node Node;494 typedef ListGraph::NodeIt NodeIt;495 496 class SymEdge;497 class SymEdgeIt;498 499 class Edge;500 class EdgeIt;501 class OutEdgeIt;502 class InEdgeIt;503 504 template <typename Value>505 class NodeMap : public Parent::NodeMap<Value> {506 public:507 NodeMap(const SymListGraph& g)508 : SymListGraph::Parent::NodeMap<Value>(g) {}509 NodeMap(const SymListGraph& g, Value v)510 : SymListGraph::Parent::NodeMap<Value>(g, v) {}511 template<typename TT>512 NodeMap(const NodeMap<TT>& copy)513 : SymListGraph::Parent::NodeMap<Value>(copy) { }514 };515 516 template <typename Value>517 class SymEdgeMap : public Parent::EdgeMap<Value> {518 public:519 typedef SymEdge KeyType;520 521 SymEdgeMap(const SymListGraph& g)522 : SymListGraph::Parent::EdgeMap<Value>(g) {}523 SymEdgeMap(const SymListGraph& g, Value v)524 : SymListGraph::Parent::EdgeMap<Value>(g, v) {}525 template<typename TT>526 SymEdgeMap(const SymEdgeMap<TT>& copy)527 : SymListGraph::Parent::EdgeMap<Value>(copy) { }528 529 };530 531 // Create edge map registry.532 CREATE_EDGE_MAP_REGISTRY;533 // Create edge maps.534 CREATE_EDGE_MAP(ArrayMap);535 536 class Edge {537 friend class SymListGraph;538 friend class SymListGraph::EdgeIt;539 friend class SymListGraph::OutEdgeIt;540 friend class SymListGraph::InEdgeIt;541 542 protected:543 int id;544 545 Edge(int pid) { id = pid; }546 547 public:548 /// An Edge with id \c n.549 550 Edge() { }551 Edge (Invalid) { id = -1; }552 553 operator SymEdge(){ return SymEdge(id >> 1);}554 555 bool operator==(const Edge i) const {return id == i.id;}556 bool operator!=(const Edge i) const {return id != i.id;}557 bool operator<(const Edge i) const {return id < i.id;}558 // ///Validity check559 // operator bool() { return n!=-1; }560 };561 562 class SymEdge : public ListGraph::Edge {563 friend class SymListGraph;564 friend class SymListGraph::Edge;565 typedef ListGraph::Edge Parent;566 567 protected:568 SymEdge(int pid) : Parent(pid) {}569 public:570 571 SymEdge() { }572 SymEdge(const ListGraph::Edge& i) : Parent(i) {}573 SymEdge (Invalid) : Parent(INVALID) {}574 575 };576 577 class OutEdgeIt {578 Parent::OutEdgeIt out;579 Parent::InEdgeIt in;580 public:581 OutEdgeIt() {}582 OutEdgeIt(const SymListGraph& g, Edge e) {583 if ((e.id & 1) == 0) {584 out = Parent::OutEdgeIt(g, SymEdge(e));585 in = Parent::InEdgeIt(g, g.tail(e));586 } else {587 out = Parent::OutEdgeIt(INVALID);588 in = Parent::InEdgeIt(g, SymEdge(e));589 }590 }591 OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }592 593 OutEdgeIt(const SymListGraph& g, const Node v)594 : out(g, v), in(g, v) {}595 OutEdgeIt &operator++() {596 if (out != INVALID) {597 ++out;598 } else {599 ++in;600 }601 return *this;602 }603 604 operator Edge() const {605 if (out == INVALID && in == INVALID) return INVALID;606 return out != INVALID ? forward(out) : backward(in);607 }608 609 bool operator==(const Edge i) const {return Edge(*this) == i;}610 bool operator!=(const Edge i) const {return Edge(*this) != i;}611 bool operator<(const Edge i) const {return Edge(*this) < i;}612 };613 614 class InEdgeIt {615 Parent::OutEdgeIt out;616 Parent::InEdgeIt in;617 public:618 InEdgeIt() {}619 InEdgeIt(const SymListGraph& g, Edge e) {620 if ((e.id & 1) == 0) {621 out = Parent::OutEdgeIt(g, SymEdge(e));622 in = Parent::InEdgeIt(g, g.tail(e));623 } else {624 out = Parent::OutEdgeIt(INVALID);625 in = Parent::InEdgeIt(g, SymEdge(e));626 }627 }628 InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }629 630 InEdgeIt(const SymListGraph& g, const Node v)631 : out(g, v), in(g, v) {}632 633 InEdgeIt &operator++() {634 if (out != INVALID) {635 ++out;636 } else {637 ++in;638 }639 return *this;640 }641 642 operator Edge() const {643 if (out == INVALID && in == INVALID) return INVALID;644 return out != INVALID ? backward(out) : forward(in);645 }646 647 bool operator==(const Edge i) const {return Edge(*this) == i;}648 bool operator!=(const Edge i) const {return Edge(*this) != i;}649 bool operator<(const Edge i) const {return Edge(*this) < i;}650 };651 652 class SymEdgeIt : public Parent::EdgeIt {653 654 public:655 SymEdgeIt() {}656 657 SymEdgeIt(const SymListGraph& g)658 : SymListGraph::Parent::EdgeIt(g) {}659 660 SymEdgeIt(const SymListGraph& g, SymEdge e)661 : SymListGraph::Parent::EdgeIt(g, e) {}662 663 SymEdgeIt(Invalid i)664 : SymListGraph::Parent::EdgeIt(INVALID) {}665 666 SymEdgeIt& operator++() {667 SymListGraph::Parent::EdgeIt::operator++();668 return *this;669 }670 671 operator SymEdge() const {672 return SymEdge673 (static_cast<const SymListGraph::Parent::EdgeIt&>(*this));674 }675 bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}676 bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}677 bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}678 };679 680 class EdgeIt {681 SymEdgeIt it;682 bool fw;683 public:684 EdgeIt(const SymListGraph& g) : it(g), fw(true) {}685 EdgeIt (Invalid i) : it(i) { }686 EdgeIt(const SymListGraph& g, Edge e)687 : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }688 EdgeIt() { }689 EdgeIt& operator++() {690 fw = !fw;691 if (fw) ++it;692 return *this;693 }694 operator Edge() const {695 if (it == INVALID) return INVALID;696 return fw ? forward(it) : backward(it);697 }698 bool operator==(const Edge i) const {return Edge(*this) == i;}699 bool operator!=(const Edge i) const {return Edge(*this) != i;}700 bool operator<(const Edge i) const {return Edge(*this) < i;}701 702 };703 704 ///Number of nodes.705 int nodeNum() const { return Parent::nodeNum(); }706 ///Number of edges.707 int edgeNum() const { return 2*Parent::edgeNum(); }708 ///Number of symmetric edges.709 int symEdgeNum() const { return Parent::edgeNum(); }710 711 ///Set the expected maximum number of edges.712 713 ///With this function, it is possible to set the expected number of edges.714 ///The use of this fasten the building of the graph and makes715 ///it possible to avoid the superfluous memory allocation.716 void reserveSymEdge(int n) { Parent::reserveEdge(n); };717 718 /// Maximum node ID.719 720 /// Maximum node ID.721 ///\sa id(Node)722 int maxNodeId() const { return Parent::maxNodeId(); }723 /// Maximum edge ID.724 725 /// Maximum edge ID.726 ///\sa id(Edge)727 int maxEdgeId() const { return 2*Parent::maxEdgeId(); }728 /// Maximum symmetric edge ID.729 730 /// Maximum symmetric edge ID.731 ///\sa id(SymEdge)732 int maxSymEdgeId() const { return Parent::maxEdgeId(); }733 734 735 Node tail(Edge e) const {736 return (e.id & 1) == 0 ?737 Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));738 }739 740 Node head(Edge e) const {741 return (e.id & 1) == 0 ?742 Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));743 }744 745 Node tail(SymEdge e) const {746 return Parent::tail(e);747 }748 749 Node head(SymEdge e) const {750 return Parent::head(e);751 }752 753 NodeIt& first(NodeIt& v) const {754 v=NodeIt(*this); return v; }755 EdgeIt& first(EdgeIt& e) const {756 e=EdgeIt(*this); return e; }757 SymEdgeIt& first(SymEdgeIt& e) const {758 e=SymEdgeIt(*this); return e; }759 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {760 e=OutEdgeIt(*this,v); return e; }761 InEdgeIt& first(InEdgeIt& e, const Node v) const {762 e=InEdgeIt(*this,v); return e; }763 764 /// Node ID.765 766 /// The ID of a valid Node is a nonnegative integer not greater than767 /// \ref maxNodeId(). The range of the ID's is not surely continuous768 /// and the greatest node ID can be actually less then \ref maxNodeId().769 ///770 /// The ID of the \ref INVALID node is -1.771 ///\return The ID of the node \c v.772 static int id(Node v) { return Parent::id(v); }773 /// Edge ID.774 775 /// The ID of a valid Edge is a nonnegative integer not greater than776 /// \ref maxEdgeId(). The range of the ID's is not surely continuous777 /// and the greatest edge ID can be actually less then \ref maxEdgeId().778 ///779 /// The ID of the \ref INVALID edge is -1.780 ///\return The ID of the edge \c e.781 static int id(Edge e) { return e.id; }782 783 /// The ID of a valid SymEdge is a nonnegative integer not greater than784 /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous785 /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().786 ///787 /// The ID of the \ref INVALID symmetric edge is -1.788 ///\return The ID of the edge \c e.789 static int id(SymEdge e) { return Parent::id(e); }790 791 /// Adds a new node to the graph.792 793 /// \warning It adds the new node to the front of the list.794 /// (i.e. the lastly added node becomes the first.)795 Node addNode() {796 return Parent::addNode();797 }798 799 SymEdge addEdge(Node u, Node v) {800 SymEdge se = Parent::addEdge(u, v);801 edge_maps.add(forward(se));802 edge_maps.add(backward(se));803 return se;804 }805 806 /// Finds an edge between two nodes.807 808 /// Finds an edge from node \c u to node \c v.809 ///810 /// If \c prev is \ref INVALID (this is the default value), then811 /// It finds the first edge from \c u to \c v. Otherwise it looks for812 /// the next edge from \c u to \c v after \c prev.813 /// \return The found edge or INVALID if there is no such an edge.814 Edge findEdge(Node u, Node v, Edge prev = INVALID)815 {816 if (prev == INVALID || id(prev) & 1 == 0) {817 SymEdge se = Parent::findEdge(u, v, SymEdge(prev));818 if (se != INVALID) return forward(se);819 } else {820 SymEdge se = Parent::findEdge(v, u, SymEdge(prev));821 if (se != INVALID) return backward(se);822 }823 return INVALID;824 }825 826 // /// Finds an symmetric edge between two nodes.827 828 // /// Finds an symmetric edge from node \c u to node \c v.829 // ///830 // /// If \c prev is \ref INVALID (this is the default value), then831 // /// It finds the first edge from \c u to \c v. Otherwise it looks for832 // /// the next edge from \c u to \c v after \c prev.833 // /// \return The found edge or INVALID if there is no such an edge.834 835 // SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)836 // {837 // if (prev == INVALID || id(prev) & 1 == 0) {838 // SymEdge se = Parent::findEdge(u, v, SymEdge(prev));839 // if (se != INVALID) return se;840 // } else {841 // SymEdge se = Parent::findEdge(v, u, SymEdge(prev));842 // if (se != INVALID) return se;843 // }844 // return INVALID;845 // }846 847 public:848 849 void erase(Node n) {850 for (OutEdgeIt it(*this, n); it != INVALID; ++it) {851 edge_maps.erase(it);852 edge_maps.erase(opposite(it));853 }854 Parent::erase(n);855 }856 857 void erase(SymEdge e) {858 edge_maps.erase(forward(e));859 edge_maps.erase(backward(e));860 Parent::erase(e);861 };862 863 void clear() {864 edge_maps.clear();865 Parent::clear();866 }867 868 static Edge opposite(Edge e) {869 return Edge(id(e) ^ 1);870 }871 872 static Edge forward(SymEdge e) {873 return Edge(id(e) << 1);874 }875 876 static Edge backward(SymEdge e) {877 return Edge((id(e) << 1) | 1);878 }879 880 486 }; 487 881 488 882 489 ///A graph class containing only nodes. -
src/hugo/map_bits.h
r909 r919 55 55 struct KeyInfo<Graph, typename Graph::SymEdgeIt> { 56 56 static int maxId(const Graph& graph) { 57 return graph.max SymEdgeId();57 return graph.maxEdgeId() >> 1; 58 58 } 59 static int id(const Graph& graph, const typename Graph:: SymEdge& edge) {60 return graph.id(edge) ;59 static int id(const Graph& graph, const typename Graph::Edge& edge) { 60 return graph.id(edge) >> 1; 61 61 } 62 62 }; -
src/hugo/map_defines.h
r909 r919 115 115 */ 116 116 #define CREATE_SYM_EDGE_MAP_REGISTRY \ 117 typedef MapRegistry<Graph, SymEdge, SymEdgeIt> SymEdgeMapRegistry; \ 117 typedef SymEdgeIt<Graph, Edge, EdgeIt> SymEdgeIt; \ 118 typedef MapRegistry<Graph, Edge, SymEdgeIt> SymEdgeMapRegistry; \ 118 119 mutable SymEdgeMapRegistry sym_edge_maps; 119 120 … … 127 128 #define CREATE_SYM_EDGE_MAP(DynMap) \ 128 129 template <typename Value> \ 129 class SymEdgeMap : public DynMap<SymEdgeMapRegistry, Value> { \130 public: \ 131 typedef DynMap<SymEdgeMapRegistry, Value> Parent; \130 class SymEdgeMap : public SymMap<DynMap, SymEdgeMapRegistry, Value> { \ 131 public: \ 132 typedef SymMap<DynMap, SymEdgeMapRegistry, Value> Parent; \ 132 133 \ 133 134 SymEdgeMap(const typename Parent::Graph& g) \ -
src/hugo/map_registry.h
r909 r919 253 253 * Notify all the registered maps about a Key added. 254 254 */ 255 void add( constKeyType& key) {255 void add(KeyType& key) { 256 256 typename Container::iterator it; 257 257 for (it = container.begin(); it != container.end(); ++it) { … … 263 263 * Notify all the registered maps about a Key erased. 264 264 */ 265 void erase( constKeyType& key) {265 void erase(KeyType& key) { 266 266 typename Container::iterator it; 267 267 for (it = container.begin(); it != container.end(); ++it) { -
src/hugo/smart_graph.h
r916 r919 28 28 29 29 #include <hugo/array_map.h> 30 #include <hugo/sym_map.h> 31 30 32 #include <hugo/map_registry.h> 31 33 … … 297 299 }; 298 300 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 check373 // 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 SymEdge487 (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 than574 /// \ref maxNodeId(). The range of the ID's is not surely continuous575 /// 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 than583 /// \ref maxEdgeId(). The range of the ID's is not surely continuous584 /// 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 than591 /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous592 /// 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), then618 /// It finds the first edge from \c u to \c v. Otherwise it looks for619 /// 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), then638 // /// It finds the first edge from \c u to \c v. Otherwise it looks for639 // /// 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 };674 301 ///Graph for bidirectional edges. 675 302 … … 692 319 //\sa SmartGraph. 693 320 694 /*class SymSmartGraph : public SmartGraph321 class SymSmartGraph : public SmartGraph 695 322 { 696 323 public: … … 727 354 728 355 729 };*/356 }; 730 357 731 358 /// @} -
src/test/Makefile.am
r909 r919 10 10 dijkstra_test \ 11 11 graph_test \ 12 sym_graph_test \13 12 graph_wrapper_test \ 14 13 kruskal_test \ … … 30 29 dijkstra_test_SOURCES = dijkstra_test.cc 31 30 graph_test_SOURCES = graph_test.cc 32 sym_graph_test_SOURCES = sym_graph_test.cc33 31 graph_wrapper_test_SOURCES = graph_wrapper_test.cc 34 32 kruskal_test_SOURCES = kruskal_test.cc -
src/test/graph_test.cc
r909 r919 64 64 checkGraphInEdgeList(G,n,3); 65 65 checkGraphOutEdgeList(G,n,3); 66 ++n; 66 67 } 67 68 } … … 82 83 83 84 //Compile SymSmartGraph 84 //template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);85 //template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);85 template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &); 86 template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &); 86 87 87 88 //Compile ListGraph … … 92 93 93 94 //Compile SymListGraph 94 //template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);95 //template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);96 //template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);95 template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &); 96 template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &); 97 template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &); 97 98 98 99 //Compile FullGraph … … 131 132 } 132 133 { 133 //SymSmartGraph G;134 //addPetersen(G);135 //checkPetersen(G);134 SymSmartGraph G; 135 addPetersen(G); 136 checkPetersen(G); 136 137 } 137 138 { 138 //SymListGraph G;139 //addPetersen(G);140 //checkPetersen(G);139 SymListGraph G; 140 addPetersen(G); 141 checkPetersen(G); 141 142 } 142 143 -
src/test/graph_test.h
r916 r919 299 299 for(int i=0;i<nn;i++) { 300 300 check(e!=INVALID,"Wrong OutEdge list linking."); 301 check(n==G.tail(e), "Wrong OutEdge list linking.");302 301 ++e; 303 302 } … … 312 311 for(int i=0;i<nn;i++) { 313 312 check(e!=INVALID,"Wrong InEdge list linking."); 314 check(n==G.head(e), "Wrong InEdge list linking.");315 313 ++e; 316 314 } -
src/test/test_tools.h
r909 r919 68 68 69 69 ///Adds a Petersen graph to \c G. 70 ///\return The nodes and edges ofthe generated graph.70 ///\return The nodes end edges og the generated graph. 71 71 72 72 template<typename Graph> … … 88 88 } 89 89 90 ///Structure returned by \ref addSymPetersen().91 90 92 ///Structure returned by \ref addSymPetersen().93 ///94 template<class Graph> struct SymPetStruct95 {96 ///Vector containing the outer nodes.97 std::vector<typename Graph::Node> outer;98 ///Vector containing the inner nodes.99 std::vector<typename Graph::Node> inner;100 ///Vector containing the edges of the inner circle.101 std::vector<typename Graph::SymEdge> incir;102 ///Vector containing the edges of the outer circle.103 std::vector<typename Graph::SymEdge> outcir;104 ///Vector containing the chord edges.105 std::vector<typename Graph::SymEdge> chords;106 };107 108 ///Adds a Petersen graph to the symmetric \c G.109 110 ///Adds a Petersen graph to the symmetric \c G.111 ///\return The nodes and edges of the generated graph.112 113 template<typename Graph>114 SymPetStruct<Graph> addSymPetersen(Graph &G,int num=5)115 {116 SymPetStruct<Graph> n;117 118 for(int i=0;i<num;i++) {119 n.outer.push_back(G.addNode());120 n.inner.push_back(G.addNode());121 }122 123 for(int i=0;i<num;i++) {124 n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));125 n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5]));126 n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5]));127 }128 return n;129 }130 91 131 92 #endif
Note: See TracChangeset
for help on using the changeset viewer.