Changeset 992:10d378f2821c in lemon0.x for src/lemon/graph_wrapper.h
 Timestamp:
 11/15/04 13:25:39 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1382
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/graph_wrapper.h
r987 r992 28 28 #include <lemon/invalid.h> 29 29 #include <lemon/maps.h> 30 #include <lemon/iterable_graph_extender.h> 30 31 #include <lemon/map_defines.h> 31 32 #include <iostream> … … 124 125 public: 125 126 GraphWrapperBase(Graph& _graph) : graph(&_graph) { } 126 GraphWrapperBase(const GraphWrapperBase<_Graph>& gw) : graph(gw.graph) { }127 // GraphWrapperBase(const GraphWrapperBase<_Graph>& gw) : graph(gw.graph) { } 127 128 128 129 typedef typename Graph::Node Node; … … 300 301 }; 301 302 302 303 304 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap> 305 class SubGraphWrapperBase : public GraphWrapperBase<_Graph> { 306 public: 307 typedef _Graph Graph; 308 typedef GraphWrapperBase<_Graph> Parent; 309 protected: 310 NodeFilterMap* node_filter_map; 311 EdgeFilterMap* edge_filter_map; 312 SubGraphWrapperBase() : Parent(), 313 node_filter_map(0), edge_filter_map(0) { } 314 315 void setNodeFilterMap(NodeFilterMap& _node_filter_map) { 316 node_filter_map=&_node_filter_map; 317 } 318 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { 319 edge_filter_map=&_edge_filter_map; 320 } 321 322 public: 323 // SubGraphWrapperBase(Graph& _graph, 324 // NodeFilterMap& _node_filter_map, 325 // EdgeFilterMap& _edge_filter_map) : 326 // Parent(&_graph), 327 // node_filter_map(&node_filter_map), 328 // edge_filter_map(&edge_filter_map) { } 329 330 typedef typename Parent::Node Node; 331 typedef typename Parent::Edge Edge; 332 333 void first(Node& i) const { 334 Parent::first(i); 335 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 336 } 337 void first(Edge& i) const { 338 Parent::first(i); 339 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 340 } 341 void firstIn(Edge& i, const Node& n) const { 342 Parent::firstIn(i, n); 343 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 344 } 345 void firstOut(Edge& i, const Node& n) const { 346 Parent::firstOut(i, n); 347 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 348 } 349 350 void next(Node& i) const { 351 Parent::next(i); 352 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 353 } 354 void next(Edge& i) const { 355 Parent::next(i); 356 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 357 } 358 void nextIn(Edge& i) const { 359 Parent::nextIn(i); 360 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 361 } 362 void nextOut(Edge& i) const { 363 Parent::nextOut(i); 364 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 365 } 366 367 /// This function hides \c n in the graph, i.e. the iteration 368 /// jumps over it. This is done by simply setting the value of \c n 369 /// to be false in the corresponding nodemap. 370 void hide(const Node& n) const { node_filter_map>set(n, false); } 371 372 /// This function hides \c e in the graph, i.e. the iteration 373 /// jumps over it. This is done by simply setting the value of \c e 374 /// to be false in the corresponding edgemap. 375 void hide(const Edge& e) const { edge_filter_map>set(e, false); } 376 377 /// The value of \c n is set to be true in the nodemap which stores 378 /// hide information. If \c n was hidden previuosly, then it is shown 379 /// again 380 void unHide(const Node& n) const { node_filter_map>set(n, true); } 381 382 /// The value of \c e is set to be true in the edgemap which stores 383 /// hide information. If \c e was hidden previuosly, then it is shown 384 /// again 385 void unHide(const Edge& e) const { edge_filter_map>set(e, true); } 386 387 /// Returns true if \c n is hidden. 388 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } 389 390 /// Returns true if \c n is hidden. 391 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 392 393 /// \warning This is a linear time operation and works only if s 394 /// \c Graph::NodeIt is defined. 395 /// \todo assign tags. 396 int nodeNum() const { 397 int i=0; 398 Node n; 399 for (first(n); n!=INVALID; next(n)) ++i; 400 return i; 401 } 402 403 /// \warning This is a linear time operation and works only if 404 /// \c Graph::EdgeIt is defined. 405 /// \todo assign tags. 406 int edgeNum() const { 407 int i=0; 408 Edge e; 409 for (first(e); e!=INVALID; next(e)) ++i; 410 return i; 411 } 412 413 414 }; 303 415 304 416 /*! \brief A graph wrapper for hiding nodes and edges from a graph. … … 348 460 \author Marton Makai 349 461 */ 350 template<typename Graph, typename NodeFilterMap,462 template<typename _Graph, typename NodeFilterMap, 351 463 typename EdgeFilterMap> 352 class SubGraphWrapper : public GraphWrapper<Graph> { 353 public: 354 typedef GraphWrapper<Graph> Parent; 464 class SubGraphWrapper : 465 public IterableGraphExtender< 466 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > { 467 public: 468 typedef _Graph Graph; 469 typedef IterableGraphExtender< 470 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; 355 471 protected: 356 NodeFilterMap* node_filter_map; 357 EdgeFilterMap* edge_filter_map; 358 359 SubGraphWrapper() : GraphWrapper<Graph>(), 360 node_filter_map(0), edge_filter_map(0) { } 361 void setNodeFilterMap(NodeFilterMap& _node_filter_map) { 362 node_filter_map=&_node_filter_map; 363 } 364 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { 365 edge_filter_map=&_edge_filter_map; 366 } 472 SubGraphWrapper() { } 473 public: 474 SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map, 475 EdgeFilterMap& _edge_filter_map) { 476 setGraph(_graph); 477 setNodeFilterMap(_node_filter_map); 478 setEdgeFilterMap(_edge_filter_map); 479 } 480 }; 481 482 // template<typename Graph, typename NodeFilterMap, 483 // typename EdgeFilterMap> 484 // class SubGraphWrapper : public GraphWrapper<Graph> { 485 // public: 486 // typedef GraphWrapper<Graph> Parent; 487 // protected: 488 // NodeFilterMap* node_filter_map; 489 // EdgeFilterMap* edge_filter_map; 490 491 // SubGraphWrapper() : GraphWrapper<Graph>(), 492 // node_filter_map(0), edge_filter_map(0) { } 493 // void setNodeFilterMap(NodeFilterMap& _node_filter_map) { 494 // node_filter_map=&_node_filter_map; 495 // } 496 // void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { 497 // edge_filter_map=&_edge_filter_map; 498 // } 367 499 368 public:369 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,370 EdgeFilterMap& _edge_filter_map) :371 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),372 edge_filter_map(&_edge_filter_map) { }373 374 typedef typename GraphWrapper<Graph>::Node Node;375 class NodeIt : public Node {376 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;377 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;378 public:379 NodeIt() { }380 NodeIt(Invalid i) : Node(i) { }381 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :382 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {383 while (*static_cast<Node*>(this)!=INVALID &&384 !(*(gw>node_filter_map))[*this])385 *(static_cast<Node*>(this))=386 ++(typename Graph::NodeIt(*(gw>graph), *this));387 }388 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,389 const Node& n) :390 Node(n), gw(&_gw) { }391 NodeIt& operator++() {392 *(static_cast<Node*>(this))=393 ++(typename Graph::NodeIt(*(gw>graph), *this));394 while (*static_cast<Node*>(this)!=INVALID &&395 !(*(gw>node_filter_map))[*this])396 *(static_cast<Node*>(this))=397 ++(typename Graph::NodeIt(*(gw>graph), *this));398 return *this;399 }400 };401 typedef typename GraphWrapper<Graph>::Edge Edge;402 class OutEdgeIt : public Edge {403 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;404 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;405 public:406 OutEdgeIt() { }407 OutEdgeIt(Invalid i) : Edge(i) { }408 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :409 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {410 while (*static_cast<Edge*>(this)!=INVALID &&411 !(*(gw>edge_filter_map))[*this])412 *(static_cast<Edge*>(this))=413 ++(typename Graph::OutEdgeIt(*(gw>graph), *this));414 }415 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,416 const Edge& e) :417 Edge(e), gw(&_gw) { }418 OutEdgeIt& operator++() {419 *(static_cast<Edge*>(this))=420 ++(typename Graph::OutEdgeIt(*(gw>graph), *this));421 while (*static_cast<Edge*>(this)!=INVALID &&422 !(*(gw>edge_filter_map))[*this])423 *(static_cast<Edge*>(this))=424 ++(typename Graph::OutEdgeIt(*(gw>graph), *this));425 return *this;426 }427 };428 class InEdgeIt : public Edge {429 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;430 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;431 public:432 InEdgeIt() { }433 // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }434 InEdgeIt(Invalid i) : Edge(i) { }435 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :436 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {437 while (*static_cast<Edge*>(this)!=INVALID &&438 !(*(gw>edge_filter_map))[*this])439 *(static_cast<Edge*>(this))=440 ++(typename Graph::InEdgeIt(*(gw>graph), *this));441 }442 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,443 const Edge& e) :444 Edge(e), gw(&_gw) { }445 InEdgeIt& operator++() {446 *(static_cast<Edge*>(this))=447 ++(typename Graph::InEdgeIt(*(gw>graph), *this));448 while (*static_cast<Edge*>(this)!=INVALID &&449 !(*(gw>edge_filter_map))[*this])450 *(static_cast<Edge*>(this))=451 ++(typename Graph::InEdgeIt(*(gw>graph), *this));452 return *this;453 }454 };455 class EdgeIt : public Edge {456 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;457 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;458 public:459 EdgeIt() { }460 EdgeIt(Invalid i) : Edge(i) { }461 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :462 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {463 while (*static_cast<Edge*>(this)!=INVALID &&464 !(*(gw>edge_filter_map))[*this])465 *(static_cast<Edge*>(this))=466 ++(typename Graph::EdgeIt(*(gw>graph), *this));467 }468 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,469 const Edge& e) :470 Edge(e), gw(&_gw) { }471 EdgeIt& operator++() {472 *(static_cast<Edge*>(this))=473 ++(typename Graph::EdgeIt(*(gw>graph), *this));474 while (*static_cast<Edge*>(this)!=INVALID &&475 !(*(gw>edge_filter_map))[*this])476 *(static_cast<Edge*>(this))=477 ++(typename Graph::EdgeIt(*(gw>graph), *this));478 return *this;479 }480 };481 482 NodeIt& first(NodeIt& i) const {483 i=NodeIt(*this); return i;484 }485 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {486 i=OutEdgeIt(*this, p); return i;487 }488 InEdgeIt& first(InEdgeIt& i, const Node& p) const {489 i=InEdgeIt(*this, p); return i;490 }491 EdgeIt& first(EdgeIt& i) const {492 i=EdgeIt(*this); return i;493 }500 // public: 501 // SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 502 // EdgeFilterMap& _edge_filter_map) : 503 // GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 504 // edge_filter_map(&_edge_filter_map) { } 505 506 // typedef typename GraphWrapper<Graph>::Node Node; 507 // class NodeIt : public Node { 508 // const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 509 // friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 510 // public: 511 // NodeIt() { } 512 // NodeIt(Invalid i) : Node(i) { } 513 // NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 514 // Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { 515 // while (*static_cast<Node*>(this)!=INVALID && 516 // !(*(gw>node_filter_map))[*this]) 517 // *(static_cast<Node*>(this))= 518 // ++(typename Graph::NodeIt(*(gw>graph), *this)); 519 // } 520 // NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 521 // const Node& n) : 522 // Node(n), gw(&_gw) { } 523 // NodeIt& operator++() { 524 // *(static_cast<Node*>(this))= 525 // ++(typename Graph::NodeIt(*(gw>graph), *this)); 526 // while (*static_cast<Node*>(this)!=INVALID && 527 // !(*(gw>node_filter_map))[*this]) 528 // *(static_cast<Node*>(this))= 529 // ++(typename Graph::NodeIt(*(gw>graph), *this)); 530 // return *this; 531 // } 532 // }; 533 // typedef typename GraphWrapper<Graph>::Edge Edge; 534 // class OutEdgeIt : public Edge { 535 // const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 536 // friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 537 // public: 538 // OutEdgeIt() { } 539 // OutEdgeIt(Invalid i) : Edge(i) { } 540 // OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 541 // Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { 542 // while (*static_cast<Edge*>(this)!=INVALID && 543 // !(*(gw>edge_filter_map))[*this]) 544 // *(static_cast<Edge*>(this))= 545 // ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 546 // } 547 // OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 548 // const Edge& e) : 549 // Edge(e), gw(&_gw) { } 550 // OutEdgeIt& operator++() { 551 // *(static_cast<Edge*>(this))= 552 // ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 553 // while (*static_cast<Edge*>(this)!=INVALID && 554 // !(*(gw>edge_filter_map))[*this]) 555 // *(static_cast<Edge*>(this))= 556 // ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 557 // return *this; 558 // } 559 // }; 560 // class InEdgeIt : public Edge { 561 // const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 562 // friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 563 // public: 564 // InEdgeIt() { } 565 // // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } 566 // InEdgeIt(Invalid i) : Edge(i) { } 567 // InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 568 // Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { 569 // while (*static_cast<Edge*>(this)!=INVALID && 570 // !(*(gw>edge_filter_map))[*this]) 571 // *(static_cast<Edge*>(this))= 572 // ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 573 // } 574 // InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 575 // const Edge& e) : 576 // Edge(e), gw(&_gw) { } 577 // InEdgeIt& operator++() { 578 // *(static_cast<Edge*>(this))= 579 // ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 580 // while (*static_cast<Edge*>(this)!=INVALID && 581 // !(*(gw>edge_filter_map))[*this]) 582 // *(static_cast<Edge*>(this))= 583 // ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 584 // return *this; 585 // } 586 // }; 587 // class EdgeIt : public Edge { 588 // const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 589 // friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 590 // public: 591 // EdgeIt() { } 592 // EdgeIt(Invalid i) : Edge(i) { } 593 // EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 594 // Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { 595 // while (*static_cast<Edge*>(this)!=INVALID && 596 // !(*(gw>edge_filter_map))[*this]) 597 // *(static_cast<Edge*>(this))= 598 // ++(typename Graph::EdgeIt(*(gw>graph), *this)); 599 // } 600 // EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 601 // const Edge& e) : 602 // Edge(e), gw(&_gw) { } 603 // EdgeIt& operator++() { 604 // *(static_cast<Edge*>(this))= 605 // ++(typename Graph::EdgeIt(*(gw>graph), *this)); 606 // while (*static_cast<Edge*>(this)!=INVALID && 607 // !(*(gw>edge_filter_map))[*this]) 608 // *(static_cast<Edge*>(this))= 609 // ++(typename Graph::EdgeIt(*(gw>graph), *this)); 610 // return *this; 611 // } 612 // }; 613 614 // NodeIt& first(NodeIt& i) const { 615 // i=NodeIt(*this); return i; 616 // } 617 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 618 // i=OutEdgeIt(*this, p); return i; 619 // } 620 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { 621 // i=InEdgeIt(*this, p); return i; 622 // } 623 // EdgeIt& first(EdgeIt& i) const { 624 // i=EdgeIt(*this); return i; 625 // } 494 626 495 /// This function hides \c n in the graph, i.e. the iteration496 /// jumps over it. This is done by simply setting the value of \c n497 /// to be false in the corresponding nodemap.498 void hide(const Node& n) const { node_filter_map>set(n, false); }499 500 /// This function hides \c e in the graph, i.e. the iteration501 /// jumps over it. This is done by simply setting the value of \c e502 /// to be false in the corresponding edgemap.503 void hide(const Edge& e) const { edge_filter_map>set(e, false); }504 505 /// The value of \c n is set to be true in the nodemap which stores506 /// hide information. If \c n was hidden previuosly, then it is shown507 /// again508 void unHide(const Node& n) const { node_filter_map>set(n, true); }509 510 /// The value of \c e is set to be true in the edgemap which stores511 /// hide information. If \c e was hidden previuosly, then it is shown512 /// again513 void unHide(const Edge& e) const { edge_filter_map>set(e, true); }514 515 /// Returns true if \c n is hidden.516 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }517 518 /// Returns true if \c n is hidden.519 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }520 521 /// \warning This is a linear time operation and works only if522 /// \c Graph::NodeIt is defined.523 int nodeNum() const {524 int i=0;525 for (NodeIt n(*this); n!=INVALID; ++n) ++i;526 return i;527 }528 529 /// \warning This is a linear time operation and works only if530 /// \c Graph::EdgeIt is defined.531 int edgeNum() const {532 int i=0;533 for (EdgeIt e(*this); e!=INVALID; ++e) ++i;534 return i;535 }536 537 // KEEP_MAPS(Parent, SubGraphWrapper);538 };627 // /// This function hides \c n in the graph, i.e. the iteration 628 // /// jumps over it. This is done by simply setting the value of \c n 629 // /// to be false in the corresponding nodemap. 630 // void hide(const Node& n) const { node_filter_map>set(n, false); } 631 632 // /// This function hides \c e in the graph, i.e. the iteration 633 // /// jumps over it. This is done by simply setting the value of \c e 634 // /// to be false in the corresponding edgemap. 635 // void hide(const Edge& e) const { edge_filter_map>set(e, false); } 636 637 // /// The value of \c n is set to be true in the nodemap which stores 638 // /// hide information. If \c n was hidden previuosly, then it is shown 639 // /// again 640 // void unHide(const Node& n) const { node_filter_map>set(n, true); } 641 642 // /// The value of \c e is set to be true in the edgemap which stores 643 // /// hide information. If \c e was hidden previuosly, then it is shown 644 // /// again 645 // void unHide(const Edge& e) const { edge_filter_map>set(e, true); } 646 647 // /// Returns true if \c n is hidden. 648 // bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } 649 650 // /// Returns true if \c n is hidden. 651 // bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 652 653 // /// \warning This is a linear time operation and works only if 654 // /// \c Graph::NodeIt is defined. 655 // int nodeNum() const { 656 // int i=0; 657 // for (NodeIt n(*this); n!=INVALID; ++n) ++i; 658 // return i; 659 // } 660 661 // /// \warning This is a linear time operation and works only if 662 // /// \c Graph::EdgeIt is defined. 663 // int edgeNum() const { 664 // int i=0; 665 // for (EdgeIt e(*this); e!=INVALID; ++e) ++i; 666 // return i; 667 // } 668 669 // // KEEP_MAPS(Parent, SubGraphWrapper); 670 // }; 539 671 540 672 … … 800 932 }; 801 933 934 935 template <typename _Graph, 936 typename ForwardFilterMap, typename BackwardFilterMap> 937 class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> { 938 public: 939 typedef _Graph Graph; 940 typedef GraphWrapperBase<_Graph> Parent; 941 protected: 942 ForwardFilterMap* forward_filter; 943 BackwardFilterMap* backward_filter; 944 SubBidirGraphWrapperBase() : Parent(), 945 forward_filter(0), backward_filter(0) { } 946 947 void setForwardFilterMap(ForwardFilterMap& _forward_filter) { 948 forward_filter=&_forward_filter; 949 } 950 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) { 951 backward_filter=&_backward_filter; 952 } 953 954 public: 955 // SubGraphWrapperBase(Graph& _graph, 956 // NodeFilterMap& _node_filter_map, 957 // EdgeFilterMap& _edge_filter_map) : 958 // Parent(&_graph), 959 // node_filter_map(&node_filter_map), 960 // edge_filter_map(&edge_filter_map) { } 961 962 typedef typename Parent::Node Node; 963 typedef typename _Graph::Edge GraphEdge; 964 template <typename T> class EdgeMap; 965 /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from 966 /// _Graph::Edge. It contains an extra bool flag which is true 967 /// if and only if the 968 /// edge is the backward version of the original edge. 969 class Edge : public _Graph::Edge { 970 friend class SubBidirGraphWrapperBase< 971 Graph, ForwardFilterMap, BackwardFilterMap>; 972 template<typename T> friend class EdgeMap; 973 protected: 974 bool backward; //true, iff backward 975 public: 976 Edge() { } 977 /// \todo =false is needed, or causes problems? 978 /// If \c _backward is false, then we get an edge corresponding to the 979 /// original one, otherwise its oppositely directed pair is obtained. 980 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : 981 _Graph::Edge(e), backward(_backward) { } 982 Edge(Invalid i) : _Graph::Edge(i), backward(true) { } 983 bool operator==(const Edge& v) const { 984 return (this>backward==v.backward && 985 static_cast<typename _Graph::Edge>(*this)== 986 static_cast<typename _Graph::Edge>(v)); 987 } 988 bool operator!=(const Edge& v) const { 989 return (this>backward!=v.backward  990 static_cast<typename _Graph::Edge>(*this)!= 991 static_cast<typename _Graph::Edge>(v)); 992 } 993 }; 994 995 void first(Node& i) const { 996 Parent::first(i); 997 } 998 999 void first(Edge& i) const { 1000 Parent::first(i); 1001 i.backward=false; 1002 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1003 !(*forward_filter)[i]) Parent::next(i); 1004 if (*static_cast<GraphEdge*>(&i)==INVALID) { 1005 Parent::first(i); 1006 i.backward=true; 1007 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1008 !(*backward_filter)[i]) Parent::next(i); 1009 } 1010 } 1011 1012 void firstIn(Edge& i, const Node& n) const { 1013 Parent::firstIn(i, n); 1014 i.backward=false; 1015 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1016 !(*forward_filter)[i]) Parent::nextOut(i); 1017 if (*static_cast<GraphEdge*>(&i)==INVALID) { 1018 Parent::firstOut(i, n); 1019 i.backward=true; 1020 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1021 !(*backward_filter)[i]) Parent::nextOut(i); 1022 } 1023 } 1024 1025 void firstOut(Edge& i, const Node& n) const { 1026 Parent::firstOut(i, n); 1027 i.backward=false; 1028 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1029 !(*forward_filter)[i]) Parent::nextOut(i); 1030 if (*static_cast<GraphEdge*>(&i)==INVALID) { 1031 Parent::firstIn(i, n); 1032 i.backward=true; 1033 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1034 !(*backward_filter)[i]) Parent::nextIn(i); 1035 } 1036 } 1037 1038 void next(Node& i) const { 1039 Parent::next(i); 1040 } 1041 1042 void next(Edge& i) const { 1043 if (!(i.backward)) { 1044 Parent::next(i); 1045 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1046 !(*forward_filter)[i]) Parent::next(i); 1047 if (*static_cast<GraphEdge*>(&i)==INVALID) { 1048 Parent::first(i); 1049 i.backward=true; 1050 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1051 !(*backward_filter)[i]) Parent::next(i); 1052 } 1053 } else { 1054 Parent::next(i); 1055 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1056 !(*backward_filter)[i]) Parent::next(i); 1057 } 1058 } 1059 1060 void nextIn(Edge& i) const { 1061 if (!(i.backward)) { 1062 Node n=Parent::target(i); 1063 Parent::nextIn(i); 1064 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1065 !(*forward_filter)[i]) Parent::nextIn(i); 1066 if (*static_cast<GraphEdge*>(&i)==INVALID) { 1067 Parent::firstOut(i, n); 1068 i.backward=true; 1069 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1070 !(*backward_filter)[i]) Parent::nextOut(i); 1071 } 1072 } else { 1073 Parent::nextOut(i); 1074 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1075 !(*backward_filter)[i]) Parent::nextOut(i); 1076 } 1077 } 1078 1079 void nextOut(Edge& i) const { 1080 if (!(i.backward)) { 1081 Node n=Parent::source(i); 1082 Parent::nextOut(i); 1083 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1084 !(*forward_filter)[i]) Parent::nextOut(i); 1085 if (*static_cast<GraphEdge*>(&i)==INVALID) { 1086 Parent::firstIn(i, n); 1087 i.backward=true; 1088 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1089 !(*backward_filter)[i]) Parent::nextIn(i); 1090 } 1091 } else { 1092 Parent::nextIn(i); 1093 while (*static_cast<GraphEdge*>(&i)!=INVALID && 1094 !(*backward_filter)[i]) Parent::nextIn(i); 1095 } 1096 } 1097 1098 Node source(Edge e) const { 1099 return ((!e.backward) ? this>graph>source(e) : this>graph>target(e)); } 1100 Node target(Edge e) const { 1101 return ((!e.backward) ? this>graph>target(e) : this>graph>source(e)); } 1102 1103 /// Gives back the opposite edge. 1104 Edge opposite(const Edge& e) const { 1105 Edge f=e; 1106 f.backward=!f.backward; 1107 return f; 1108 } 1109 1110 /// \warning This is a linear time operation and works only if 1111 /// \c Graph::EdgeIt is defined. 1112 /// \todo hmm 1113 int edgeNum() const { 1114 int i=0; 1115 Edge e; 1116 for (first(e); e!=INVALID; next(e)) ++i; 1117 return i; 1118 } 1119 1120 bool forward(const Edge& e) const { return !e.backward; } 1121 bool backward(const Edge& e) const { return e.backward; } 1122 1123 template <typename T> 1124 /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two 1125 /// _Graph::EdgeMap one for the forward edges and 1126 /// one for the backward edges. 1127 class EdgeMap { 1128 template <typename TT> friend class EdgeMap; 1129 typename _Graph::template EdgeMap<T> forward_map, backward_map; 1130 public: 1131 typedef T Value; 1132 typedef Edge Key; 1133 1134 EdgeMap(const SubBidirGraphWrapperBase<_Graph, 1135 ForwardFilterMap, BackwardFilterMap>& g) : 1136 forward_map(*(g.graph)), backward_map(*(g.graph)) { } 1137 1138 EdgeMap(const SubBidirGraphWrapperBase<_Graph, 1139 ForwardFilterMap, BackwardFilterMap>& g, T a) : 1140 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } 1141 1142 // template <typename TT> 1143 // EdgeMap(const EdgeMap<TT>& copy) 1144 // : forward_map(copy.forward_map), backward_map(copy.backward_map) {} 1145 1146 // template <typename TT> 1147 // EdgeMap& operator=(const EdgeMap<TT>& copy) { 1148 // forward_map = copy.forward_map; 1149 // backward_map = copy.backward_map; 1150 // return *this; 1151 // } 1152 1153 void set(Edge e, T a) { 1154 if (!e.backward) 1155 forward_map.set(e, a); 1156 else 1157 backward_map.set(e, a); 1158 } 1159 1160 // typename _Graph::template EdgeMap<T>::ConstReference 1161 // operator[](Edge e) const { 1162 // if (!e.backward) 1163 // return forward_map[e]; 1164 // else 1165 // return backward_map[e]; 1166 // } 1167 1168 // typename _Graph::template EdgeMap<T>::Reference 1169 T operator[](Edge e) { 1170 if (!e.backward) 1171 return forward_map[e]; 1172 else 1173 return backward_map[e]; 1174 } 1175 1176 void update() { 1177 forward_map.update(); 1178 backward_map.update(); 1179 } 1180 }; 1181 1182 }; 802 1183 803 1184 … … 839 1220 /// above mentioned graph structure without its physical storage, 840 1221 /// that is the whole stuff is stored in constant memory. 841 template<typename Graph,1222 template<typename _Graph, 842 1223 typename ForwardFilterMap, typename BackwardFilterMap> 843 class SubBidirGraphWrapper : public GraphWrapper<Graph> { 844 public: 845 typedef GraphWrapper<Graph> Parent; 1224 class SubBidirGraphWrapper : 1225 public IterableGraphExtender< 1226 SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > { 1227 public: 1228 typedef _Graph Graph; 1229 typedef IterableGraphExtender< 1230 SubBidirGraphWrapperBase< 1231 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent; 846 1232 protected: 847 ForwardFilterMap* forward_filter; 848 BackwardFilterMap* backward_filter; 849 850 SubBidirGraphWrapper() : GraphWrapper<Graph>() { } 851 void setForwardFilterMap(ForwardFilterMap& _forward_filter) { 852 forward_filter=&_forward_filter; 853 } 854 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) { 855 backward_filter=&_backward_filter; 856 } 857 858 public: 859 860 SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter, 861 BackwardFilterMap& _backward_filter) : 862 GraphWrapper<Graph>(_graph), 863 forward_filter(&_forward_filter), backward_filter(&_backward_filter) { } 864 SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph, 865 ForwardFilterMap, BackwardFilterMap>& gw) : 866 Parent(gw), 867 forward_filter(gw.forward_filter), 868 backward_filter(gw.backward_filter) { } 869 870 class Edge; 871 class OutEdgeIt; 872 friend class Edge; 873 friend class OutEdgeIt; 874 875 template<typename T> class EdgeMap; 876 877 typedef typename GraphWrapper<Graph>::Node Node; 878 879 typedef typename Graph::Edge GraphEdge; 880 /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from 881 /// Graph::Edge. It contains an extra bool flag which is true 882 /// if and only if the 883 /// edge is the backward version of the original edge. 884 class Edge : public Graph::Edge { 885 friend class SubBidirGraphWrapper<Graph, 886 ForwardFilterMap, BackwardFilterMap>; 887 template<typename T> friend class EdgeMap; 888 protected: 889 bool backward; //true, iff backward 890 public: 891 Edge() { } 892 /// \todo =false is needed, or causes problems? 893 /// If \c _backward is false, then we get an edge corresponding to the 894 /// original one, otherwise its oppositely directed pair is obtained. 895 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : 896 Graph::Edge(e), backward(_backward) { } 897 Edge(Invalid i) : Graph::Edge(i), backward(true) { } 898 bool operator==(const Edge& v) const { 899 return (this>backward==v.backward && 900 static_cast<typename Graph::Edge>(*this)== 901 static_cast<typename Graph::Edge>(v)); 902 } 903 bool operator!=(const Edge& v) const { 904 return (this>backward!=v.backward  905 static_cast<typename Graph::Edge>(*this)!= 906 static_cast<typename Graph::Edge>(v)); 907 } 908 }; 909 910 class OutEdgeIt : public Edge { 911 friend class SubBidirGraphWrapper<Graph, 912 ForwardFilterMap, BackwardFilterMap>; 913 protected: 914 const SubBidirGraphWrapper<Graph, 915 ForwardFilterMap, BackwardFilterMap>* gw; 916 public: 917 OutEdgeIt() { } 918 OutEdgeIt(Invalid i) : Edge(i) { } 919 OutEdgeIt(const SubBidirGraphWrapper<Graph, 920 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 921 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 922 while (*static_cast<GraphEdge*>(this)!=INVALID && 923 !(*(gw>forward_filter))[*this]) 924 *(static_cast<GraphEdge*>(this))= 925 ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 926 if (*static_cast<GraphEdge*>(this)==INVALID) { 927 *static_cast<Edge*>(this)= 928 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true); 929 while (*static_cast<GraphEdge*>(this)!=INVALID && 930 !(*(gw>backward_filter))[*this]) 931 *(static_cast<GraphEdge*>(this))= 932 ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 933 } 934 } 935 OutEdgeIt(const SubBidirGraphWrapper<Graph, 936 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 937 Edge(e), gw(&_gw) { } 938 OutEdgeIt& operator++() { 939 if (!this>backward) { 940 Node n=gw>source(*this); 941 *(static_cast<GraphEdge*>(this))= 942 ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 943 while (*static_cast<GraphEdge*>(this)!=INVALID && 944 !(*(gw>forward_filter))[*this]) 945 *(static_cast<GraphEdge*>(this))= 946 ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 947 if (*static_cast<GraphEdge*>(this)==INVALID) { 948 *static_cast<Edge*>(this)= 949 Edge(typename Graph::InEdgeIt(*(gw>graph), n), true); 950 while (*static_cast<GraphEdge*>(this)!=INVALID && 951 !(*(gw>backward_filter))[*this]) 952 *(static_cast<GraphEdge*>(this))= 953 ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 954 } 955 } else { 956 *(static_cast<GraphEdge*>(this))= 957 ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 958 while (*static_cast<GraphEdge*>(this)!=INVALID && 959 !(*(gw>backward_filter))[*this]) 960 *(static_cast<GraphEdge*>(this))= 961 ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 962 } 963 return *this; 964 } 965 }; 966 967 class InEdgeIt : public Edge { 968 friend class SubBidirGraphWrapper<Graph, 969 ForwardFilterMap, BackwardFilterMap>; 970 protected: 971 const SubBidirGraphWrapper<Graph, 972 ForwardFilterMap, BackwardFilterMap>* gw; 973 public: 974 InEdgeIt() { } 975 InEdgeIt(Invalid i) : Edge(i) { } 976 InEdgeIt(const SubBidirGraphWrapper<Graph, 977 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 978 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 979 while (*static_cast<GraphEdge*>(this)!=INVALID && 980 !(*(gw>forward_filter))[*this]) 981 *(static_cast<GraphEdge*>(this))= 982 ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 983 if (*static_cast<GraphEdge*>(this)==INVALID) { 984 *static_cast<Edge*>(this)= 985 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true); 986 while (*static_cast<GraphEdge*>(this)!=INVALID && 987 !(*(gw>backward_filter))[*this]) 988 *(static_cast<GraphEdge*>(this))= 989 ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 990 } 991 } 992 InEdgeIt(const SubBidirGraphWrapper<Graph, 993 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 994 Edge(e), gw(&_gw) { } 995 InEdgeIt& operator++() { 996 if (!this>backward) { 997 Node n=gw>source(*this); 998 *(static_cast<GraphEdge*>(this))= 999 ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 1000 while (*static_cast<GraphEdge*>(this)!=INVALID && 1001 !(*(gw>forward_filter))[*this]) 1002 *(static_cast<GraphEdge*>(this))= 1003 ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 1004 if (*static_cast<GraphEdge*>(this)==INVALID) { 1005 *static_cast<Edge*>(this)= 1006 Edge(typename Graph::OutEdgeIt(*(gw>graph), n), true); 1007 while (*static_cast<GraphEdge*>(this)!=INVALID && 1008 !(*(gw>backward_filter))[*this]) 1009 *(static_cast<GraphEdge*>(this))= 1010 ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 1011 } 1012 } else { 1013 *(static_cast<GraphEdge*>(this))= 1014 ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 1015 while (*static_cast<GraphEdge*>(this)!=INVALID && 1016 !(*(gw>backward_filter))[*this]) 1017 *(static_cast<GraphEdge*>(this))= 1018 ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 1019 } 1020 return *this; 1021 } 1022 }; 1023 1024 class EdgeIt : public Edge { 1025 friend class SubBidirGraphWrapper<Graph, 1026 ForwardFilterMap, BackwardFilterMap>; 1027 protected: 1028 const SubBidirGraphWrapper<Graph, 1029 ForwardFilterMap, BackwardFilterMap>* gw; 1030 public: 1031 EdgeIt() { } 1032 EdgeIt(Invalid i) : Edge(i) { } 1033 EdgeIt(const SubBidirGraphWrapper<Graph, 1034 ForwardFilterMap, BackwardFilterMap>& _gw) : 1035 Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) { 1036 while (*static_cast<GraphEdge*>(this)!=INVALID && 1037 !(*(gw>forward_filter))[*this]) 1038 *(static_cast<GraphEdge*>(this))= 1039 ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1040 if (*static_cast<GraphEdge*>(this)==INVALID) { 1041 *static_cast<Edge*>(this)= 1042 Edge(typename Graph::EdgeIt(*(_gw.graph)), true); 1043 while (*static_cast<GraphEdge*>(this)!=INVALID && 1044 !(*(gw>backward_filter))[*this]) 1045 *(static_cast<GraphEdge*>(this))= 1046 ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1047 } 1048 } 1049 EdgeIt(const SubBidirGraphWrapper<Graph, 1050 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 1051 Edge(e), gw(&_gw) { } 1052 EdgeIt& operator++() { 1053 if (!this>backward) { 1054 *(static_cast<GraphEdge*>(this))= 1055 ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1056 while (*static_cast<GraphEdge*>(this)!=INVALID && 1057 !(*(gw>forward_filter))[*this]) 1058 *(static_cast<GraphEdge*>(this))= 1059 ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1060 if (*static_cast<GraphEdge*>(this)==INVALID) { 1061 *static_cast<Edge*>(this)= 1062 Edge(typename Graph::EdgeIt(*(gw>graph)), true); 1063 while (*static_cast<GraphEdge*>(this)!=INVALID && 1064 !(*(gw>backward_filter))[*this]) 1065 *(static_cast<GraphEdge*>(this))= 1066 ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1067 } 1068 } else { 1069 *(static_cast<GraphEdge*>(this))= 1070 ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1071 while (*static_cast<GraphEdge*>(this)!=INVALID && 1072 !(*(gw>backward_filter))[*this]) 1073 *(static_cast<GraphEdge*>(this))= 1074 ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1075 } 1076 return *this; 1077 } 1078 }; 1079 1080 // using GraphWrapper<Graph>::first; 1081 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 1082 // i=OutEdgeIt(*this, p); return i; 1233 SubBidirGraphWrapper() { } 1234 public: 1235 SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter, 1236 BackwardFilterMap& _backward_filter) { 1237 setGraph(_graph); 1238 setForwardFilterMap(_forward_filter); 1239 setBackwardFilterMap(_backward_filter); 1240 } 1241 }; 1242 1243 // template<typename Graph, 1244 // typename ForwardFilterMap, typename BackwardFilterMap> 1245 // class SubBidirGraphWrapper : public GraphWrapper<Graph> { 1246 // public: 1247 // typedef GraphWrapper<Graph> Parent; 1248 // protected: 1249 // ForwardFilterMap* forward_filter; 1250 // BackwardFilterMap* backward_filter; 1251 1252 // SubBidirGraphWrapper() : GraphWrapper<Graph>() { } 1253 // void setForwardFilterMap(ForwardFilterMap& _forward_filter) { 1254 // forward_filter=&_forward_filter; 1083 1255 // } 1084 // InEdgeIt& first(InEdgeIt& i, const Node& p) const {1085 // i=InEdgeIt(*this, p); return i;1256 // void setBackwardFilterMap(BackwardFilterMap& _backward_filter) { 1257 // backward_filter=&_backward_filter; 1086 1258 // } 1087 // EdgeIt& first(EdgeIt& i) const { 1088 // i=EdgeIt(*this); return i; 1259 1260 // public: 1261 1262 // SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter, 1263 // BackwardFilterMap& _backward_filter) : 1264 // GraphWrapper<Graph>(_graph), 1265 // forward_filter(&_forward_filter), backward_filter(&_backward_filter) { } 1266 // SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph, 1267 // ForwardFilterMap, BackwardFilterMap>& gw) : 1268 // Parent(gw), 1269 // forward_filter(gw.forward_filter), 1270 // backward_filter(gw.backward_filter) { } 1271 1272 // class Edge; 1273 // class OutEdgeIt; 1274 // friend class Edge; 1275 // friend class OutEdgeIt; 1276 1277 // template<typename T> class EdgeMap; 1278 1279 // typedef typename GraphWrapper<Graph>::Node Node; 1280 1281 // typedef typename Graph::Edge GraphEdge; 1282 // /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from 1283 // /// Graph::Edge. It contains an extra bool flag which is true 1284 // /// if and only if the 1285 // /// edge is the backward version of the original edge. 1286 // class Edge : public Graph::Edge { 1287 // friend class SubBidirGraphWrapper<Graph, 1288 // ForwardFilterMap, BackwardFilterMap>; 1289 // template<typename T> friend class EdgeMap; 1290 // protected: 1291 // bool backward; //true, iff backward 1292 // public: 1293 // Edge() { } 1294 // /// \todo =false is needed, or causes problems? 1295 // /// If \c _backward is false, then we get an edge corresponding to the 1296 // /// original one, otherwise its oppositely directed pair is obtained. 1297 // Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : 1298 // Graph::Edge(e), backward(_backward) { } 1299 // Edge(Invalid i) : Graph::Edge(i), backward(true) { } 1300 // bool operator==(const Edge& v) const { 1301 // return (this>backward==v.backward && 1302 // static_cast<typename Graph::Edge>(*this)== 1303 // static_cast<typename Graph::Edge>(v)); 1304 // } 1305 // bool operator!=(const Edge& v) const { 1306 // return (this>backward!=v.backward  1307 // static_cast<typename Graph::Edge>(*this)!= 1308 // static_cast<typename Graph::Edge>(v)); 1309 // } 1310 // }; 1311 1312 // class OutEdgeIt : public Edge { 1313 // friend class SubBidirGraphWrapper<Graph, 1314 // ForwardFilterMap, BackwardFilterMap>; 1315 // protected: 1316 // const SubBidirGraphWrapper<Graph, 1317 // ForwardFilterMap, BackwardFilterMap>* gw; 1318 // public: 1319 // OutEdgeIt() { } 1320 // OutEdgeIt(Invalid i) : Edge(i) { } 1321 // OutEdgeIt(const SubBidirGraphWrapper<Graph, 1322 // ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 1323 // Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 1324 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1325 // !(*(gw>forward_filter))[*this]) 1326 // *(static_cast<GraphEdge*>(this))= 1327 // ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 1328 // if (*static_cast<GraphEdge*>(this)==INVALID) { 1329 // *static_cast<Edge*>(this)= 1330 // Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true); 1331 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1332 // !(*(gw>backward_filter))[*this]) 1333 // *(static_cast<GraphEdge*>(this))= 1334 // ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 1335 // } 1336 // } 1337 // OutEdgeIt(const SubBidirGraphWrapper<Graph, 1338 // ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 1339 // Edge(e), gw(&_gw) { } 1340 // OutEdgeIt& operator++() { 1341 // if (!this>backward) { 1342 // Node n=gw>source(*this); 1343 // *(static_cast<GraphEdge*>(this))= 1344 // ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 1345 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1346 // !(*(gw>forward_filter))[*this]) 1347 // *(static_cast<GraphEdge*>(this))= 1348 // ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 1349 // if (*static_cast<GraphEdge*>(this)==INVALID) { 1350 // *static_cast<Edge*>(this)= 1351 // Edge(typename Graph::InEdgeIt(*(gw>graph), n), true); 1352 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1353 // !(*(gw>backward_filter))[*this]) 1354 // *(static_cast<GraphEdge*>(this))= 1355 // ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 1356 // } 1357 // } else { 1358 // *(static_cast<GraphEdge*>(this))= 1359 // ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 1360 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1361 // !(*(gw>backward_filter))[*this]) 1362 // *(static_cast<GraphEdge*>(this))= 1363 // ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 1364 // } 1365 // return *this; 1366 // } 1367 // }; 1368 1369 // class InEdgeIt : public Edge { 1370 // friend class SubBidirGraphWrapper<Graph, 1371 // ForwardFilterMap, BackwardFilterMap>; 1372 // protected: 1373 // const SubBidirGraphWrapper<Graph, 1374 // ForwardFilterMap, BackwardFilterMap>* gw; 1375 // public: 1376 // InEdgeIt() { } 1377 // InEdgeIt(Invalid i) : Edge(i) { } 1378 // InEdgeIt(const SubBidirGraphWrapper<Graph, 1379 // ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 1380 // Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 1381 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1382 // !(*(gw>forward_filter))[*this]) 1383 // *(static_cast<GraphEdge*>(this))= 1384 // ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 1385 // if (*static_cast<GraphEdge*>(this)==INVALID) { 1386 // *static_cast<Edge*>(this)= 1387 // Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true); 1388 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1389 // !(*(gw>backward_filter))[*this]) 1390 // *(static_cast<GraphEdge*>(this))= 1391 // ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 1392 // } 1393 // } 1394 // InEdgeIt(const SubBidirGraphWrapper<Graph, 1395 // ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 1396 // Edge(e), gw(&_gw) { } 1397 // InEdgeIt& operator++() { 1398 // if (!this>backward) { 1399 // Node n=gw>source(*this); 1400 // *(static_cast<GraphEdge*>(this))= 1401 // ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 1402 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1403 // !(*(gw>forward_filter))[*this]) 1404 // *(static_cast<GraphEdge*>(this))= 1405 // ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 1406 // if (*static_cast<GraphEdge*>(this)==INVALID) { 1407 // *static_cast<Edge*>(this)= 1408 // Edge(typename Graph::OutEdgeIt(*(gw>graph), n), true); 1409 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1410 // !(*(gw>backward_filter))[*this]) 1411 // *(static_cast<GraphEdge*>(this))= 1412 // ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 1413 // } 1414 // } else { 1415 // *(static_cast<GraphEdge*>(this))= 1416 // ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 1417 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1418 // !(*(gw>backward_filter))[*this]) 1419 // *(static_cast<GraphEdge*>(this))= 1420 // ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 1421 // } 1422 // return *this; 1423 // } 1424 // }; 1425 1426 // class EdgeIt : public Edge { 1427 // friend class SubBidirGraphWrapper<Graph, 1428 // ForwardFilterMap, BackwardFilterMap>; 1429 // protected: 1430 // const SubBidirGraphWrapper<Graph, 1431 // ForwardFilterMap, BackwardFilterMap>* gw; 1432 // public: 1433 // EdgeIt() { } 1434 // EdgeIt(Invalid i) : Edge(i) { } 1435 // EdgeIt(const SubBidirGraphWrapper<Graph, 1436 // ForwardFilterMap, BackwardFilterMap>& _gw) : 1437 // Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) { 1438 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1439 // !(*(gw>forward_filter))[*this]) 1440 // *(static_cast<GraphEdge*>(this))= 1441 // ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1442 // if (*static_cast<GraphEdge*>(this)==INVALID) { 1443 // *static_cast<Edge*>(this)= 1444 // Edge(typename Graph::EdgeIt(*(_gw.graph)), true); 1445 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1446 // !(*(gw>backward_filter))[*this]) 1447 // *(static_cast<GraphEdge*>(this))= 1448 // ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1449 // } 1450 // } 1451 // EdgeIt(const SubBidirGraphWrapper<Graph, 1452 // ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 1453 // Edge(e), gw(&_gw) { } 1454 // EdgeIt& operator++() { 1455 // if (!this>backward) { 1456 // *(static_cast<GraphEdge*>(this))= 1457 // ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1458 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1459 // !(*(gw>forward_filter))[*this]) 1460 // *(static_cast<GraphEdge*>(this))= 1461 // ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1462 // if (*static_cast<GraphEdge*>(this)==INVALID) { 1463 // *static_cast<Edge*>(this)= 1464 // Edge(typename Graph::EdgeIt(*(gw>graph)), true); 1465 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1466 // !(*(gw>backward_filter))[*this]) 1467 // *(static_cast<GraphEdge*>(this))= 1468 // ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1469 // } 1470 // } else { 1471 // *(static_cast<GraphEdge*>(this))= 1472 // ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1473 // while (*static_cast<GraphEdge*>(this)!=INVALID && 1474 // !(*(gw>backward_filter))[*this]) 1475 // *(static_cast<GraphEdge*>(this))= 1476 // ++(typename Graph::EdgeIt(*(gw>graph), *this)); 1477 // } 1478 // return *this; 1479 // } 1480 // }; 1481 1482 // // using GraphWrapper<Graph>::first; 1483 // // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 1484 // // i=OutEdgeIt(*this, p); return i; 1485 // // } 1486 // // InEdgeIt& first(InEdgeIt& i, const Node& p) const { 1487 // // i=InEdgeIt(*this, p); return i; 1488 // // } 1489 // // EdgeIt& first(EdgeIt& i) const { 1490 // // i=EdgeIt(*this); return i; 1491 // // } 1492 1493 1494 // Node source(Edge e) const { 1495 // return ((!e.backward) ? this>graph>source(e) : this>graph>target(e)); } 1496 // Node target(Edge e) const { 1497 // return ((!e.backward) ? this>graph>target(e) : this>graph>source(e)); } 1498 1499 // /// Gives back the opposite edge. 1500 // Edge opposite(const Edge& e) const { 1501 // Edge f=e; 1502 // f.backward=!f.backward; 1503 // return f; 1089 1504 // } 1090 1091 1092 Node source(Edge e) const { 1093 return ((!e.backward) ? this>graph>source(e) : this>graph>target(e)); } 1094 Node target(Edge e) const { 1095 return ((!e.backward) ? this>graph>target(e) : this>graph>source(e)); } 1096 1097 /// Gives back the opposite edge. 1098 Edge opposite(const Edge& e) const { 1099 Edge f=e; 1100 f.backward=!f.backward; 1101 return f; 1102 } 1103 1104 /// \warning This is a linear time operation and works only if 1105 /// \c Graph::EdgeIt is defined. 1106 int edgeNum() const { 1107 int i=0; 1108 for (EdgeIt e(*this); e!=INVALID; ++e) ++i; 1109 return i; 1110 } 1111 1112 bool forward(const Edge& e) const { return !e.backward; } 1113 bool backward(const Edge& e) const { return e.backward; } 1114 1115 1116 template <typename T> 1117 /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two 1118 /// Graph::EdgeMap one for the forward edges and 1119 /// one for the backward edges. 1120 class EdgeMap { 1121 template <typename TT> friend class EdgeMap; 1122 typename Graph::template EdgeMap<T> forward_map, backward_map; 1123 public: 1124 typedef T Value; 1125 typedef Edge Key; 1126 1127 EdgeMap(const SubBidirGraphWrapper<Graph, 1128 ForwardFilterMap, BackwardFilterMap>& g) : 1129 forward_map(*(g.graph)), backward_map(*(g.graph)) { } 1130 1131 EdgeMap(const SubBidirGraphWrapper<Graph, 1132 ForwardFilterMap, BackwardFilterMap>& g, T a) : 1133 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } 1134 1135 template <typename TT> 1136 EdgeMap(const EdgeMap<TT>& copy) 1137 : forward_map(copy.forward_map), backward_map(copy.backward_map) {} 1138 1139 template <typename TT> 1140 EdgeMap& operator=(const EdgeMap<TT>& copy) { 1141 forward_map = copy.forward_map; 1142 backward_map = copy.backward_map; 1143 return *this; 1144 } 1505 1506 // /// \warning This is a linear time operation and works only if 1507 // /// \c Graph::EdgeIt is defined. 1508 // int edgeNum() const { 1509 // int i=0; 1510 // for (EdgeIt e(*this); e!=INVALID; ++e) ++i; 1511 // return i; 1512 // } 1513 1514 // bool forward(const Edge& e) const { return !e.backward; } 1515 // bool backward(const Edge& e) const { return e.backward; } 1516 1517 1518 // template <typename T> 1519 // /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two 1520 // /// Graph::EdgeMap one for the forward edges and 1521 // /// one for the backward edges. 1522 // class EdgeMap { 1523 // template <typename TT> friend class EdgeMap; 1524 // typename Graph::template EdgeMap<T> forward_map, backward_map; 1525 // public: 1526 // typedef T Value; 1527 // typedef Edge Key; 1528 1529 // EdgeMap(const SubBidirGraphWrapper<Graph, 1530 // ForwardFilterMap, BackwardFilterMap>& g) : 1531 // forward_map(*(g.graph)), backward_map(*(g.graph)) { } 1532 1533 // EdgeMap(const SubBidirGraphWrapper<Graph, 1534 // ForwardFilterMap, BackwardFilterMap>& g, T a) : 1535 // forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } 1536 1537 // template <typename TT> 1538 // EdgeMap(const EdgeMap<TT>& copy) 1539 // : forward_map(copy.forward_map), backward_map(copy.backward_map) {} 1540 1541 // template <typename TT> 1542 // EdgeMap& operator=(const EdgeMap<TT>& copy) { 1543 // forward_map = copy.forward_map; 1544 // backward_map = copy.backward_map; 1545 // return *this; 1546 // } 1145 1547 1146 void set(Edge e, T a) {1147 if (!e.backward)1148 forward_map.set(e, a);1149 else1150 backward_map.set(e, a);1151 }1152 1153 typename Graph::template EdgeMap<T>::ConstReference1154 operator[](Edge e) const {1155 if (!e.backward)1156 return forward_map[e];1157 else1158 return backward_map[e];1159 }1160 1161 typename Graph::template EdgeMap<T>::Reference1162 operator[](Edge e) {1163 if (!e.backward)1164 return forward_map[e];1165 else1166 return backward_map[e];1167 }1168 1169 void update() {1170 forward_map.update();1171 backward_map.update();1172 }1173 };1174 1175 1176 // KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);1177 1178 };1548 // void set(Edge e, T a) { 1549 // if (!e.backward) 1550 // forward_map.set(e, a); 1551 // else 1552 // backward_map.set(e, a); 1553 // } 1554 1555 // typename Graph::template EdgeMap<T>::ConstReference 1556 // operator[](Edge e) const { 1557 // if (!e.backward) 1558 // return forward_map[e]; 1559 // else 1560 // return backward_map[e]; 1561 // } 1562 1563 // typename Graph::template EdgeMap<T>::Reference 1564 // operator[](Edge e) { 1565 // if (!e.backward) 1566 // return forward_map[e]; 1567 // else 1568 // return backward_map[e]; 1569 // } 1570 1571 // void update() { 1572 // forward_map.update(); 1573 // backward_map.update(); 1574 // } 1575 // }; 1576 1577 1578 // // KEEP_NODE_MAP(Parent, SubBidirGraphWrapper); 1579 1580 // }; 1179 1581 1180 1582
Note: See TracChangeset
for help on using the changeset viewer.