Changeset 1383:79b68a337f9f in lemon0.x for src/lemon
 Timestamp:
 04/23/05 18:59:49 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1836
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/graph_wrapper.h
r1359 r1383 29 29 #include <lemon/maps.h> 30 30 #include <lemon/bits/iterable_graph_extender.h> 31 #include <lemon/bits/undir_graph_extender.h> 31 32 #include <iostream> 32 33 … … 152 153 typedef typename Parent::Edge Edge; 153 154 154 using Parent::first;155 // using Parent::first; 155 156 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); } 156 157 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); } 157 158 158 using Parent::next;159 // using Parent::next; 159 160 void nextIn(Edge& i) const { Parent::nextOut(i); } 160 161 void nextOut(Edge& i) const { Parent::nextIn(i); } … … 566 567 }; 567 568 568 569 template<typename Graph> 570 class UndirGraphWrapper : public GraphWrapper<Graph> { 571 public: 572 typedef GraphWrapper<Graph> Parent; 573 protected: 574 UndirGraphWrapper() : GraphWrapper<Graph>() { } 569 template <typename _Graph> 570 class UndirGraphWrapperBase : 571 public UndirGraphExtender<GraphWrapperBase<_Graph> > { 572 public: 573 typedef _Graph Graph; 574 typedef UndirGraphExtender<GraphWrapperBase<_Graph> > Parent; 575 protected: 576 UndirGraphWrapperBase() : Parent() { } 577 public: 578 typedef typename Parent::UndirEdge UndirEdge; 579 typedef typename Parent::Edge Edge; 575 580 576 public: 577 typedef typename GraphWrapper<Graph>::Node Node; 578 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 579 typedef typename GraphWrapper<Graph>::Edge Edge; 580 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt; 581 582 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 583 584 class OutEdgeIt { 585 friend class UndirGraphWrapper<Graph>; 586 bool out_or_in; //true iff out 587 typename Graph::OutEdgeIt out; 588 typename Graph::InEdgeIt in; 581 /// \bug Why cant an edge say that it is forward or not??? 582 /// By this, a pointer to the graph have to be stored 583 /// The implementation 584 template <typename T> 585 class EdgeMap { 586 protected: 587 const UndirGraphWrapperBase<_Graph>* g; 588 template <typename TT> friend class EdgeMap; 589 typename _Graph::template EdgeMap<T> forward_map, backward_map; 589 590 public: 590 OutEdgeIt() { } 591 OutEdgeIt(const Invalid& i) : Edge(i) { } 592 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) { 593 out_or_in=true; _G.graph>first(out, _n); 594 if (!(_G.graph>valid(out))) { out_or_in=false; _G.graph>first(in, _n); } 595 } 596 operator Edge() const { 597 if (out_or_in) return Edge(out); else return Edge(in); 591 typedef T Value; 592 typedef Edge Key; 593 594 EdgeMap(const UndirGraphWrapperBase<_Graph>& _g) : g(&_g), 595 forward_map(*(g>graph)), backward_map(*(g>graph)) { } 596 597 EdgeMap(const UndirGraphWrapperBase<_Graph>& _g, T a) : g(&_g), 598 forward_map(*(g>graph), a), backward_map(*(g>graph), a) { } 599 600 void set(Edge e, T a) { 601 if (g>forward(e)) 602 forward_map.set(e, a); 603 else 604 backward_map.set(e, a); 605 } 606 607 T operator[](Edge e) const { 608 if (g>forward(e)) 609 return forward_map[e]; 610 else 611 return backward_map[e]; 598 612 } 599 613 }; 600 601 typedef OutEdgeIt InEdgeIt; 602 603 using GraphWrapper<Graph>::first; 604 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 605 i=OutEdgeIt(*this, p); return i; 606 } 607 608 using GraphWrapper<Graph>::next; 609 610 OutEdgeIt& next(OutEdgeIt& e) const { 611 if (e.out_or_in) { 612 typename Graph::Node n=this>graph>source(e.out); 613 this>graph>next(e.out); 614 if (!this>graph>valid(e.out)) { 615 e.out_or_in=false; this>graph>first(e.in, n); } 616 } else { 617 this>graph>next(e.in); 618 } 619 return e; 620 } 621 622 Node aNode(const OutEdgeIt& e) const { 623 if (e.out_or_in) return this>graph>source(e); else 624 return this>graph>target(e); } 625 Node bNode(const OutEdgeIt& e) const { 626 if (e.out_or_in) return this>graph>target(e); else 627 return this>graph>source(e); } 628 629 // KEEP_MAPS(Parent, UndirGraphWrapper); 630 631 }; 632 633 // /// \brief An undirected graph template. 634 // /// 635 // ///\warning Graph wrappers are in even more experimental state than the other 636 // ///parts of the lib. Use them at your own risk. 637 // /// 638 // /// An undirected graph template. 639 // /// This class works as an undirected graph and a directed graph of 640 // /// class \c Graph is used for the physical storage. 641 // /// \ingroup graphs 642 template<typename Graph> 643 class UndirGraph : public UndirGraphWrapper<Graph> { 644 typedef UndirGraphWrapper<Graph> Parent; 645 protected: 646 Graph gr; 647 public: 648 UndirGraph() : UndirGraphWrapper<Graph>() { 649 Parent::setGraph(gr); 650 } 651 652 // KEEP_MAPS(Parent, UndirGraph); 614 615 template <typename T> 616 class UndirEdgeMap { 617 template <typename TT> friend class UndirEdgeMap; 618 typename _Graph::template EdgeMap<T> map; 619 public: 620 typedef T Value; 621 typedef UndirEdge Key; 622 623 UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g) : 624 map(*(g.graph)) { } 625 626 UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g, T a) : 627 map(*(g.graph), a) { } 628 629 void set(UndirEdge e, T a) { 630 map.set(e, a); 631 } 632 633 T operator[](UndirEdge e) const { 634 return map[e]; 635 } 636 }; 637 638 }; 639 640 /// \brief An undirected graph is made from a directed graph by a wrapper 641 /// 642 /// Undocumented, untested!!! 643 /// If somebody knows nice demo application, let's polulate it. 644 /// 645 /// \author Marton Makai 646 template<typename _Graph> 647 class UndirGraphWrapper : 648 public IterableUndirGraphExtender< 649 UndirGraphWrapperBase<_Graph> > { 650 public: 651 typedef _Graph Graph; 652 typedef IterableUndirGraphExtender< 653 UndirGraphWrapperBase<_Graph> > Parent; 654 protected: 655 UndirGraphWrapper() { } 656 public: 657 UndirGraphWrapper(_Graph& _graph) { 658 setGraph(_graph); 659 } 653 660 }; 654 661
Note: See TracChangeset
for help on using the changeset viewer.