1.1 --- a/src/work/marci/edmonds_karp_demo.cc Thu Apr 15 19:01:00 2004 +0000
1.2 +++ b/src/work/marci/edmonds_karp_demo.cc Thu Apr 15 20:19:26 2004 +0000
1.3 @@ -9,6 +9,7 @@
1.4 #include <time_measure.h>
1.5 //#include <graph_wrapper.h>
1.6 #include <preflow.h>
1.7 +#include <for_each_macros.h>
1.8
1.9 using namespace hugo;
1.10
1.11 @@ -66,59 +67,27 @@
1.12 Node s, t;
1.13 Graph::EdgeMap<int> cap(G);
1.14 readDimacsMaxFlow(std::cin, G, s, t, cap);
1.15 + Timer ts;
1.16 + Graph::EdgeMap<int> flow(G); //0 flow
1.17 + Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.18 + pre_flow_test(G, s, t, cap, flow);
1.19 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.20 + max_flow_test(G, s, t, cap, flow);
1.21
1.22 {
1.23 std::cout << "preflow ..." << std::endl;
1.24 - Graph::EdgeMap<int> flow(G); //0 flow
1.25 -
1.26 - Timer ts;
1.27 ts.reset();
1.28 -
1.29 - Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.30 - max_flow_test(G, s, t, cap, flow);
1.31 - max_flow_test.run();
1.32 -// int i=0;
1.33 -// while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
1.34 -// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
1.35 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.36 -// }
1.37 -// std::cout<<std::endl;
1.38 -// ++i;
1.39 -// }
1.40 -
1.41 -// std::cout << "maximum flow: "<< std::endl;
1.42 -// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
1.43 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.44 -// }
1.45 -// std::cout<<std::endl;
1.46 + pre_flow_test.run();
1.47 std::cout << "elapsed time: " << ts << std::endl;
1.48 -// std::cout << "number of augmentation phases: " << i << std::endl;
1.49 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.50 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.51 }
1.52
1.53 {
1.54 std::cout << "physical blocking flow augmentation ..." << std::endl;
1.55 - Graph::EdgeMap<int> flow(G); //0 flow
1.56 -
1.57 - Timer ts;
1.58 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.59 ts.reset();
1.60 -
1.61 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.62 - max_flow_test(G, s, t, cap, flow);
1.63 int i=0;
1.64 - while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
1.65 -// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
1.66 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.67 -// }
1.68 -// std::cout<<std::endl;
1.69 - ++i;
1.70 - }
1.71 -
1.72 -// std::cout << "maximum flow: "<< std::endl;
1.73 -// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
1.74 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.75 -// }
1.76 -// std::cout<<std::endl;
1.77 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.78 std::cout << "elapsed time: " << ts << std::endl;
1.79 std::cout << "number of augmentation phases: " << i << std::endl;
1.80 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.81 @@ -126,27 +95,10 @@
1.82
1.83 {
1.84 std::cout << "faster physical blocking flow augmentation ..." << std::endl;
1.85 - Graph::EdgeMap<int> flow(G); //0 flow
1.86 -
1.87 - Timer ts;
1.88 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.89 ts.reset();
1.90 -
1.91 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.92 - max_flow_test(G, s, t, cap, flow);
1.93 int i=0;
1.94 - while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
1.95 -// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
1.96 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.97 -// }
1.98 -// std::cout<<std::endl;
1.99 - ++i;
1.100 - }
1.101 -
1.102 -// std::cout << "maximum flow: "<< std::endl;
1.103 -// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
1.104 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.105 -// }
1.106 -// std::cout<<std::endl;
1.107 + while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
1.108 std::cout << "elapsed time: " << ts << std::endl;
1.109 std::cout << "number of augmentation phases: " << i << std::endl;
1.110 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.111 @@ -154,27 +106,10 @@
1.112
1.113 {
1.114 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
1.115 - Graph::EdgeMap<int> flow(G); //0 flow
1.116 -
1.117 - Timer ts;
1.118 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.119 ts.reset();
1.120 -
1.121 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.122 - max_flow_test(G, s, t, cap, flow);
1.123 int i=0;
1.124 - while (max_flow_test.augmentOnBlockingFlow2()) {
1.125 -// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
1.126 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.127 -// }
1.128 -// std::cout<<std::endl;
1.129 - ++i;
1.130 - }
1.131 -
1.132 -// std::cout << "maximum flow: "<< std::endl;
1.133 -// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
1.134 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.135 -// }
1.136 -// std::cout<<std::endl;
1.137 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.138 std::cout << "elapsed time: " << ts << std::endl;
1.139 std::cout << "number of augmentation phases: " << i << std::endl;
1.140 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.141 @@ -182,27 +117,10 @@
1.142
1.143 {
1.144 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
1.145 - Graph::EdgeMap<int> flow(G); //0 flow
1.146 -
1.147 - Timer ts;
1.148 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.149 ts.reset();
1.150 -
1.151 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.152 - max_flow_test(G, s, t, cap, flow);
1.153 int i=0;
1.154 - while (max_flow_test.augmentOnShortestPath()) {
1.155 -// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
1.156 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.157 -// }
1.158 -// std::cout<<std::endl;
1.159 - ++i;
1.160 - }
1.161 -
1.162 -// std::cout << "maximum flow: "<< std::endl;
1.163 -// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
1.164 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.165 -// }
1.166 -// std::cout<<std::endl;
1.167 + while (max_flow_test.augmentOnShortestPath()) { ++i; }
1.168 std::cout << "elapsed time: " << ts << std::endl;
1.169 std::cout << "number of augmentation phases: " << i << std::endl;
1.170 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.1 --- a/src/work/marci/for_each_macros.h Thu Apr 15 19:01:00 2004 +0000
2.2 +++ b/src/work/marci/for_each_macros.h Thu Apr 15 20:19:26 2004 +0000
2.3 @@ -43,13 +43,13 @@
2.4
2.5 //FIXME ezt hogy a gorcsbe birja levezetni. Csak ugy leveszi a const-ot??
2.6 template<typename It, typename Graph>
2.7 - It loopFirst(const It& i, const Graph& g) {
2.8 - It e=i; g.first(e); return e;
2.9 + It loopFirst(const It&, const Graph& g) {
2.10 + It e; g.first(e); return e;
2.11 }
2.12
2.13 template<typename It, typename Graph, typename Node>
2.14 - It loopFirst(const It& i, const Graph& g, const Node& v) {
2.15 - It e=i; g.first(e, v); return e;
2.16 + It loopFirst(const It&, const Graph& g, const Node& v) {
2.17 + It e; g.first(e, v); return e;
2.18 }
2.19
2.20 // template<typename Graph>
2.21 @@ -71,10 +71,10 @@
2.22 // typename Graph::InEdgeIt e; g.first(e, n); return e;
2.23 // }
2.24
2.25 -#define FOR_EACH_LOC(Ittype, e, g) for(Ittype (e)=loopFirst(Ittype(), (g)); (g).valid((e)); (g).next((e)))
2.26 -#define FOR_EACH_INC_LOC(Ittype, e, g, v) for(Ittype (e)=loopFirst(Ittype(), (g), (v)); (g).valid((e)); (g).next((e)))
2.27 +#define FOR_EACH_LOC(Ittype, e, g) for(Ittype e=loopFirst(Ittype(), (g)); (g).valid(e); (g).next(e))
2.28 +#define FOR_EACH_INC_LOC(Ittype, e, g, v) for(Ittype e=loopFirst(Ittype(), (g), (v)); (g).valid(e); (g).next(e))
2.29
2.30 -// #define FOR_EACH_EDGE_LOC(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
2.31 +// #define FOR_EACH_EDGE_LOC(e, g) ezt nem tom hogy kell for((g).first((e)); (g).valid((e)); (g).next((e)))
2.32 // #define FOR_EACH_NODE_LOC(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
2.33 // #define FOR_EACH_INEDGE_LOC(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
2.34 // #define FOR_EACH_OUTEDGE_LOC(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
3.1 --- a/src/work/marci/graph_concept.h Thu Apr 15 19:01:00 2004 +0000
3.2 +++ b/src/work/marci/graph_concept.h Thu Apr 15 20:19:26 2004 +0000
3.3 @@ -364,8 +364,29 @@
3.4 GraphSkeleturo(const GraphSkeleturo &G) {}
3.5 };
3.6
3.7 - /// An empty graph class which provides a function to get the number
3.8 - /// of its nodes.
3.9 + /// An empty node-eraseable graph class.
3.10 +
3.11 + /// An empty graph class which provides a function to
3.12 + /// delete any of its nodes.
3.13 + class NodeEraseableGraphSkeleturo : public GraphSkeleturo
3.14 + {
3.15 + public:
3.16 + /// Deletes a node.
3.17 + void erase(Node n) {}
3.18 + };
3.19 +
3.20 + /// An empty edge-eraseable graph class.
3.21 +
3.22 + /// An empty graph class which provides a function to delete any
3.23 + /// of its edges.
3.24 + class EdgeEraseableGraphSkeleturo : public GraphSkeleturo
3.25 + {
3.26 + public:
3.27 + /// Deletes a node.
3.28 + void erase(Edge n) {}
3.29 + };
3.30 +
3.31 + /// An empty graph class which provides a function to get the number of its nodes.
3.32
3.33 /// This graph class provides a function for getting the number of its
3.34 /// nodes.
3.35 @@ -373,15 +394,14 @@
3.36 /// function. For wrappers or graphs which are given in an implicit way,
3.37 /// the implementation can be circumstantial, that is why this composes a
3.38 /// separate concept.
3.39 - class NodeCountingGraphSkeleturo
3.40 + class NodeCountingGraphSkeleturo : public GraphSkeleturo
3.41 {
3.42 public:
3.43 /// Returns the number of nodes.
3.44 int nodeNum() const { return 0;}
3.45 };
3.46
3.47 - /// An empty graph class which provides a function to get the number of its
3.48 - /// edges.
3.49 + /// An empty graph class which provides a function to get the number of its edges.
3.50
3.51 /// This graph class provides a function for getting the number of its
3.52 /// edges.
3.53 @@ -389,7 +409,7 @@
3.54 /// function. For wrappers or graphs which are given in an implicit way,
3.55 /// the implementation can be circumstantial, that is why this composes a
3.56 /// separate concept.
3.57 - class EdgeCountingGraphSkeleturo
3.58 + class EdgeCountingGraphSkeleturo : public GraphSkeleturo
3.59 {
3.60 public:
3.61 /// Returns the number of edges.