1.1 --- a/src/work/edmonds_karp.h Mon Mar 29 21:43:27 2004 +0000
1.2 +++ b/src/work/edmonds_karp.h Tue Mar 30 07:07:44 2004 +0000
1.3 @@ -313,26 +313,174 @@
1.4 return _augment;
1.5 }
1.6
1.7 +// template<typename MutableGraph> bool augmentOnBlockingFlow() {
1.8 +// bool _augment=false;
1.9 +
1.10 +// AugGraph res_graph(*G, *flow, *capacity);
1.11 +
1.12 +// typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.13 +// BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
1.14 +
1.15 +// bfs.pushAndSetReached(s);
1.16 +// typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.17 +// while ( !bfs.finished() ) {
1.18 +// AugOutEdgeIt e=bfs;
1.19 +// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.20 +// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.21 +// }
1.22 +
1.23 +// ++bfs;
1.24 +// } //computing distances from s in the residual graph
1.25 +
1.26 +// MutableGraph F;
1.27 +// typename AugGraph::NodeMap<typename MutableGraph::Node>
1.28 +// res_graph_to_F(res_graph);
1.29 +// for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.30 +// res_graph_to_F.set(n, F.addNode());
1.31 +// }
1.32 +
1.33 +// typename MutableGraph::Node sF=res_graph_to_F.get(s);
1.34 +// typename MutableGraph::Node tF=res_graph_to_F.get(t);
1.35 +
1.36 +// typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
1.37 +// typename MutableGraph::EdgeMap<Number> residual_capacity(F);
1.38 +
1.39 +// //Making F to the graph containing the edges of the residual graph
1.40 +// //which are in some shortest paths
1.41 +// for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
1.42 +// if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.43 +// typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.44 +// original_edge.update();
1.45 +// original_edge.set(f, e);
1.46 +// residual_capacity.update();
1.47 +// residual_capacity.set(f, res_graph.free(e));
1.48 +// }
1.49 +// }
1.50 +
1.51 +// bool __augment=true;
1.52 +
1.53 +// while (__augment) {
1.54 +// __augment=false;
1.55 +// //computing blocking flow with dfs
1.56 +// typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
1.57 +// DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
1.58 +// typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
1.59 +// pred.set(sF, typename MutableGraph::Edge(INVALID));
1.60 +// //invalid iterators for sources
1.61 +
1.62 +// typename MutableGraph::NodeMap<Number> free(F);
1.63 +
1.64 +// dfs.pushAndSetReached(sF);
1.65 +// while (!dfs.finished()) {
1.66 +// ++dfs;
1.67 +// if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
1.68 +// if (dfs.isBNodeNewlyReached()) {
1.69 +// typename MutableGraph::Node v=F.aNode(dfs);
1.70 +// typename MutableGraph::Node w=F.bNode(dfs);
1.71 +// pred.set(w, dfs);
1.72 +// if (F.valid(pred.get(v))) {
1.73 +// free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
1.74 +// } else {
1.75 +// free.set(w, residual_capacity.get(dfs));
1.76 +// }
1.77 +// if (w==tF) {
1.78 +// __augment=true;
1.79 +// _augment=true;
1.80 +// break;
1.81 +// }
1.82 +
1.83 +// } else {
1.84 +// F.erase(typename MutableGraph::OutEdgeIt(dfs));
1.85 +// }
1.86 +// }
1.87 +// }
1.88 +
1.89 +// if (__augment) {
1.90 +// typename MutableGraph::Node n=tF;
1.91 +// Number augment_value=free.get(tF);
1.92 +// while (F.valid(pred.get(n))) {
1.93 +// typename MutableGraph::Edge e=pred.get(n);
1.94 +// res_graph.augment(original_edge.get(e), augment_value);
1.95 +// n=F.tail(e);
1.96 +// if (residual_capacity.get(e)==augment_value)
1.97 +// F.erase(e);
1.98 +// else
1.99 +// residual_capacity.set(e, residual_capacity.get(e)-augment_value);
1.100 +// }
1.101 +// }
1.102 +
1.103 +// }
1.104 +
1.105 +// return _augment;
1.106 +// }
1.107 +
1.108 + template<typename GraphWrapper>
1.109 + class DistanceMap {
1.110 + protected:
1.111 + GraphWrapper gw;
1.112 + typename GraphWrapper::NodeMap<int> dist;
1.113 + public:
1.114 + DistanceMap(GraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
1.115 + //NodeMap(const ListGraph& _G, T a) :
1.116 + //G(_G), container(G.node_id, a) { }
1.117 + void set(const typename GraphWrapper::Node& n, int a) { dist[n]=a; }
1.118 + int get(const typename GraphWrapper::Node& n) const { return dist[n]; }
1.119 + bool get(const typename GraphWrapper::Edge& e) const {
1.120 + return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
1.121 + }
1.122 + //typename std::vector<T>::reference operator[](Node n) {
1.123 + //return container[/*G.id(n)*/n.node->id]; }
1.124 + //typename std::vector<T>::const_reference operator[](Node n) const {
1.125 + //return container[/*G.id(n)*/n.node->id];
1.126 + };
1.127 +
1.128 template<typename MutableGraph> bool augmentOnBlockingFlow() {
1.129 bool _augment=false;
1.130
1.131 AugGraph res_graph(*G, *flow, *capacity);
1.132
1.133 typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.134 - BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
1.135 + BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
1.136
1.137 bfs.pushAndSetReached(s);
1.138 - typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.139 + //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.140 + DistanceMap<AugGraph> dist(res_graph);
1.141 while ( !bfs.finished() ) {
1.142 AugOutEdgeIt e=bfs;
1.143 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.144 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.145 }
1.146 -
1.147 ++bfs;
1.148 } //computing distances from s in the residual graph
1.149
1.150 +// MutableGraph F;
1.151 +// typename AugGraph::NodeMap<typename MutableGraph::Node>
1.152 +// res_graph_to_F(res_graph);
1.153 +// for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.154 +// res_graph_to_F.set(n, F.addNode());
1.155 +// }
1.156 +
1.157 +// typename MutableGraph::Node sF=res_graph_to_F.get(s);
1.158 +// typename MutableGraph::Node tF=res_graph_to_F.get(t);
1.159 +
1.160 +// typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
1.161 +// typename MutableGraph::EdgeMap<Number> residual_capacity(F);
1.162 +
1.163 +// //Making F to the graph containing the edges of the residual graph
1.164 +// //which are in some shortest paths
1.165 +// for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
1.166 +// if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.167 +// typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.168 +// original_edge.update();
1.169 +// original_edge.set(f, e);
1.170 +// residual_capacity.update();
1.171 +// residual_capacity.set(f, res_graph.free(e));
1.172 +// }
1.173 +// }
1.174 +
1.175 MutableGraph F;
1.176 + typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;
1.177 + FilterResGraph filter_res_graph(res_graph, dist);
1.178 typename AugGraph::NodeMap<typename MutableGraph::Node>
1.179 res_graph_to_F(res_graph);
1.180 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.181 @@ -363,7 +511,7 @@
1.182 __augment=false;
1.183 //computing blocking flow with dfs
1.184 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
1.185 - DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
1.186 + DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F);
1.187 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
1.188 pred.set(sF, typename MutableGraph::Edge(INVALID));
1.189 //invalid iterators for sources
1.190 @@ -413,6 +561,7 @@
1.191
1.192 return _augment;
1.193 }
1.194 +
1.195 template<typename MutableGraph> bool augmentOnBlockingFlow1() {
1.196 bool _augment=false;
1.197
1.198 @@ -420,7 +569,7 @@
1.199
1.200 //bfs for distances on the residual graph
1.201 typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.202 - BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
1.203 + BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
1.204 bfs.pushAndSetReached(s);
1.205 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.206
2.1 --- a/src/work/marci/graph_wrapper.h Mon Mar 29 21:43:27 2004 +0000
2.2 +++ b/src/work/marci/graph_wrapper.h Tue Mar 30 07:07:44 2004 +0000
2.3 @@ -91,7 +91,7 @@
2.4 GraphWrapper gw;
2.5
2.6 public:
2.7 - typedef typename GraphWrapper::BaseGraph BaseGraph;
2.8 + //typedef typename GraphWrapper::BaseGraph BaseGraph;
2.9
2.10 typedef typename GraphWrapper::Node Node;
2.11 typedef typename GraphWrapper::NodeIt NodeIt;
2.12 @@ -105,8 +105,8 @@
2.13 //GraphWrapperSkeleton() : gw() { }
2.14 GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { }
2.15
2.16 - void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
2.17 - BaseGraph& getGraph() const { return gw.getGraph(); }
2.18 + //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
2.19 + //BaseGraph& getGraph() const { return gw.getGraph(); }
2.20
2.21 template<typename I> I& first(I& i) const { return gw.first(i); }
2.22 template<typename I, typename P> I& first(I& i, const P& p) const {
2.23 @@ -342,6 +342,48 @@
2.24 { return GraphWrapperSkeleton<GraphWrapper>::head(e); }
2.25 };
2.26
2.27 + //Subgraph on the same node-set and partial edge-set
2.28 + template<typename GraphWrapper, typename EdgeFilterMap>
2.29 + class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
2.30 + protected:
2.31 + EdgeFilterMap* filter_map;
2.32 + public:
2.33 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
2.34 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
2.35 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
2.36 + typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
2.37 + typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
2.38 + typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
2.39 +
2.40 + SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) :
2.41 + GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { }
2.42 +
2.43 + template<typename I> I& first(I& i) const {
2.44 + gw.first(i);
2.45 + while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
2.46 + return i;
2.47 + }
2.48 + template<typename I, typename P> I& first(I& i, const P& p) const {
2.49 + gw.first(i, p);
2.50 + while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
2.51 + return i;
2.52 + }
2.53 +
2.54 + //template<typename I> I getNext(const I& i) const {
2.55 + // return gw.getNext(i);
2.56 + //}
2.57 + template<typename I> I& next(I &i) const {
2.58 + gw.next(i);
2.59 + while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
2.60 + return i;
2.61 + }
2.62 +
2.63 + template< typename It > It first() const {
2.64 + It e; this->first(e); return e; }
2.65 +
2.66 + template< typename It > It first(const Node& v) const {
2.67 + It e; this->first(e, v); return e; }
2.68 + };
2.69
2.70 // template<typename GraphWrapper>
2.71 // class UndirGraphWrapper {
2.72 @@ -858,6 +900,9 @@
2.73 // }
2.74 };
2.75
2.76 + //FIXME This is just for having InEdgeIt
2.77 + typedef void InEdgeIt;
2.78 +
2.79 class EdgeIt : public Edge {
2.80 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
2.81 typename Graph::NodeIt v;
2.82 @@ -1005,6 +1050,11 @@
2.83 Node bNode(OutEdgeIt e) const {
2.84 return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
2.85
2.86 + int nodeNum() const { return gw.nodeNum(); }
2.87 + //FIXME
2.88 + //int edgeNum() const { return gw.edgeNum(); }
2.89 +
2.90 +
2.91 int id(Node v) const { return gw.id(v); }
2.92
2.93 bool valid(Node n) const { return gw.valid(n); }