# HG changeset patch
# User marci
# Date 1083255903 0
# Node ID cfe5507617458d6af77d7d3c13bc08f72ccf58d8
# Parent 5fa75db9ebb4f192c6e5f3f1c9e888887b8efac0
preflow, maxflow
diff -r 5fa75db9ebb4 -r cfe550761745 src/work/jacint/preflow.h
--- a/src/work/jacint/preflow.h Thu Apr 29 16:08:16 2004 +0000
+++ b/src/work/jacint/preflow.h Thu Apr 29 16:25:03 2004 +0000
@@ -55,7 +55,7 @@
template <typename Graph, typename Num,
typename CapMap=typename Graph::template EdgeMap<Num>,
typename FlowMap=typename Graph::template EdgeMap<Num> >
- class Preflow {
+ class MaxFlow {
typedef typename Graph::Node Node;
typedef typename Graph::NodeIt NodeIt;
@@ -92,7 +92,7 @@
PREFLOW=2
};
- Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
+ MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
FlowMap& _flow) :
g(&_G), s(_s), t(_t), capacity(&_capacity),
flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
@@ -535,7 +535,7 @@
template <typename Graph, typename Num, typename CapMap, typename FlowMap>
- void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
+ void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
{
int heur0=(int)(H0*n); //time while running 'bound decrease'
@@ -644,7 +644,7 @@
template <typename Graph, typename Num, typename CapMap, typename FlowMap>
- void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
+ void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
{
int k=n-2; //bound on the highest level under n containing a node
@@ -708,7 +708,7 @@
template <typename Graph, typename Num, typename CapMap, typename FlowMap>
- bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath()
+ bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath()
{
ResGW res_graph(*g, *capacity, *flow);
bool _augment=false;
@@ -764,7 +764,7 @@
template <typename Graph, typename Num, typename CapMap, typename FlowMap>
template<typename MutableGraph>
- bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow()
+ bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow()
{
typedef MutableGraph MG;
bool _augment=false;
@@ -881,7 +881,7 @@
template <typename Graph, typename Num, typename CapMap, typename FlowMap>
- bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
+ bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
{
bool _augment=false;
diff -r 5fa75db9ebb4 -r cfe550761745 src/work/marci/bipartite_graph_wrapper_test.cc
--- a/src/work/marci/bipartite_graph_wrapper_test.cc Thu Apr 29 16:08:16 2004 +0000
+++ b/src/work/marci/bipartite_graph_wrapper_test.cc Thu Apr 29 16:25:03 2004 +0000
@@ -11,7 +11,7 @@
#include <bfs_iterator.h>
#include <graph_wrapper.h>
#include <maps.h>
-#include <edmonds_karp.h>
+#include <preflow.h>
using namespace hugo;
diff -r 5fa75db9ebb4 -r cfe550761745 src/work/marci/bipartite_matching_try.cc
--- a/src/work/marci/bipartite_matching_try.cc Thu Apr 29 16:08:16 2004 +0000
+++ b/src/work/marci/bipartite_matching_try.cc Thu Apr 29 16:25:03 2004 +0000
@@ -12,7 +12,6 @@
#include <bfs_iterator.h>
#include <graph_wrapper.h>
#include <maps.h>
-#include <edmonds_karp.h>
#include <preflow.h>
/**
@@ -180,7 +179,7 @@
ts.reset();
stGW::EdgeMap<int> pre_flow(stgw);
- Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
+ MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow/*, true*/);
pre_flow_test.run();
std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl;
diff -r 5fa75db9ebb4 -r cfe550761745 src/work/marci/lg_vs_sg.cc
--- a/src/work/marci/lg_vs_sg.cc Thu Apr 29 16:08:16 2004 +0000
+++ b/src/work/marci/lg_vs_sg.cc Thu Apr 29 16:25:03 2004 +0000
@@ -6,7 +6,6 @@
#include <list_graph.h>
#include <smart_graph.h>
#include <dimacs.h>
-#include <edmonds_karp.h>
#include <preflow.h>
#include <time_measure.h>
#include <for_each_macros.h>
@@ -34,19 +33,17 @@
Timer ts;
Graph::EdgeMap<int> flow(G); //0 flow
- Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
- pre_flow_test(G, s, t, cap, flow/*, true*/);
MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
- max_flow_test(G, s, t, cap, flow);
+ max_flow_test(G, s, t, cap, flow/*, true*/);
std::cout << "ListGraph ..." << std::endl;
{
std::cout << "preflow ..." << std::endl;
ts.reset();
- pre_flow_test.run();
+ max_flow_test.run();
std::cout << "elapsed time: " << ts << std::endl;
- std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+ std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
}
{
@@ -60,16 +57,16 @@
std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
}
- {
- std::cout << "faster physical blocking flow augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
- ts.reset();
- int i=0;
- while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
- std::cout << "elapsed time: " << ts << std::endl;
- std::cout << "number of augmentation phases: " << i << std::endl;
- std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
- }
+// {
+// std::cout << "faster physical blocking flow augmentation ..." << std::endl;
+// FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+// ts.reset();
+// int i=0;
+// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
+// std::cout << "elapsed time: " << ts << std::endl;
+// std::cout << "number of augmentation phases: " << i << std::endl;
+// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+// }
{
std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
@@ -108,10 +105,10 @@
Timer ts;
Graph::EdgeMap<int> flow(G); //0 flow
- Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
- pre_flow_test(G, s, t, cap, flow/*, true*/);
MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
- max_flow_test(G, s, t, cap, flow);
+ max_flow_test(G, s, t, cap, flow/*, true*/);
+ // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
+ // max_flow_test(G, s, t, cap, flow);
std::cout << "SmatrGraph ..." << std::endl;
@@ -119,9 +116,9 @@
std::cout << "preflow ..." << std::endl;
FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
ts.reset();
- pre_flow_test.run();
+ max_flow_test.run();
std::cout << "elapsed time: " << ts << std::endl;
- std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+ std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
}
{
@@ -135,16 +132,16 @@
std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
}
- {
- std::cout << "faster physical blocking flow augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
- ts.reset();
- int i=0;
- while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
- std::cout << "elapsed time: " << ts << std::endl;
- std::cout << "number of augmentation phases: " << i << std::endl;
- std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
- }
+// {
+// std::cout << "faster physical blocking flow augmentation ..." << std::endl;
+// FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+// ts.reset();
+// int i=0;
+// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
+// std::cout << "elapsed time: " << ts << std::endl;
+// std::cout << "number of augmentation phases: " << i << std::endl;
+// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+// }
{
std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
diff -r 5fa75db9ebb4 -r cfe550761745 src/work/marci/makefile
--- a/src/work/marci/makefile Thu Apr 29 16:08:16 2004 +0000
+++ b/src/work/marci/makefile Thu Apr 29 16:25:03 2004 +0000
@@ -4,7 +4,7 @@
INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
-BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try
+BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try
#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
include ../makefile
diff -r 5fa75db9ebb4 -r cfe550761745 src/work/marci/max_flow_demo.cc
--- a/src/work/marci/max_flow_demo.cc Thu Apr 29 16:08:16 2004 +0000
+++ b/src/work/marci/max_flow_demo.cc Thu Apr 29 16:25:03 2004 +0000
@@ -5,7 +5,6 @@
#include <list_graph.h>
#include <smart_graph.h>
#include <dimacs.h>
-//#include <edmonds_karp.h>
#include <time_measure.h>
//#include <graph_wrapper.h>
#include <preflow.h>
@@ -70,30 +69,24 @@
readDimacsMaxFlow(std::cin, G, s, t, cap);
Timer ts;
Graph::EdgeMap<int> flow(G); //0 flow
- Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
- pre_flow_test(G, s, t, cap, flow/*, true*/);
- // Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
- // pre_flow_ize(G, s, t, cap, flow/*, false*/);
-// PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
-// pre_flow_res(G, s, t, cap, flow/*, true*/);
- //MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
- // max_flow_test(G, s, t, cap, flow);
+ MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
+ max_flow_test(G, s, t, cap, flow);
{
std::cout << "preflow ..." << std::endl;
ts.reset();
- pre_flow_test.run();
+ max_flow_test.run();
std::cout << "elapsed time: " << ts << std::endl;
- std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+ std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
}
{
std::cout << "preflow ..." << std::endl;
FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
ts.reset();
- pre_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
+ max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
std::cout << "elapsed time: " << ts << std::endl;
- std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+ std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
}
// {
@@ -110,10 +103,10 @@
FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
ts.reset();
int i=0;
- while (pre_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
+ while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
std::cout << "elapsed time: " << ts << std::endl;
std::cout << "number of augmentation phases: " << i << std::endl;
- std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+ std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
}
// {
@@ -132,10 +125,10 @@
FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
ts.reset();
int i=0;
- while (pre_flow_test.augmentOnBlockingFlow2()) { ++i; }
+ while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
std::cout << "elapsed time: " << ts << std::endl;
std::cout << "number of augmentation phases: " << i << std::endl;
- std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+ std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
}
{
@@ -143,10 +136,10 @@
FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
ts.reset();
int i=0;
- while (pre_flow_test.augmentOnShortestPath()) { ++i; }
+ while (max_flow_test.augmentOnShortestPath()) { ++i; }
std::cout << "elapsed time: " << ts << std::endl;
std::cout << "number of augmentation phases: " << i << std::endl;
- std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+ std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
}