1.1 --- a/src/include/invalid.h Fri Apr 23 21:26:32 2004 +0000
1.2 +++ b/src/include/invalid.h Sat Apr 24 12:44:41 2004 +0000
1.3 @@ -27,7 +27,7 @@
1.4 //const Invalid &INVALID = *(Invalid *)0;
1.5 const Invalid INVALID = Invalid();
1.6
1.7 -};
1.8 +} //namespace hugo
1.9
1.10 #endif
1.11
2.1 --- a/src/include/maps.h Fri Apr 23 21:26:32 2004 +0000
2.2 +++ b/src/include/maps.h Sat Apr 24 12:44:41 2004 +0000
2.3 @@ -92,13 +92,16 @@
2.4 StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}
2.5
2.6 template<typename T1, typename Comp1>
2.7 - StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) { FIXME; }
2.8 + StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) {
2.9 + //FIXME;
2.10 + }
2.11
2.12 ReferenceType operator[](const Key &k) {
2.13 return insert(PairType(k,v)).first -> second;
2.14 }
2.15 ConstReferenceType operator[](const Key &k) const {
2.16 - typename parent::iterator i = lower_bound(__k);
2.17 +//marci jav typename parent::iterator i = lower_bound(__k);
2.18 + typename parent::iterator i = lower_bound(k);
2.19 if (i == end() || key_comp()(k, (*i).first))
2.20 return v;
2.21 return (*i).second;
3.1 --- a/src/work/jacint/preflow.h Fri Apr 23 21:26:32 2004 +0000
3.2 +++ b/src/work/jacint/preflow.h Sat Apr 24 12:44:41 2004 +0000
3.3 @@ -52,8 +52,8 @@
3.4 namespace hugo {
3.5
3.6 template <typename Graph, typename T,
3.7 - typename CapMap=typename Graph::EdgeMap<T>,
3.8 - typename FlowMap=typename Graph::EdgeMap<T> >
3.9 + typename CapMap=typename Graph::template EdgeMap<T>,
3.10 + typename FlowMap=typename Graph::template EdgeMap<T> >
3.11 class Preflow {
3.12
3.13 typedef typename Graph::Node Node;
3.14 @@ -99,16 +99,16 @@
3.15 int k=n-2; //bound on the highest level under n containing a node
3.16 int b=k; //bound on the highest level under n of an active node
3.17
3.18 - typename Graph::NodeMap<int> level(G,n);
3.19 - typename Graph::NodeMap<T> excess(G);
3.20 + typename Graph::template NodeMap<int> level(G,n);
3.21 + typename Graph::template NodeMap<T> excess(G);
3.22
3.23 std::vector<Node> active(n-1,INVALID);
3.24 - typename Graph::NodeMap<Node> next(G,INVALID);
3.25 + typename Graph::template NodeMap<Node> next(G,INVALID);
3.26 //Stack of the active nodes in level i < n.
3.27 //We use it in both phases.
3.28
3.29 - typename Graph::NodeMap<Node> left(G,INVALID);
3.30 - typename Graph::NodeMap<Node> right(G,INVALID);
3.31 + typename Graph::template NodeMap<Node> left(G,INVALID);
3.32 + typename Graph::template NodeMap<Node> right(G,INVALID);
3.33 std::vector<Node> level_list(n,INVALID);
3.34 /*
3.35 List of the nodes in level i<n.
4.1 --- a/src/work/list_graph.h Fri Apr 23 21:26:32 2004 +0000
4.2 +++ b/src/work/list_graph.h Sat Apr 24 12:44:41 2004 +0000
4.3 @@ -29,7 +29,7 @@
4.4 class SymEdgeIt;
4.5 template <typename T> class NodeMap;
4.6 template <typename T> class EdgeMap;
4.7 - private:
4.8 +// private:
4.9 template <typename T> friend class NodeMap;
4.10 template <typename T> friend class EdgeMap;
4.11
4.12 @@ -75,6 +75,7 @@
4.13 void update(T a) { container.resize(G.edge_id, a); }
4.14 };
4.15
4.16 + private:
4.17 int node_id;
4.18 int edge_id;
4.19 int _node_num;
5.1 --- a/src/work/makefile Fri Apr 23 21:26:32 2004 +0000
5.2 +++ b/src/work/makefile Sat Apr 24 12:44:41 2004 +0000
5.3 @@ -1,10 +1,11 @@
5.4 INCLUDEDIRS ?= -I../include -I. -I./{marci,jacint,alpar,klao,akos}
5.5 -CXXFLAGS = -g -O -Wall $(INCLUDEDIRS) -ansi -pedantic
5.6 +CXXFLAGS = -g -O2 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
5.7
5.8 BINARIES ?= bin_heap_demo
5.9
5.10 # Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam
5.11 # ismert rendszeren :-) (Misi)
5.12 +#CXX := $(shell type -p g++-3.4 || type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
5.13 CXX := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
5.14 CC := $(CXX)
5.15
6.1 --- a/src/work/marci/bfs_iterator.h Fri Apr 23 21:26:32 2004 +0000
6.2 +++ b/src/work/marci/bfs_iterator.h Sat Apr 24 12:44:41 2004 +0000
6.3 @@ -146,7 +146,7 @@
6.4 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
6.5 bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
6.6 Node aNode() const { return actual_node; /*FIXME*/}
6.7 - Node bNode() const { return G.bNode(actual_edge); }
6.8 + Node bNode() const { return graph->bNode(actual_edge); }
6.9 const ReachedMap& getReachedMap() const { return reached; }
6.10 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
6.11 };
7.1 --- a/src/work/marci/bfsit_vs_byhand.cc Fri Apr 23 21:26:32 2004 +0000
7.2 +++ b/src/work/marci/bfsit_vs_byhand.cc Sat Apr 24 12:44:41 2004 +0000
7.3 @@ -3,7 +3,7 @@
7.4 #include <fstream>
7.5
7.6 #include <list_graph.h>
7.7 -#include <smart_graph.h>
7.8 +//#include <smart_graph.h>
7.9 #include <dimacs.h>
7.10 #include <time_measure.h>
7.11 #include <for_each_macros.h>
8.1 --- a/src/work/marci/bipartite_graph_wrapper_test.cc Fri Apr 23 21:26:32 2004 +0000
8.2 +++ b/src/work/marci/bipartite_graph_wrapper_test.cc Sat Apr 24 12:44:41 2004 +0000
8.3 @@ -4,7 +4,7 @@
8.4 #include <vector>
8.5
8.6 #include <list_graph.h>
8.7 -#include <smart_graph.h>
8.8 +//#include <smart_graph.h>
8.9 //#include <dimacs.h>
8.10 #include <time_measure.h>
8.11 #include <for_each_macros.h>
9.1 --- a/src/work/marci/edmonds_karp.h Fri Apr 23 21:26:32 2004 +0000
9.2 +++ b/src/work/marci/edmonds_karp.h Sat Apr 24 12:44:41 2004 +0000
9.3 @@ -275,13 +275,14 @@
9.4 ResGW res_graph(*g, *capacity, *flow);
9.5 bool _augment=false;
9.6
9.7 - BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
9.8 + BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
9.9 + bfs(res_graph);
9.10 bfs.pushAndSetReached(s);
9.11
9.12 - typename ResGW::NodeMap<ResGWEdge> pred(res_graph);
9.13 + typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
9.14 pred.set(s, INVALID);
9.15
9.16 - typename ResGW::NodeMap<Number> free(res_graph);
9.17 + typename ResGW::template NodeMap<Number> free(res_graph);
9.18
9.19 //searching for augmenting path
9.20 while ( !bfs.finished() ) {
9.21 @@ -318,7 +319,7 @@
9.22 class DistanceMap {
9.23 protected:
9.24 const MapGraphWrapper* g;
9.25 - typename MapGraphWrapper::NodeMap<int> dist;
9.26 + typename MapGraphWrapper::template NodeMap<int> dist;
9.27 public:
9.28 DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
9.29 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
9.30 @@ -339,7 +340,8 @@
9.31
9.32 ResGW res_graph(*g, *capacity, *flow);
9.33
9.34 - BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
9.35 + BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
9.36 + bfs(res_graph);
9.37
9.38 bfs.pushAndSetReached(s);
9.39 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
9.40 @@ -357,7 +359,8 @@
9.41 typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
9.42 DistanceMap<ResGW> > FilterResGW;
9.43 FilterResGW filter_res_graph(res_graph, true_map, dist);
9.44 - typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
9.45 + typename ResGW::template NodeMap<typename MG::Node>
9.46 + res_graph_to_F(res_graph);
9.47 {
9.48 typename ResGW::NodeIt n;
9.49 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
9.50 @@ -367,8 +370,8 @@
9.51
9.52 typename MG::Node sF=res_graph_to_F[s];
9.53 typename MG::Node tF=res_graph_to_F[t];
9.54 - typename MG::EdgeMap<ResGWEdge> original_edge(F);
9.55 - typename MG::EdgeMap<Number> residual_capacity(F);
9.56 + typename MG::template EdgeMap<ResGWEdge> original_edge(F);
9.57 + typename MG::template EdgeMap<Number> residual_capacity(F);
9.58
9.59 //Making F to the graph containing the edges of the residual graph
9.60 //which are in some shortest paths
9.61 @@ -391,12 +394,12 @@
9.62 __augment=false;
9.63 //computing blocking flow with dfs
9.64
9.65 - DfsIterator< MG, typename MG::NodeMap<bool> > dfs(F);
9.66 - typename MG::NodeMap<typename MG::Edge> pred(F);
9.67 + DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F);
9.68 + typename MG::template NodeMap<typename MG::Edge> pred(F);
9.69 pred.set(sF, INVALID);
9.70 //invalid iterators for sources
9.71
9.72 - typename MG::NodeMap<Number> free(F);
9.73 + typename MG::template NodeMap<Number> free(F);
9.74
9.75 dfs.pushAndSetReached(sF);
9.76 while (!dfs.finished()) {
9.77 @@ -449,14 +452,17 @@
9.78 ResGW res_graph(*g, *capacity, *flow);
9.79
9.80 //bfs for distances on the residual graph
9.81 - BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
9.82 + BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
9.83 + bfs(res_graph);
9.84 bfs.pushAndSetReached(s);
9.85 - typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
9.86 + typename ResGW::template NodeMap<int>
9.87 + dist(res_graph); //filled up with 0's
9.88
9.89 //F will contain the physical copy of the residual graph
9.90 //with the set of edges which are on shortest paths
9.91 MG F;
9.92 - typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
9.93 + typename ResGW::template NodeMap<typename MG::Node>
9.94 + res_graph_to_F(res_graph);
9.95 {
9.96 typename ResGW::NodeIt n;
9.97 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
9.98 @@ -466,8 +472,8 @@
9.99
9.100 typename MG::Node sF=res_graph_to_F[s];
9.101 typename MG::Node tF=res_graph_to_F[t];
9.102 - typename MG::EdgeMap<ResGWEdge> original_edge(F);
9.103 - typename MG::EdgeMap<Number> residual_capacity(F);
9.104 + typename MG::template EdgeMap<ResGWEdge> original_edge(F);
9.105 + typename MG::template EdgeMap<Number> residual_capacity(F);
9.106
9.107 while ( !bfs.finished() ) {
9.108 ResGWOutEdgeIt e=bfs;
9.109 @@ -497,12 +503,12 @@
9.110 while (__augment) {
9.111 __augment=false;
9.112 //computing blocking flow with dfs
9.113 - DfsIterator< MG, typename MG::NodeMap<bool> > dfs(F);
9.114 - typename MG::NodeMap<typename MG::Edge> pred(F);
9.115 + DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F);
9.116 + typename MG::template NodeMap<typename MG::Edge> pred(F);
9.117 pred.set(sF, INVALID);
9.118 //invalid iterators for sources
9.119
9.120 - typename MG::NodeMap<Number> free(F);
9.121 + typename MG::template NodeMap<Number> free(F);
9.122
9.123 dfs.pushAndSetReached(sF);
9.124 while (!dfs.finished()) {
9.125 @@ -553,7 +559,8 @@
9.126
9.127 ResGW res_graph(*g, *capacity, *flow);
9.128
9.129 - BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
9.130 + BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
9.131 + bfs(res_graph);
9.132
9.133 bfs.pushAndSetReached(s);
9.134 DistanceMap<ResGW> dist(res_graph);
9.135 @@ -573,7 +580,7 @@
9.136
9.137 //Subgraph, which is able to delete edges which are already
9.138 //met by the dfs
9.139 - typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt>
9.140 + typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
9.141 first_out_edges(filter_res_graph);
9.142 typename FilterResGW::NodeIt v;
9.143 for(filter_res_graph.first(v); filter_res_graph.valid(v);
9.144 @@ -584,7 +591,7 @@
9.145 first_out_edges.set(v, e);
9.146 }
9.147 typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
9.148 - NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
9.149 + template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
9.150 ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
9.151
9.152 bool __augment=true;
9.153 @@ -593,14 +600,17 @@
9.154
9.155 __augment=false;
9.156 //computing blocking flow with dfs
9.157 - DfsIterator< ErasingResGW, typename ErasingResGW::NodeMap<bool> >
9.158 + DfsIterator< ErasingResGW,
9.159 + typename ErasingResGW::template NodeMap<bool> >
9.160 dfs(erasing_res_graph);
9.161 - typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>
9.162 - pred(erasing_res_graph);
9.163 + typename ErasingResGW::
9.164 + template NodeMap<typename ErasingResGW::OutEdgeIt>
9.165 + pred(erasing_res_graph);
9.166 pred.set(s, INVALID);
9.167 //invalid iterators for sources
9.168
9.169 - typename ErasingResGW::NodeMap<Number> free1(erasing_res_graph);
9.170 + typename ErasingResGW::template NodeMap<Number>
9.171 + free1(erasing_res_graph);
9.172
9.173 dfs.pushAndSetReached(
9.174 typename ErasingResGW::Node(
10.1 --- a/src/work/marci/edmonds_karp_demo.cc Fri Apr 23 21:26:32 2004 +0000
10.2 +++ b/src/work/marci/edmonds_karp_demo.cc Sat Apr 24 12:44:41 2004 +0000
10.3 @@ -3,7 +3,7 @@
10.4 #include <fstream>
10.5
10.6 #include <list_graph.h>
10.7 -#include <smart_graph.h>
10.8 +//#include <smart_graph.h>
10.9 #include <dimacs.h>
10.10 #include <edmonds_karp.h>
10.11 #include <time_measure.h>
11.1 --- a/src/work/marci/graph_wrapper.h Fri Apr 23 21:26:32 2004 +0000
11.2 +++ b/src/work/marci/graph_wrapper.h Sat Apr 24 12:44:41 2004 +0000
11.3 @@ -183,20 +183,18 @@
11.4
11.5 void clear() const { graph->clear(); }
11.6
11.7 - template<typename T> class NodeMap : public Graph::NodeMap<T> {
11.8 + template<typename T> class NodeMap : public Graph::template NodeMap<T> {
11.9 + typedef typename Graph::template NodeMap<T> Parent;
11.10 public:
11.11 - NodeMap(const GraphWrapper<Graph>& _G) :
11.12 - Graph::NodeMap<T>(*(_G.graph)) { }
11.13 - NodeMap(const GraphWrapper<Graph>& _G, T a) :
11.14 - Graph::NodeMap<T>(*(_G.graph), a) { }
11.15 + NodeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
11.16 + NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
11.17 };
11.18
11.19 - template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
11.20 + template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
11.21 + typedef typename Graph::template EdgeMap<T> Parent;
11.22 public:
11.23 - EdgeMap(const GraphWrapper<Graph>& _G) :
11.24 - Graph::EdgeMap<T>(*(_G.graph)) { }
11.25 - EdgeMap(const GraphWrapper<Graph>& _G, T a) :
11.26 - Graph::EdgeMap<T>(*(_G.graph), a) { }
11.27 + EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
11.28 + EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
11.29 };
11.30 };
11.31
11.32 @@ -252,13 +250,17 @@
11.33 }
11.34
11.35 using GraphWrapper<Graph>::next;
11.36 - OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
11.37 - InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
11.38 + OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
11.39 + InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
11.40
11.41 - Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
11.42 - Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
11.43 - Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
11.44 - Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
11.45 + Node aNode(const OutEdgeIt& e) const {
11.46 + return Node(this->graph->aNode(e.e)); }
11.47 + Node aNode(const InEdgeIt& e) const {
11.48 + return Node(this->graph->aNode(e.e)); }
11.49 + Node bNode(const OutEdgeIt& e) const {
11.50 + return Node(this->graph->bNode(e.e)); }
11.51 + Node bNode(const InEdgeIt& e) const {
11.52 + return Node(this->graph->bNode(e.e)); }
11.53
11.54 Node tail(const Edge& e) const {
11.55 return GraphWrapper<Graph>::head(e); }
11.56 @@ -366,30 +368,38 @@
11.57 }
11.58
11.59 NodeIt& next(NodeIt& i) const {
11.60 - graph->next(i.n);
11.61 - while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); }
11.62 + this->graph->next(i.n);
11.63 + while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
11.64 + this->graph->next(i.n); }
11.65 return i;
11.66 }
11.67 OutEdgeIt& next(OutEdgeIt& i) const {
11.68 - graph->next(i.e);
11.69 - while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
11.70 + this->graph->next(i.e);
11.71 + while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
11.72 + this->graph->next(i.e); }
11.73 return i;
11.74 }
11.75 InEdgeIt& next(InEdgeIt& i) const {
11.76 - graph->next(i.e);
11.77 - while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
11.78 + this->graph->next(i.e);
11.79 + while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
11.80 + this->graph->next(i.e); }
11.81 return i;
11.82 }
11.83 EdgeIt& next(EdgeIt& i) const {
11.84 - graph->next(i.e);
11.85 - while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
11.86 + this->graph->next(i.e);
11.87 + while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
11.88 + this->graph->next(i.e); }
11.89 return i;
11.90 }
11.91
11.92 - Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
11.93 - Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
11.94 - Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
11.95 - Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
11.96 + Node aNode(const OutEdgeIt& e) const {
11.97 + return Node(this->graph->aNode(e.e)); }
11.98 + Node aNode(const InEdgeIt& e) const {
11.99 + return Node(this->graph->aNode(e.e)); }
11.100 + Node bNode(const OutEdgeIt& e) const {
11.101 + return Node(this->graph->bNode(e.e)); }
11.102 + Node bNode(const InEdgeIt& e) const {
11.103 + return Node(this->graph->bNode(e.e)); }
11.104
11.105 ///\todo
11.106 ///Some doki, please.
11.107 @@ -469,11 +479,12 @@
11.108 // }
11.109 OutEdgeIt& next(OutEdgeIt& e) const {
11.110 if (e.out_or_in) {
11.111 - typename Graph::Node n=graph->tail(e.out);
11.112 - graph->next(e.out);
11.113 - if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
11.114 + typename Graph::Node n=this->graph->tail(e.out);
11.115 + this->graph->next(e.out);
11.116 + if (!this->graph->valid(e.out)) {
11.117 + e.out_or_in=false; this->graph->first(e.in, n); }
11.118 } else {
11.119 - graph->next(e.in);
11.120 + this->graph->next(e.in);
11.121 }
11.122 return e;
11.123 }
11.124 @@ -485,9 +496,11 @@
11.125 // }
11.126
11.127 Node aNode(const OutEdgeIt& e) const {
11.128 - if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
11.129 + if (e.out_or_in) return this->graph->tail(e); else
11.130 + return this->graph->head(e); }
11.131 Node bNode(const OutEdgeIt& e) const {
11.132 - if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
11.133 + if (e.out_or_in) return this->graph->head(e); else
11.134 + return this->graph->tail(e); }
11.135 };
11.136
11.137 /// A wrapper for composing the residual graph for directed flow and circulation problems.
11.138 @@ -645,67 +658,80 @@
11.139 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
11.140 OutEdgeIt& next(OutEdgeIt& e) const {
11.141 if (e.forward) {
11.142 - Node v=graph->aNode(e.out);
11.143 - graph->next(e.out);
11.144 - while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
11.145 - if (!graph->valid(e.out)) {
11.146 + Node v=this->graph->aNode(e.out);
11.147 + this->graph->next(e.out);
11.148 + while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
11.149 + this->graph->next(e.out); }
11.150 + if (!this->graph->valid(e.out)) {
11.151 e.forward=false;
11.152 - graph->first(e.in, v);
11.153 - while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
11.154 + this->graph->first(e.in, v);
11.155 + while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
11.156 + this->graph->next(e.in); }
11.157 }
11.158 } else {
11.159 - graph->next(e.in);
11.160 - while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
11.161 + this->graph->next(e.in);
11.162 + while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
11.163 + this->graph->next(e.in); }
11.164 }
11.165 return e;
11.166 }
11.167 // FIXME Not tested
11.168 InEdgeIt& next(InEdgeIt& e) const {
11.169 if (e.forward) {
11.170 - Node v=graph->aNode(e.in);
11.171 - graph->next(e.in);
11.172 - while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
11.173 - if (!graph->valid(e.in)) {
11.174 + Node v=this->graph->aNode(e.in);
11.175 + this->graph->next(e.in);
11.176 + while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
11.177 + this->graph->next(e.in); }
11.178 + if (!this->graph->valid(e.in)) {
11.179 e.forward=false;
11.180 - graph->first(e.out, v);
11.181 - while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
11.182 + this->graph->first(e.out, v);
11.183 + while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
11.184 + this->graph->next(e.out); }
11.185 }
11.186 } else {
11.187 - graph->next(e.out);
11.188 - while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
11.189 + this->graph->next(e.out);
11.190 + while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
11.191 + this->graph->next(e.out); }
11.192 }
11.193 return e;
11.194 }
11.195 EdgeIt& next(EdgeIt& e) const {
11.196 if (e.forward) {
11.197 - graph->next(e.e);
11.198 - while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
11.199 - if (!graph->valid(e.e)) {
11.200 + this->graph->next(e.e);
11.201 + while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
11.202 + this->graph->next(e.e); }
11.203 + if (!this->graph->valid(e.e)) {
11.204 e.forward=false;
11.205 - graph->first(e.e);
11.206 - while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
11.207 + this->graph->first(e.e);
11.208 + while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
11.209 + this->graph->next(e.e); }
11.210 }
11.211 } else {
11.212 - graph->next(e.e);
11.213 - while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
11.214 + this->graph->next(e.e);
11.215 + while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
11.216 + this->graph->next(e.e); }
11.217 }
11.218 return e;
11.219 }
11.220
11.221 Node tail(Edge e) const {
11.222 - return ((e.forward) ? graph->tail(e) : graph->head(e)); }
11.223 + return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
11.224 Node head(Edge e) const {
11.225 - return ((e.forward) ? graph->head(e) : graph->tail(e)); }
11.226 + return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
11.227
11.228 Node aNode(OutEdgeIt e) const {
11.229 - return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
11.230 + return ((e.forward) ? this->graph->aNode(e.out) :
11.231 + this->graph->aNode(e.in)); }
11.232 Node bNode(OutEdgeIt e) const {
11.233 - return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
11.234 + return ((e.forward) ? this->graph->bNode(e.out) :
11.235 + this->graph->bNode(e.in)); }
11.236
11.237 Node aNode(InEdgeIt e) const {
11.238 - return ((e.forward) ? graph->aNode(e.in) : graph->aNode(e.out)); }
11.239 + return ((e.forward) ? this->graph->aNode(e.in) :
11.240 + this->graph->aNode(e.out)); }
11.241 Node bNode(InEdgeIt e) const {
11.242 - return ((e.forward) ? graph->bNode(e.in) : graph->bNode(e.out)); }
11.243 + return ((e.forward) ? this->graph->bNode(e.in) :
11.244 + this->graph->bNode(e.out)); }
11.245
11.246 // int nodeNum() const { return graph->nodeNum(); }
11.247 //FIXME
11.248 @@ -717,7 +743,7 @@
11.249
11.250 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
11.251 bool valid(Edge e) const {
11.252 - return graph->valid(e);
11.253 + return this->graph->valid(e);
11.254 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
11.255 }
11.256
11.257 @@ -751,7 +777,7 @@
11.258
11.259 template <typename T>
11.260 class EdgeMap {
11.261 - typename Graph::EdgeMap<T> forward_map, backward_map;
11.262 + typename Graph::template EdgeMap<T> forward_map, backward_map;
11.263 public:
11.264 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
11.265 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
11.266 @@ -861,14 +887,18 @@
11.267
11.268 using GraphWrapper<Graph>::next;
11.269 // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
11.270 - OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
11.271 - InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
11.272 - EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
11.273 + OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
11.274 + InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
11.275 + EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
11.276
11.277 - Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
11.278 - Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
11.279 - Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
11.280 - Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
11.281 + Node aNode(const OutEdgeIt& e) const {
11.282 + return Node(this->graph->aNode(e.e)); }
11.283 + Node aNode(const InEdgeIt& e) const {
11.284 + return Node(this->graph->aNode(e.e)); }
11.285 + Node bNode(const OutEdgeIt& e) const {
11.286 + return Node(this->graph->bNode(e.e)); }
11.287 + Node bNode(const InEdgeIt& e) const {
11.288 + return Node(this->graph->bNode(e.e)); }
11.289
11.290 void erase(const OutEdgeIt& e) const {
11.291 OutEdgeIt f=e;
11.292 @@ -885,7 +915,8 @@
11.293 /// graph or a directed graph with edges oriented from S to T.
11.294 template<typename Graph>
11.295 class BipartiteGraphWrapper : public GraphWrapper<Graph> {
11.296 - typedef IterableBoolMap< typename Graph::NodeMap<int> > SFalseTTrueMap;
11.297 + typedef IterableBoolMap< typename Graph::template NodeMap<int> >
11.298 + SFalseTTrueMap;
11.299 SFalseTTrueMap* s_false_t_true_map;
11.300
11.301 public:
11.302 @@ -983,8 +1014,8 @@
11.303 // TNodeIt& next(TNodeIt& n) const {
11.304 // this->s_false_t_true_map->next(n); return n;
11.305 // }
11.306 - OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
11.307 - InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
11.308 + OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
11.309 + InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
11.310
11.311 Node tail(const Edge& e) {
11.312 if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
11.313 @@ -1078,7 +1109,7 @@
11.314 protected:
11.315 friend class GraphWrapper<Graph>;
11.316 friend class stGraphWrapper<Graph>;
11.317 - template <typename T> friend class stGraphWrapper<Graph>::NodeMap;
11.318 + template <typename T> friend class NodeMap;
11.319 friend class Edge;
11.320 friend class OutEdgeIt;
11.321 friend class InEdgeIt;
11.322 @@ -1119,7 +1150,7 @@
11.323 class Edge : public Graph::Edge {
11.324 friend class GraphWrapper<Graph>;
11.325 friend class stGraphWrapper<Graph>;
11.326 - template <typename T> friend class stGraphWrapper<Graph>::EdgeMap;
11.327 + template <typename T> friend class EdgeMap;
11.328 int spec;
11.329 typename Graph::Node n;
11.330 public:
11.331 @@ -1273,8 +1304,8 @@
11.332 NodeIt& next(NodeIt& i) const {
11.333 switch (i.spec) {
11.334 case 0:
11.335 - graph->next(i.n);
11.336 - if (!graph->valid(i.n)) {
11.337 + this->graph->next(i.n);
11.338 + if (!this->graph->valid(i.n)) {
11.339 i.spec=1;
11.340 }
11.341 break;
11.342 @@ -1290,10 +1321,10 @@
11.343 OutEdgeIt& next(OutEdgeIt& i) const {
11.344 switch (i.spec) {
11.345 case 0: //normal edge
11.346 - typename Graph::Node v=graph->aNode(i.e);
11.347 - graph->next(i.e);
11.348 - if (!graph->valid(i.e)) { //Az igazi elek vegere ertunk
11.349 - if (graph->inSClass(v)) { //S, nincs kiel
11.350 + typename Graph::Node v=this->graph->aNode(i.e);
11.351 + this->graph->next(i.e);
11.352 + if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
11.353 + if (this->graph->inSClass(v)) { //S, nincs kiel
11.354 i.spec=3;
11.355 i.n=INVALID;
11.356 } else { //T, van kiel
11.357 @@ -1303,8 +1334,8 @@
11.358 }
11.359 break;
11.360 case 1: //s->vmi
11.361 - graph->next(i.n);
11.362 - if (!graph->valid(i.n)) i.spec=3;
11.363 + this->graph->next(i.n);
11.364 + if (!this->graph->valid(i.n)) i.spec=3;
11.365 break;
11.366 case 2: //vmi->t
11.367 i.spec=3;
11.368 @@ -1316,10 +1347,10 @@
11.369 InEdgeIt& next(InEdgeIt& i) const {
11.370 switch (i.spec) {
11.371 case 0: //normal edge
11.372 - typename Graph::Node v=graph->aNode(i.e);
11.373 - graph->next(i.e);
11.374 - if (!graph->valid(i.e)) { //Az igazi elek vegere ertunk
11.375 - if (graph->inTClass(v)) { //S, nincs beel
11.376 + typename Graph::Node v=this->graph->aNode(i.e);
11.377 + this->graph->next(i.e);
11.378 + if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
11.379 + if (this->graph->inTClass(v)) { //S, nincs beel
11.380 i.spec=3;
11.381 i.n=INVALID;
11.382 } else { //S, van beel
11.383 @@ -1333,8 +1364,8 @@
11.384 i.n=INVALID;
11.385 break;
11.386 case 2: //vmi->t
11.387 - graph->next(i.n);
11.388 - if (!graph->valid(i.n)) i.spec=3;
11.389 + this->graph->next(i.n);
11.390 + if (!this->graph->valid(i.n)) i.spec=3;
11.391 break;
11.392 }
11.393 return i;
11.394 @@ -1343,28 +1374,28 @@
11.395 EdgeIt& next(EdgeIt& i) const {
11.396 switch (i.spec) {
11.397 case 0:
11.398 - graph->next(i.e);
11.399 - if (!graph->valid(i.e)) {
11.400 + this->graph->next(i.e);
11.401 + if (!this->graph->valid(i.e)) {
11.402 i.spec=1;
11.403 - graph->first(n, S_CLASS);
11.404 - if (!graph->valid(i.n)) {
11.405 + this->graph->first(i.n, S_CLASS);
11.406 + if (!this->graph->valid(i.n)) {
11.407 i.spec=2;
11.408 - graph->first(n, T_CLASS);
11.409 - if (!graph->valid(i.n)) spec=3;
11.410 + this->graph->first(i.n, T_CLASS);
11.411 + if (!this->graph->valid(i.n)) i.spec=3;
11.412 }
11.413 }
11.414 break;
11.415 case 1:
11.416 - graph->next(i.n);
11.417 - if (!graph->valid(i.n)) {
11.418 + this->graph->next(i.n);
11.419 + if (!this->graph->valid(i.n)) {
11.420 i.spec=2;
11.421 - graph->first(n, T_CLASS);
11.422 - if (!graph->valid(i.n)) spec=3;
11.423 + this->graph->first(i.n, T_CLASS);
11.424 + if (!this->graph->valid(i.n)) i.spec=3;
11.425 }
11.426 break;
11.427 case 2:
11.428 - graph->next(i.n);
11.429 - if (!graph->valid(i.n)) i.spec=3;
11.430 + this->graph->next(i.n);
11.431 + if (!this->graph->valid(i.n)) i.spec=3;
11.432 break;
11.433 }
11.434 return i;
11.435 @@ -1373,7 +1404,7 @@
11.436 Node tail(const Edge& e) const {
11.437 switch (e.spec) {
11.438 case 0:
11.439 - return Node(graph->tail(e));
11.440 + return Node(this->graph->tail(e));
11.441 break;
11.442 case 1:
11.443 return S_NODE;
11.444 @@ -1386,7 +1417,7 @@
11.445 Node head(const Edge& e) const {
11.446 switch (e.spec) {
11.447 case 0:
11.448 - return Node(graph->head(e));
11.449 + return Node(this->graph->head(e));
11.450 break;
11.451 case 1:
11.452 return Node(e.n);
11.453 @@ -1400,30 +1431,31 @@
11.454 bool valid(const Node& n) const { return (n.spec<3); }
11.455 bool valid(const Edge& e) const { return (e.spec<3); }
11.456
11.457 -// int nodeNum() const { return graph->nodeNum(); }
11.458 -// int edgeNum() const { return graph->edgeNum(); }
11.459 +// int nodeNum() const { return this->graph->nodeNum(); }
11.460 +// int edgeNum() const { return this->graph->edgeNum(); }
11.461
11.462 Node aNode(const OutEdgeIt& e) const { return tail(e); }
11.463 Node aNode(const InEdgeIt& e) const { return head(e); }
11.464 Node bNode(const OutEdgeIt& e) const { return head(e); }
11.465 Node bNode(const InEdgeIt& e) const { return tail(e); }
11.466
11.467 -// Node addNode() const { return Node(graph->addNode()); }
11.468 +// Node addNode() const { return Node(this->graph->addNode()); }
11.469 // Edge addEdge(const Node& tail, const Node& head) const {
11.470 -// return Edge(graph->addEdge(tail, head)); }
11.471 +// return Edge(this->graph->addEdge(tail, head)); }
11.472
11.473 -// void erase(const Node& i) const { graph->erase(i); }
11.474 -// void erase(const Edge& i) const { graph->erase(i); }
11.475 +// void erase(const Node& i) const { this->graph->erase(i); }
11.476 +// void erase(const Edge& i) const { this->graph->erase(i); }
11.477
11.478 -// void clear() const { graph->clear(); }
11.479 +// void clear() const { this->graph->clear(); }
11.480
11.481 - template<typename T> class NodeMap : public GraphWrapper<Graph>::NodeMap<T> {
11.482 + template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
11.483 + typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
11.484 T s_value, t_value;
11.485 public:
11.486 - NodeMap(const stGraphWrapper<Graph>& _G) :
11.487 - GraphWrapper<Graph>::NodeMap<T>(_G) { }
11.488 - NodeMap(const stGraphWrapper<Graph>& _G, T a) :
11.489 - GraphWrapper<Graph>::NodeMap<T>(_G, a), s_value(a), t_value(a) { }
11.490 + NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G) { }
11.491 + NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
11.492 + s_value(a),
11.493 + t_value(a) { }
11.494 T operator[](const Node& n) const {
11.495 switch (n.spec) {
11.496 case 0:
11.497 @@ -1440,7 +1472,7 @@
11.498 void set(const Node& n, T t) {
11.499 switch (n.spec) {
11.500 case 0:
11.501 - GraphWrapper<Graph>::NodeMap<T>::set(n, t);
11.502 + GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
11.503 break;
11.504 case 1:
11.505 s_value=t;
11.506 @@ -1452,13 +1484,14 @@
11.507 }
11.508 };
11.509
11.510 - template<typename T> class EdgeMap : public GraphWrapper<Graph>::EdgeMap<T> {
11.511 - typename GraphWrapper<Graph>::NodeMap<T> node_value;
11.512 + template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
11.513 + typedef typename Graph::template NodeMap<T> Parent;
11.514 + typename GraphWrapper<Graph>::template NodeMap<T> node_value;
11.515 public:
11.516 - EdgeMap(const stGraphWrapper<Graph>& _G) :
11.517 - GraphWrapper<Graph>::EdgeMap<T>(_G), node_value(_G) { }
11.518 - EdgeMap(const stGraphWrapper<Graph>& _G, T a) :
11.519 - GraphWrapper<Graph>::EdgeMap<T>(_G, a), node_value(_G, a) { }
11.520 + EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
11.521 + node_value(_G) { }
11.522 + EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
11.523 + node_value(_G, a) { }
11.524 T operator[](const Edge& e) const {
11.525 switch (e.spec) {
11.526 case 0:
12.1 --- a/src/work/marci/iterator_bfs_demo.cc Fri Apr 23 21:26:32 2004 +0000
12.2 +++ b/src/work/marci/iterator_bfs_demo.cc Sat Apr 24 12:44:41 2004 +0000
12.3 @@ -4,7 +4,7 @@
12.4 #include <string>
12.5
12.6 #include <list_graph.h>
12.7 -#include <smart_graph.h>
12.8 +//#include <smart_graph.h>
12.9 #include <bfs_iterator.h>
12.10 #include <graph_wrapper.h>
12.11
13.1 --- a/src/work/marci/makefile Fri Apr 23 21:26:32 2004 +0000
13.2 +++ b/src/work/marci/makefile Sat Apr 24 12:44:41 2004 +0000
13.3 @@ -1,7 +1,7 @@
13.4 CXX2 = g++-2.95
13.5 -CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
13.6 -CXX=$(CXX3)
13.7 -CC=$(CXX)
13.8 +#CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
13.9 +#CXX=$(CXX3)
13.10 +#CC=$(CXX)
13.11 #LEDAROOT ?= /ledasrc/LEDA-4.1
13.12 BOOSTROOT ?= /home/marci/boost
13.13 INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
13.14 @@ -12,16 +12,17 @@
13.15 BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test
13.16 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
13.17
13.18 -all: $(BINARIES)
13.19 +include ../makefile
13.20 +#all: $(BINARIES)
13.21
13.22 -.depend dep depend:
13.23 - -$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
13.24 +#.depend dep depend:
13.25 +# -$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
13.26 # -g++ $(INCLUDEDIRS) $(LEDAINCLUDE) -M $(LEDABINARIES:=.cc) >> .depend #2>/dev/null
13.27
13.28
13.29
13.30 -makefile: .depend
13.31 -sinclude .depend
13.32 +#makefile: .depend
13.33 +#sinclude .depend
13.34
13.35 leda_graph_demo.o:
13.36 $(CXX3) -Wall -O -I.. -I../alpar -I$(LEDAROOT)/incl -I. -c leda_graph_demo.cc
13.37 @@ -72,7 +73,7 @@
13.38 preflow_demo_athos:
13.39 $(CXX3) $(CXXFLAGS) -I. -I.. -I../athos -o preflow_demo_athos preflow_demo_athos.cc
13.40
13.41 -clean:
13.42 - $(RM) *.o $(BINARIES) .depend
13.43 -
13.44 -.PHONY: all clean dep depend
13.45 +#clean:
13.46 +# $(RM) *.o $(BINARIES) .depend
13.47 +#
13.48 +#.PHONY: all clean dep depend