1.1 --- a/src/lemon/graph_wrapper.h Fri Apr 22 17:53:26 2005 +0000
1.2 +++ b/src/lemon/graph_wrapper.h Sat Apr 23 16:59:49 2005 +0000
1.3 @@ -28,6 +28,7 @@
1.4 #include <lemon/invalid.h>
1.5 #include <lemon/maps.h>
1.6 #include <lemon/bits/iterable_graph_extender.h>
1.7 +#include <lemon/bits/undir_graph_extender.h>
1.8 #include <iostream>
1.9
1.10 namespace lemon {
1.11 @@ -151,11 +152,11 @@
1.12 typedef typename Parent::Node Node;
1.13 typedef typename Parent::Edge Edge;
1.14
1.15 - using Parent::first;
1.16 + // using Parent::first;
1.17 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
1.18 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
1.19
1.20 - using Parent::next;
1.21 + // using Parent::next;
1.22 void nextIn(Edge& i) const { Parent::nextOut(i); }
1.23 void nextOut(Edge& i) const { Parent::nextIn(i); }
1.24
1.25 @@ -565,91 +566,97 @@
1.26 }
1.27 };
1.28
1.29 + template <typename _Graph>
1.30 + class UndirGraphWrapperBase :
1.31 + public UndirGraphExtender<GraphWrapperBase<_Graph> > {
1.32 + public:
1.33 + typedef _Graph Graph;
1.34 + typedef UndirGraphExtender<GraphWrapperBase<_Graph> > Parent;
1.35 + protected:
1.36 + UndirGraphWrapperBase() : Parent() { }
1.37 + public:
1.38 + typedef typename Parent::UndirEdge UndirEdge;
1.39 + typedef typename Parent::Edge Edge;
1.40 +
1.41 + /// \bug Why cant an edge say that it is forward or not???
1.42 + /// By this, a pointer to the graph have to be stored
1.43 + /// The implementation
1.44 + template <typename T>
1.45 + class EdgeMap {
1.46 + protected:
1.47 + const UndirGraphWrapperBase<_Graph>* g;
1.48 + template <typename TT> friend class EdgeMap;
1.49 + typename _Graph::template EdgeMap<T> forward_map, backward_map;
1.50 + public:
1.51 + typedef T Value;
1.52 + typedef Edge Key;
1.53 +
1.54 + EdgeMap(const UndirGraphWrapperBase<_Graph>& _g) : g(&_g),
1.55 + forward_map(*(g->graph)), backward_map(*(g->graph)) { }
1.56
1.57 - template<typename Graph>
1.58 - class UndirGraphWrapper : public GraphWrapper<Graph> {
1.59 - public:
1.60 - typedef GraphWrapper<Graph> Parent;
1.61 - protected:
1.62 - UndirGraphWrapper() : GraphWrapper<Graph>() { }
1.63 -
1.64 - public:
1.65 - typedef typename GraphWrapper<Graph>::Node Node;
1.66 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.67 - typedef typename GraphWrapper<Graph>::Edge Edge;
1.68 - typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
1.69 + EdgeMap(const UndirGraphWrapperBase<_Graph>& _g, T a) : g(&_g),
1.70 + forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
1.71 +
1.72 + void set(Edge e, T a) {
1.73 + if (g->forward(e))
1.74 + forward_map.set(e, a);
1.75 + else
1.76 + backward_map.set(e, a);
1.77 + }
1.78
1.79 - UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
1.80 -
1.81 - class OutEdgeIt {
1.82 - friend class UndirGraphWrapper<Graph>;
1.83 - bool out_or_in; //true iff out
1.84 - typename Graph::OutEdgeIt out;
1.85 - typename Graph::InEdgeIt in;
1.86 - public:
1.87 - OutEdgeIt() { }
1.88 - OutEdgeIt(const Invalid& i) : Edge(i) { }
1.89 - OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
1.90 - out_or_in=true; _G.graph->first(out, _n);
1.91 - if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
1.92 - }
1.93 - operator Edge() const {
1.94 - if (out_or_in) return Edge(out); else return Edge(in);
1.95 + T operator[](Edge e) const {
1.96 + if (g->forward(e))
1.97 + return forward_map[e];
1.98 + else
1.99 + return backward_map[e];
1.100 }
1.101 };
1.102 +
1.103 + template <typename T>
1.104 + class UndirEdgeMap {
1.105 + template <typename TT> friend class UndirEdgeMap;
1.106 + typename _Graph::template EdgeMap<T> map;
1.107 + public:
1.108 + typedef T Value;
1.109 + typedef UndirEdge Key;
1.110 +
1.111 + UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g) :
1.112 + map(*(g.graph)) { }
1.113
1.114 - typedef OutEdgeIt InEdgeIt;
1.115 + UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g, T a) :
1.116 + map(*(g.graph), a) { }
1.117 +
1.118 + void set(UndirEdge e, T a) {
1.119 + map.set(e, a);
1.120 + }
1.121
1.122 - using GraphWrapper<Graph>::first;
1.123 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.124 - i=OutEdgeIt(*this, p); return i;
1.125 + T operator[](UndirEdge e) const {
1.126 + return map[e];
1.127 + }
1.128 + };
1.129 +
1.130 + };
1.131 +
1.132 + /// \brief An undirected graph is made from a directed graph by a wrapper
1.133 + ///
1.134 + /// Undocumented, untested!!!
1.135 + /// If somebody knows nice demo application, let's polulate it.
1.136 + ///
1.137 + /// \author Marton Makai
1.138 + template<typename _Graph>
1.139 + class UndirGraphWrapper :
1.140 + public IterableUndirGraphExtender<
1.141 + UndirGraphWrapperBase<_Graph> > {
1.142 + public:
1.143 + typedef _Graph Graph;
1.144 + typedef IterableUndirGraphExtender<
1.145 + UndirGraphWrapperBase<_Graph> > Parent;
1.146 + protected:
1.147 + UndirGraphWrapper() { }
1.148 + public:
1.149 + UndirGraphWrapper(_Graph& _graph) {
1.150 + setGraph(_graph);
1.151 }
1.152 -
1.153 - using GraphWrapper<Graph>::next;
1.154 -
1.155 - OutEdgeIt& next(OutEdgeIt& e) const {
1.156 - if (e.out_or_in) {
1.157 - typename Graph::Node n=this->graph->source(e.out);
1.158 - this->graph->next(e.out);
1.159 - if (!this->graph->valid(e.out)) {
1.160 - e.out_or_in=false; this->graph->first(e.in, n); }
1.161 - } else {
1.162 - this->graph->next(e.in);
1.163 - }
1.164 - return e;
1.165 - }
1.166 -
1.167 - Node aNode(const OutEdgeIt& e) const {
1.168 - if (e.out_or_in) return this->graph->source(e); else
1.169 - return this->graph->target(e); }
1.170 - Node bNode(const OutEdgeIt& e) const {
1.171 - if (e.out_or_in) return this->graph->target(e); else
1.172 - return this->graph->source(e); }
1.173 -
1.174 - // KEEP_MAPS(Parent, UndirGraphWrapper);
1.175 -
1.176 - };
1.177 -
1.178 -// /// \brief An undirected graph template.
1.179 -// ///
1.180 -// ///\warning Graph wrappers are in even more experimental state than the other
1.181 -// ///parts of the lib. Use them at your own risk.
1.182 -// ///
1.183 -// /// An undirected graph template.
1.184 -// /// This class works as an undirected graph and a directed graph of
1.185 -// /// class \c Graph is used for the physical storage.
1.186 -// /// \ingroup graphs
1.187 - template<typename Graph>
1.188 - class UndirGraph : public UndirGraphWrapper<Graph> {
1.189 - typedef UndirGraphWrapper<Graph> Parent;
1.190 - protected:
1.191 - Graph gr;
1.192 - public:
1.193 - UndirGraph() : UndirGraphWrapper<Graph>() {
1.194 - Parent::setGraph(gr);
1.195 - }
1.196 -
1.197 - // KEEP_MAPS(Parent, UndirGraph);
1.198 };
1.199
1.200