# HG changeset patch
# User marci
# Date 1100960607 0
# Node ID aae850a2394d52ea658c41cdb4a6c4144b081f90
# Parent b3bdd856faf43a606e175669849e83087a9d84c7
Modifications for hugo 0.2
diff -r b3bdd856faf4 -r aae850a2394d src/work/marci/lp/lp_solver_wrapper.h
--- a/src/work/marci/lp/lp_solver_wrapper.h Sat Nov 20 14:09:27 2004 +0000
+++ b/src/work/marci/lp/lp_solver_wrapper.h Sat Nov 20 14:23:27 2004 +0000
@@ -10,7 +10,9 @@
#include <stdlib.h>
// #include <stdio>
//#include <stdlib>
+extern "C" {
#include "glpk.h"
+}
#include <iostream>
#include <vector>
diff -r b3bdd856faf4 -r aae850a2394d src/work/marci/lp/makefile
--- a/src/work/marci/lp/makefile Sat Nov 20 14:09:27 2004 +0000
+++ b/src/work/marci/lp/makefile Sat Nov 20 14:23:27 2004 +0000
@@ -5,7 +5,7 @@
CXXFLAGS = -g -O2 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
LDFLAGS = -L$(GLPKROOT)/lib -lglpk
-BINARIES = max_flow_by_lp sample sample2 sample11 sample15
+BINARIES = max_flow_by_lp# sample sample2 sample11 sample15
#include ../makefile
diff -r b3bdd856faf4 -r aae850a2394d src/work/marci/lp/max_flow_by_lp.cc
--- a/src/work/marci/lp/max_flow_by_lp.cc Sat Nov 20 14:09:27 2004 +0000
+++ b/src/work/marci/lp/max_flow_by_lp.cc Sat Nov 20 14:23:27 2004 +0000
@@ -2,15 +2,14 @@
#include <iostream>
#include <fstream>
-#include <sage_graph.h>
#include <lemon/smart_graph.h>
+#include <lemon/list_graph.h>
#include <lemon/dimacs.h>
#include <lemon/time_measure.h>
//#include <graph_wrapper.h>
-#include <lemon/max_flow.h>
+#include <lemon/preflow.h>
#include <augmenting_flow.h>
//#include <preflow_res.h>
-#include <for_each_macros.h>
#include <lp_solver_wrapper.h>
using namespace lemon;
@@ -33,9 +32,8 @@
int main(int, char **) {
- typedef SageGraph MutableGraph;
- //typedef SmartGraph Graph;
- typedef SageGraph Graph;
+ typedef ListGraph MutableGraph;
+ typedef SmartGraph Graph;
typedef Graph::Node Node;
typedef Graph::EdgeIt EdgeIt;
@@ -47,7 +45,7 @@
readDimacs(std::cin, g, cap, s, t);
Timer ts;
Graph::EdgeMap<int> flow(g); //0 flow
- MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
+ Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
max_flow_test(g, s, t, cap, flow);
AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
augmenting_flow_test(g, s, t, cap, flow);
@@ -60,9 +58,9 @@
max_flow_test.run();
std::cout << "elapsed time: " << ts << std::endl;
std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
- max_flow_test.actMinCut(cut);
+ max_flow_test.minCut(cut);
- FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
std::cout << "Slackness does not hold!" << std::endl;
if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
@@ -74,7 +72,7 @@
// std::cout << "preflow ..." << std::endl;
// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
// ts.reset();
-// max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
+// max_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
// std::cout << "elapsed time: " << ts << std::endl;
// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
@@ -97,7 +95,7 @@
{
std::cout << "physical blocking flow augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
@@ -105,7 +103,7 @@
std::cout << "number of augmentation phases: " << i << std::endl;
std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
std::cout << "Slackness does not hold!" << std::endl;
if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
@@ -126,7 +124,7 @@
{
std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
@@ -134,7 +132,7 @@
std::cout << "number of augmentation phases: " << i << std::endl;
std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
std::cout << "Slackness does not hold!" << std::endl;
if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
@@ -186,37 +184,28 @@
typedef Graph::EdgeMap<ColIt> EdgeIndexMap;
EdgeIndexMap edge_index_map(g);
PrimalMap<Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map);
- Graph::EdgeIt e;
- for (g.first(e); g.valid(e); g.next(e)) {
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
ColIt col_it=lp.addCol();
edge_index_map.set(e, col_it);
lp.setColBounds(col_it, LPX_DB, 0.0, cap[e]);
}
- Graph::NodeIt n;
- for (g.first(n); g.valid(n); g.next(n)) {
+ for (Graph::NodeIt n(g); n!=INVALID; ++n) {
if (n!=s) {
//hurokelek miatt
Graph::EdgeMap<int> coeffs(g, 0);
- {
- Graph::InEdgeIt e;
- for (g.first(e, n); g.valid(e); g.next(e)) coeffs.set(e, coeffs[e]+1);
- }
- {
- Graph::OutEdgeIt e;
- for (g.first(e, n); g.valid(e); g.next(e)) coeffs.set(e, coeffs[e]-1);
- }
+ for (Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
+ coeffs.set(e, coeffs[e]+1);
+ for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)
+ coeffs.set(e, coeffs[e]-1);
if (n==t) {
- Graph::EdgeIt e;
- //std::vector< std::pair<ColIt, double> > row;
- for (g.first(e); g.valid(e); g.next(e)) {
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
if (coeffs[e]!=0)
lp.setObjCoef(edge_index_map[e], coeffs[e]);
}
} else {
RowIt row_it=lp.addRow();
- Graph::EdgeIt e;
std::vector< std::pair<ColIt, double> > row;
- for (g.first(e); g.valid(e); g.next(e)) {
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
if (coeffs[e]!=0)
row.push_back(std::make_pair(edge_index_map[e], coeffs[e]));
}