diff -r 2c925c18d130 -r 79b68a337f9f src/lemon/graph_wrapper.h --- a/src/lemon/graph_wrapper.h Fri Apr 22 17:53:26 2005 +0000 +++ b/src/lemon/graph_wrapper.h Sat Apr 23 16:59:49 2005 +0000 @@ -28,6 +28,7 @@ #include #include #include +#include #include namespace lemon { @@ -151,11 +152,11 @@ typedef typename Parent::Node Node; typedef typename Parent::Edge Edge; - using Parent::first; + // using Parent::first; void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); } void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); } - using Parent::next; + // using Parent::next; void nextIn(Edge& i) const { Parent::nextOut(i); } void nextOut(Edge& i) const { Parent::nextIn(i); } @@ -565,91 +566,97 @@ } }; + template + class UndirGraphWrapperBase : + public UndirGraphExtender > { + public: + typedef _Graph Graph; + typedef UndirGraphExtender > Parent; + protected: + UndirGraphWrapperBase() : Parent() { } + public: + typedef typename Parent::UndirEdge UndirEdge; + typedef typename Parent::Edge Edge; + + /// \bug Why cant an edge say that it is forward or not??? + /// By this, a pointer to the graph have to be stored + /// The implementation + template + class EdgeMap { + protected: + const UndirGraphWrapperBase<_Graph>* g; + template friend class EdgeMap; + typename _Graph::template EdgeMap forward_map, backward_map; + public: + typedef T Value; + typedef Edge Key; + + EdgeMap(const UndirGraphWrapperBase<_Graph>& _g) : g(&_g), + forward_map(*(g->graph)), backward_map(*(g->graph)) { } - template - class UndirGraphWrapper : public GraphWrapper { - public: - typedef GraphWrapper Parent; - protected: - UndirGraphWrapper() : GraphWrapper() { } - - public: - typedef typename GraphWrapper::Node Node; - typedef typename GraphWrapper::NodeIt NodeIt; - typedef typename GraphWrapper::Edge Edge; - typedef typename GraphWrapper::EdgeIt EdgeIt; + EdgeMap(const UndirGraphWrapperBase<_Graph>& _g, T a) : g(&_g), + forward_map(*(g->graph), a), backward_map(*(g->graph), a) { } + + void set(Edge e, T a) { + if (g->forward(e)) + forward_map.set(e, a); + else + backward_map.set(e, a); + } - UndirGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } - - class OutEdgeIt { - friend class UndirGraphWrapper; - bool out_or_in; //true iff out - typename Graph::OutEdgeIt out; - typename Graph::InEdgeIt in; - public: - OutEdgeIt() { } - OutEdgeIt(const Invalid& i) : Edge(i) { } - OutEdgeIt(const UndirGraphWrapper& _G, const Node& _n) { - out_or_in=true; _G.graph->first(out, _n); - if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); } - } - operator Edge() const { - if (out_or_in) return Edge(out); else return Edge(in); + T operator[](Edge e) const { + if (g->forward(e)) + return forward_map[e]; + else + return backward_map[e]; } }; + + template + class UndirEdgeMap { + template friend class UndirEdgeMap; + typename _Graph::template EdgeMap map; + public: + typedef T Value; + typedef UndirEdge Key; + + UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g) : + map(*(g.graph)) { } - typedef OutEdgeIt InEdgeIt; + UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g, T a) : + map(*(g.graph), a) { } + + void set(UndirEdge e, T a) { + map.set(e, a); + } - using GraphWrapper::first; - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { - i=OutEdgeIt(*this, p); return i; + T operator[](UndirEdge e) const { + return map[e]; + } + }; + + }; + + /// \brief An undirected graph is made from a directed graph by a wrapper + /// + /// Undocumented, untested!!! + /// If somebody knows nice demo application, let's polulate it. + /// + /// \author Marton Makai + template + class UndirGraphWrapper : + public IterableUndirGraphExtender< + UndirGraphWrapperBase<_Graph> > { + public: + typedef _Graph Graph; + typedef IterableUndirGraphExtender< + UndirGraphWrapperBase<_Graph> > Parent; + protected: + UndirGraphWrapper() { } + public: + UndirGraphWrapper(_Graph& _graph) { + setGraph(_graph); } - - using GraphWrapper::next; - - OutEdgeIt& next(OutEdgeIt& e) const { - if (e.out_or_in) { - typename Graph::Node n=this->graph->source(e.out); - this->graph->next(e.out); - if (!this->graph->valid(e.out)) { - e.out_or_in=false; this->graph->first(e.in, n); } - } else { - this->graph->next(e.in); - } - return e; - } - - Node aNode(const OutEdgeIt& e) const { - if (e.out_or_in) return this->graph->source(e); else - return this->graph->target(e); } - Node bNode(const OutEdgeIt& e) const { - if (e.out_or_in) return this->graph->target(e); else - return this->graph->source(e); } - - // KEEP_MAPS(Parent, UndirGraphWrapper); - - }; - -// /// \brief An undirected graph template. -// /// -// ///\warning Graph wrappers are in even more experimental state than the other -// ///parts of the lib. Use them at your own risk. -// /// -// /// An undirected graph template. -// /// This class works as an undirected graph and a directed graph of -// /// class \c Graph is used for the physical storage. -// /// \ingroup graphs - template - class UndirGraph : public UndirGraphWrapper { - typedef UndirGraphWrapper Parent; - protected: - Graph gr; - public: - UndirGraph() : UndirGraphWrapper() { - Parent::setGraph(gr); - } - - // KEEP_MAPS(Parent, UndirGraph); };