1.1 --- a/src/work/marci/lp/lp_solver_wrapper.h Sat Nov 20 14:09:27 2004 +0000
1.2 +++ b/src/work/marci/lp/lp_solver_wrapper.h Sat Nov 20 14:23:27 2004 +0000
1.3 @@ -10,7 +10,9 @@
1.4 #include <stdlib.h>
1.5 // #include <stdio>
1.6 //#include <stdlib>
1.7 +extern "C" {
1.8 #include "glpk.h"
1.9 +}
1.10
1.11 #include <iostream>
1.12 #include <vector>
2.1 --- a/src/work/marci/lp/makefile Sat Nov 20 14:09:27 2004 +0000
2.2 +++ b/src/work/marci/lp/makefile Sat Nov 20 14:23:27 2004 +0000
2.3 @@ -5,7 +5,7 @@
2.4 CXXFLAGS = -g -O2 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
2.5 LDFLAGS = -L$(GLPKROOT)/lib -lglpk
2.6
2.7 -BINARIES = max_flow_by_lp sample sample2 sample11 sample15
2.8 +BINARIES = max_flow_by_lp# sample sample2 sample11 sample15
2.9
2.10 #include ../makefile
2.11
3.1 --- a/src/work/marci/lp/max_flow_by_lp.cc Sat Nov 20 14:09:27 2004 +0000
3.2 +++ b/src/work/marci/lp/max_flow_by_lp.cc Sat Nov 20 14:23:27 2004 +0000
3.3 @@ -2,15 +2,14 @@
3.4 #include <iostream>
3.5 #include <fstream>
3.6
3.7 -#include <sage_graph.h>
3.8 #include <lemon/smart_graph.h>
3.9 +#include <lemon/list_graph.h>
3.10 #include <lemon/dimacs.h>
3.11 #include <lemon/time_measure.h>
3.12 //#include <graph_wrapper.h>
3.13 -#include <lemon/max_flow.h>
3.14 +#include <lemon/preflow.h>
3.15 #include <augmenting_flow.h>
3.16 //#include <preflow_res.h>
3.17 -#include <for_each_macros.h>
3.18 #include <lp_solver_wrapper.h>
3.19
3.20 using namespace lemon;
3.21 @@ -33,9 +32,8 @@
3.22
3.23 int main(int, char **) {
3.24
3.25 - typedef SageGraph MutableGraph;
3.26 - //typedef SmartGraph Graph;
3.27 - typedef SageGraph Graph;
3.28 + typedef ListGraph MutableGraph;
3.29 + typedef SmartGraph Graph;
3.30 typedef Graph::Node Node;
3.31 typedef Graph::EdgeIt EdgeIt;
3.32
3.33 @@ -47,7 +45,7 @@
3.34 readDimacs(std::cin, g, cap, s, t);
3.35 Timer ts;
3.36 Graph::EdgeMap<int> flow(g); //0 flow
3.37 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
3.38 + Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
3.39 max_flow_test(g, s, t, cap, flow);
3.40 AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
3.41 augmenting_flow_test(g, s, t, cap, flow);
3.42 @@ -60,9 +58,9 @@
3.43 max_flow_test.run();
3.44 std::cout << "elapsed time: " << ts << std::endl;
3.45 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.46 - max_flow_test.actMinCut(cut);
3.47 + max_flow_test.minCut(cut);
3.48
3.49 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
3.50 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
3.51 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
3.52 std::cout << "Slackness does not hold!" << std::endl;
3.53 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
3.54 @@ -74,7 +72,7 @@
3.55 // std::cout << "preflow ..." << std::endl;
3.56 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
3.57 // ts.reset();
3.58 -// max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
3.59 +// max_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
3.60 // std::cout << "elapsed time: " << ts << std::endl;
3.61 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.62
3.63 @@ -97,7 +95,7 @@
3.64
3.65 {
3.66 std::cout << "physical blocking flow augmentation ..." << std::endl;
3.67 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
3.68 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
3.69 ts.reset();
3.70 int i=0;
3.71 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
3.72 @@ -105,7 +103,7 @@
3.73 std::cout << "number of augmentation phases: " << i << std::endl;
3.74 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
3.75
3.76 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
3.77 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
3.78 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
3.79 std::cout << "Slackness does not hold!" << std::endl;
3.80 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
3.81 @@ -126,7 +124,7 @@
3.82
3.83 {
3.84 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
3.85 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
3.86 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
3.87 ts.reset();
3.88 int i=0;
3.89 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
3.90 @@ -134,7 +132,7 @@
3.91 std::cout << "number of augmentation phases: " << i << std::endl;
3.92 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
3.93
3.94 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
3.95 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
3.96 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
3.97 std::cout << "Slackness does not hold!" << std::endl;
3.98 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
3.99 @@ -186,37 +184,28 @@
3.100 typedef Graph::EdgeMap<ColIt> EdgeIndexMap;
3.101 EdgeIndexMap edge_index_map(g);
3.102 PrimalMap<Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map);
3.103 - Graph::EdgeIt e;
3.104 - for (g.first(e); g.valid(e); g.next(e)) {
3.105 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
3.106 ColIt col_it=lp.addCol();
3.107 edge_index_map.set(e, col_it);
3.108 lp.setColBounds(col_it, LPX_DB, 0.0, cap[e]);
3.109 }
3.110 - Graph::NodeIt n;
3.111 - for (g.first(n); g.valid(n); g.next(n)) {
3.112 + for (Graph::NodeIt n(g); n!=INVALID; ++n) {
3.113 if (n!=s) {
3.114 //hurokelek miatt
3.115 Graph::EdgeMap<int> coeffs(g, 0);
3.116 - {
3.117 - Graph::InEdgeIt e;
3.118 - for (g.first(e, n); g.valid(e); g.next(e)) coeffs.set(e, coeffs[e]+1);
3.119 - }
3.120 - {
3.121 - Graph::OutEdgeIt e;
3.122 - for (g.first(e, n); g.valid(e); g.next(e)) coeffs.set(e, coeffs[e]-1);
3.123 - }
3.124 + for (Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
3.125 + coeffs.set(e, coeffs[e]+1);
3.126 + for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)
3.127 + coeffs.set(e, coeffs[e]-1);
3.128 if (n==t) {
3.129 - Graph::EdgeIt e;
3.130 - //std::vector< std::pair<ColIt, double> > row;
3.131 - for (g.first(e); g.valid(e); g.next(e)) {
3.132 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
3.133 if (coeffs[e]!=0)
3.134 lp.setObjCoef(edge_index_map[e], coeffs[e]);
3.135 }
3.136 } else {
3.137 RowIt row_it=lp.addRow();
3.138 - Graph::EdgeIt e;
3.139 std::vector< std::pair<ColIt, double> > row;
3.140 - for (g.first(e); g.valid(e); g.next(e)) {
3.141 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
3.142 if (coeffs[e]!=0)
3.143 row.push_back(std::make_pair(edge_index_map[e], coeffs[e]));
3.144 }