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