1.1 --- a/src/demo/sub_graph_wrapper_demo.cc Mon Sep 20 08:27:34 2004 +0000
1.2 +++ b/src/demo/sub_graph_wrapper_demo.cc Mon Sep 20 09:05:19 2004 +0000
1.3 @@ -14,7 +14,7 @@
1.4 #include <hugo/graph_wrapper.h>
1.5 #include <hugo/dimacs.h>
1.6 #include <hugo/preflow.h>
1.7 -#include <tight_edge_filter_map.h>
1.8 +#include <hugo/tight_edge_filter_map.h>
1.9
1.10 using namespace hugo;
1.11
2.1 --- a/src/demo/tight_edge_filter_map.h Mon Sep 20 08:27:34 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,46 +0,0 @@
2.4 -// -*- C++ -*-
2.5 -#ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
2.6 -#define HUGO_TIGHT_EDGE_FILTER_MAP_H
2.7 -
2.8 -// /// \file
2.9 -// /// \brief Maximum flow algorithms.
2.10 -// /// \ingroup galgs
2.11 -
2.12 -namespace hugo {
2.13 -
2.14 - /// \brief A map for filtering the edge-set to those edges
2.15 - /// which are tight w.r.t. some node_potential map and
2.16 - /// edge_distance map.
2.17 - ///
2.18 - /// A node-map node_potential is said to be a potential w.r.t.
2.19 - /// an edge-map edge_distance
2.20 - /// if and only if for each edge e, node_potential[g.head(e)]
2.21 - /// <= edge_distance[e]+node_potential[g.tail(e)]
2.22 - /// (or the reverse inequality holds for each edge).
2.23 - /// An edge is said to be tight if this inequality holds with equality,
2.24 - /// and the map returns true exactly for those edges.
2.25 - /// To avoid rounding errors, it is recommended to use this class with exact
2.26 - /// types, e.g. with int.
2.27 - template<typename Graph,
2.28 - typename NodePotentialMap, typename EdgeDistanceMap>
2.29 - class TightEdgeFilterMap {
2.30 - protected:
2.31 - const Graph* g;
2.32 - NodePotentialMap* node_potential;
2.33 - EdgeDistanceMap* edge_distance;
2.34 - public:
2.35 - TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
2.36 - EdgeDistanceMap& _edge_distance) :
2.37 - g(&_g), node_potential(&_node_potential),
2.38 - edge_distance(&_edge_distance) { }
2.39 - bool operator[](const typename Graph::Edge& e) const {
2.40 - return ((*node_potential)[g->head(e)] ==
2.41 - (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
2.42 - }
2.43 - };
2.44 -
2.45 -} //namespace hugo
2.46 -
2.47 -#endif //HUGO_TIGHT_EDGE_FILTER_MAP_H
2.48 -
2.49 -
3.1 --- a/src/hugo/graph_wrapper.h Mon Sep 20 08:27:34 2004 +0000
3.2 +++ b/src/hugo/graph_wrapper.h Mon Sep 20 09:05:19 2004 +0000
3.3 @@ -1096,8 +1096,8 @@
3.4 public:
3.5 typedef Number ValueType;
3.6 typedef Edge KeyType;
3.7 - ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _res_graph) :
3.8 - res_graph(&_res_graph) { }
3.9 + ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
3.10 + _res_graph) : res_graph(&_res_graph) { }
3.11 Number operator[](const Edge& e) const {
3.12 if (res_graph->forward(e))
3.13 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/hugo/tight_edge_filter_map.h Mon Sep 20 09:05:19 2004 +0000
4.3 @@ -0,0 +1,46 @@
4.4 +// -*- C++ -*-
4.5 +#ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
4.6 +#define HUGO_TIGHT_EDGE_FILTER_MAP_H
4.7 +
4.8 +// /// \file
4.9 +// /// \brief Maximum flow algorithms.
4.10 +// /// \ingroup galgs
4.11 +
4.12 +namespace hugo {
4.13 +
4.14 + /// \brief A map for filtering the edge-set to those edges
4.15 + /// which are tight w.r.t. some node_potential map and
4.16 + /// edge_distance map.
4.17 + ///
4.18 + /// A node-map node_potential is said to be a potential w.r.t.
4.19 + /// an edge-map edge_distance
4.20 + /// if and only if for each edge e, node_potential[g.head(e)]
4.21 + /// <= edge_distance[e]+node_potential[g.tail(e)]
4.22 + /// (or the reverse inequality holds for each edge).
4.23 + /// An edge is said to be tight if this inequality holds with equality,
4.24 + /// and the map returns true exactly for those edges.
4.25 + /// To avoid rounding errors, it is recommended to use this class with exact
4.26 + /// types, e.g. with int.
4.27 + template<typename Graph,
4.28 + typename NodePotentialMap, typename EdgeDistanceMap>
4.29 + class TightEdgeFilterMap {
4.30 + protected:
4.31 + const Graph* g;
4.32 + NodePotentialMap* node_potential;
4.33 + EdgeDistanceMap* edge_distance;
4.34 + public:
4.35 + TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
4.36 + EdgeDistanceMap& _edge_distance) :
4.37 + g(&_g), node_potential(&_node_potential),
4.38 + edge_distance(&_edge_distance) { }
4.39 + bool operator[](const typename Graph::Edge& e) const {
4.40 + return ((*node_potential)[g->head(e)] ==
4.41 + (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
4.42 + }
4.43 + };
4.44 +
4.45 +} //namespace hugo
4.46 +
4.47 +#endif //HUGO_TIGHT_EDGE_FILTER_MAP_H
4.48 +
4.49 +
5.1 --- a/src/work/marci/augmenting_flow.h Mon Sep 20 08:27:34 2004 +0000
5.2 +++ b/src/work/marci/augmenting_flow.h Mon Sep 20 09:05:19 2004 +0000
5.3 @@ -9,7 +9,7 @@
5.4 #include <bfs_dfs.h>
5.5 #include <hugo/invalid.h>
5.6 #include <hugo/maps.h>
5.7 -#include <tight_edge_filter_map.h>
5.8 +#include <hugo/tight_edge_filter_map.h>
5.9
5.10 /// \file
5.11 /// \brief Maximum flow algorithms.
5.12 @@ -247,6 +247,8 @@
5.13 bool AugmentingFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath()
5.14 {
5.15 ResGW res_graph(*g, *capacity, *flow);
5.16 + typename ResGW::ResCap res_cap(res_graph);
5.17 +
5.18 bool _augment=false;
5.19
5.20 //ReachedMap level(res_graph);
5.21 @@ -267,9 +269,9 @@
5.22 Node w=res_graph.head(e);
5.23 pred.set(w, e);
5.24 if (pred[v]!=INVALID) {
5.25 - free.set(w, std::min(free[v], res_graph.resCap(e)));
5.26 + free.set(w, std::min(free[v], res_cap[e]));
5.27 } else {
5.28 - free.set(w, res_graph.resCap(e));
5.29 + free.set(w, res_cap[e]);
5.30 }
5.31 if (res_graph.head(e)==t) { _augment=true; break; }
5.32 }
5.33 @@ -295,6 +297,8 @@
5.34 bool AugmentingFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath2()
5.35 {
5.36 ResGW res_graph(*g, *capacity, *flow);
5.37 + typename ResGW::ResCap res_cap(res_graph);
5.38 +
5.39 bool _augment=false;
5.40
5.41 if (status!=AFTER_FAST_AUGMENTING) {
5.42 @@ -324,9 +328,9 @@
5.43 Node w=res_graph.head(e);
5.44 pred.set(w, e);
5.45 if (pred[v]!=INVALID) {
5.46 - free.set(w, std::min(free[v], res_graph.resCap(e)));
5.47 + free.set(w, std::min(free[v], res_cap[e]));
5.48 } else {
5.49 - free.set(w, res_graph.resCap(e));
5.50 + free.set(w, res_cap[e]);
5.51 }
5.52 if (res_graph.head(e)==t) { _augment=true; break; }
5.53 }
5.54 @@ -357,6 +361,7 @@
5.55 bool _augment=false;
5.56
5.57 ResGW res_graph(*g, *capacity, *flow);
5.58 + typename ResGW::ResCap res_cap(res_graph);
5.59
5.60 //bfs for distances on the residual graph
5.61 //ReachedMap level(res_graph);
5.62 @@ -392,7 +397,7 @@
5.63 //original_edge.update();
5.64 original_edge.set(f, e);
5.65 //residual_capacity.update();
5.66 - residual_capacity.set(f, res_graph.resCap(e));
5.67 + residual_capacity.set(f, res_cap[e]);
5.68 } else {
5.69 if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
5.70 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
5.71 @@ -400,7 +405,7 @@
5.72 //original_edge.update();
5.73 original_edge.set(f, e);
5.74 //residual_capacity.update();
5.75 - residual_capacity.set(f, res_graph.resCap(e));
5.76 + residual_capacity.set(f, res_cap[e]);
5.77 }
5.78 }
5.79 }
5.80 @@ -472,6 +477,7 @@
5.81 bool _augment=false;
5.82
5.83 ResGW res_graph(*g, *capacity, *flow);
5.84 + typename ResGW::ResCap res_cap(res_graph);
5.85
5.86 //Potential map, for distances from s
5.87 typename ResGW::template NodeMap<int> potential(res_graph, 0);
5.88 @@ -549,12 +555,12 @@
5.89 pred.set(w, typename ErasingResGW::Edge(dfs));
5.90 if (pred[v]!=INVALID) {
5.91 free1.set
5.92 - (w, std::min(free1[v], res_graph.resCap
5.93 - (typename ErasingResGW::Edge(dfs))));
5.94 + (w, std::min(free1[v], res_cap
5.95 + [typename ErasingResGW::Edge(dfs)]));
5.96 } else {
5.97 free1.set
5.98 - (w, res_graph.resCap
5.99 - (typename ErasingResGW::Edge(dfs)));
5.100 + (w, res_cap
5.101 + [typename ErasingResGW::Edge(dfs)]);
5.102 }
5.103
5.104 if (w==t) {
5.105 @@ -576,7 +582,7 @@
5.106 typename ErasingResGW::Edge e=pred[n];
5.107 res_graph.augment(e, augment_value);
5.108 n=erasing_res_graph.tail(e);
5.109 - if (res_graph.resCap(e)==0)
5.110 + if (res_cap[e]==0)
5.111 erasing_res_graph.erase(e);
5.112 }
5.113 }
6.1 --- a/src/work/marci/lp/lp_solver_wrapper.h Mon Sep 20 08:27:34 2004 +0000
6.2 +++ b/src/work/marci/lp/lp_solver_wrapper.h Mon Sep 20 09:05:19 2004 +0000
6.3 @@ -339,9 +339,10 @@
6.4 double lo, double up) {
6.5 lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up);
6.6 }
6.7 -// void setObjCoef(const RowIt& row_it, double obj_coef) {
6.8 -// lpx_set_obj_coef(lp, row_iter_map[row_it], obj_coef);
6.9 -// }
6.10 + ///.
6.11 + void setObjCoef(const ColIt& col_it, double obj_coef) {
6.12 + lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef);
6.13 + }
6.14 ///.
6.15 void solveSimplex() { lpx_simplex(lp); }
6.16 ///.