1.1 --- a/src/work/marci/graph_concept.h Thu Apr 15 20:19:26 2004 +0000
1.2 +++ b/src/work/marci/graph_concept.h Thu Apr 15 20:50:03 2004 +0000
1.3 @@ -109,55 +109,6 @@
1.4 bool operator<(Edge n) const { return true; }
1.5 };
1.6
1.7 - /// This iterator goes trough the outgoing edges of a node.
1.8 -
1.9 - /// This iterator goes trough the \e outgoing edges of a certain node
1.10 - /// of a graph.
1.11 - /// Its usage is quite simple, for example you can count the number
1.12 - /// of outgoing edges of a node \c n
1.13 - /// in graph \c G of type \c Graph as follows.
1.14 - /// \code
1.15 - ///int count=0;
1.16 - ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
1.17 - /// \endcode
1.18 -
1.19 - class OutEdgeIt : public Edge {
1.20 - public:
1.21 - /// @warning The default constructor sets the iterator
1.22 - /// to an undefined value.
1.23 - OutEdgeIt() {}
1.24 - /// Initialize the iterator to be invalid
1.25 - OutEdgeIt(Invalid) {}
1.26 - /// This constructor sets the iterator to first outgoing edge.
1.27 -
1.28 - /// This constructor set the iterator to the first outgoing edge of
1.29 - /// node
1.30 - ///@param n the node
1.31 - ///@param G the graph
1.32 - OutEdgeIt(const GraphSkeleturo & G, Node n) {}
1.33 - };
1.34 -
1.35 - /// This iterator goes trough the incoming edges of a node.
1.36 -
1.37 - /// This iterator goes trough the \e incoming edges of a certain node
1.38 - /// of a graph.
1.39 - /// Its usage is quite simple, for example you can count the number
1.40 - /// of outgoing edges of a node \c n
1.41 - /// in graph \c G of type \c Graph as follows.
1.42 - /// \code
1.43 - ///int count=0;
1.44 - ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
1.45 - /// \endcode
1.46 -
1.47 - class InEdgeIt : public Edge {
1.48 - public:
1.49 - /// @warning The default constructor sets the iterator
1.50 - /// to an undefined value.
1.51 - InEdgeIt() {}
1.52 - /// Initialize the iterator to be invalid
1.53 - InEdgeIt(Invalid) {}
1.54 - InEdgeIt(const GraphSkeleturo &, Node) {}
1.55 - };
1.56 // class SymEdgeIt : public Edge {};
1.57
1.58 /// This iterator goes through each edge.
1.59 @@ -364,6 +315,79 @@
1.60 GraphSkeleturo(const GraphSkeleturo &G) {}
1.61 };
1.62
1.63 + /// An empty out-edge-iterable graph class.
1.64 +
1.65 + /// An empty graph class which provides a function to
1.66 + /// iterate on out-edges of any node.
1.67 + class OutEdgeIterableGraphSkeleturo : public GraphSkeleturo
1.68 + {
1.69 + public:
1.70 +
1.71 + /// This iterator goes trough the outgoing edges of a node.
1.72 +
1.73 + /// This iterator goes trough the \e outgoing edges of a certain node
1.74 + /// of a graph.
1.75 + /// Its usage is quite simple, for example you can count the number
1.76 + /// of outgoing edges of a node \c n
1.77 + /// in graph \c G of type \c Graph as follows.
1.78 + /// \code
1.79 + ///int count=0;
1.80 + ///for(Graph::OutEdgeIt e(G,n); G.valid(e); G.next(e)) ++count;
1.81 + /// \endcode
1.82 + class OutEdgeIt : public Edge {
1.83 + public:
1.84 + /// @warning The default constructor sets the iterator
1.85 + /// to an undefined value.
1.86 + OutEdgeIt() {}
1.87 + /// Initialize the iterator to be invalid
1.88 + OutEdgeIt(Invalid) {}
1.89 + /// This constructor sets the iterator to first outgoing edge.
1.90 +
1.91 + /// This constructor set the iterator to the first outgoing edge of
1.92 + /// node
1.93 + ///@param n the node
1.94 + ///@param G the graph
1.95 + OutEdgeIt(const GraphSkeleturo & G, Node n) {}
1.96 + };
1.97 + };
1.98 +
1.99 + /// An empty in-edge-iterable graph class.
1.100 +
1.101 + /// An empty graph class which provides a function to
1.102 + /// iterate on in-edges of any node.
1.103 + class InEdgeIterableGraphSkeleturo : public GraphSkeleturo
1.104 + {
1.105 + public:
1.106 +
1.107 + /// This iterator goes trough the incoming edges of a node.
1.108 +
1.109 + /// This iterator goes trough the \e incoming edges of a certain node
1.110 + /// of a graph.
1.111 + /// Its usage is quite simple, for example you can count the number
1.112 + /// of incoming edges of a node \c n
1.113 + /// in graph \c G of type \c Graph as follows.
1.114 + /// \code
1.115 + ///int count=0;
1.116 + ///for(Graph::InEdgeIt e(G,n); G.valid(e); G.next(e)) ++count;
1.117 + /// \endcode
1.118 + class InEdgeIt : public Edge {
1.119 + public:
1.120 + /// @warning The default constructor sets the iterator
1.121 + /// to an undefined value.
1.122 + InEdgeIt() {}
1.123 + /// Initialize the iterator to be invalid
1.124 + InEdgeIt(Invalid) {}
1.125 + /// This constructor sets the iterator to first incomig edge.
1.126 +
1.127 + /// This constructor set the iterator to the first incomig edge of
1.128 + /// node
1.129 + ///@param n the node
1.130 + ///@param G the graph
1.131 + InEdgeIt(const GraphSkeleturo & G, Node n) {}
1.132 + };
1.133 + };
1.134 +
1.135 +
1.136 /// An empty node-eraseable graph class.
1.137
1.138 /// An empty graph class which provides a function to
2.1 --- a/src/work/marci/lg_vs_sg.cc Thu Apr 15 20:19:26 2004 +0000
2.2 +++ b/src/work/marci/lg_vs_sg.cc Thu Apr 15 20:50:03 2004 +0000
2.3 @@ -7,8 +7,9 @@
2.4 #include <smart_graph.h>
2.5 #include <dimacs.h>
2.6 #include <edmonds_karp.h>
2.7 +#include <preflow.h>
2.8 #include <time_measure.h>
2.9 -#include <graph_wrapper.h>
2.10 +#include <for_each_macros.h>
2.11
2.12 using namespace hugo;
2.13
2.14 @@ -31,50 +32,62 @@
2.15 std::ifstream ins(in.c_str());
2.16 readDimacsMaxFlow(ins, G, s, t, cap);
2.17
2.18 + Timer ts;
2.19 + Graph::EdgeMap<int> flow(G); //0 flow
2.20 + Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
2.21 + pre_flow_test(G, s, t, cap, flow);
2.22 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
2.23 + max_flow_test(G, s, t, cap, flow);
2.24 +
2.25 + std::cout << "ListGraph ..." << std::endl;
2.26 +
2.27 {
2.28 - std::cout << "ListGraph..." << std::endl;
2.29 - std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
2.30 - Graph::EdgeMap<int> flow(G); //0 flow
2.31 + std::cout << "preflow ..." << std::endl;
2.32 + ts.reset();
2.33 + pre_flow_test.run();
2.34 + std::cout << "elapsed time: " << ts << std::endl;
2.35 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
2.36 + }
2.37
2.38 - Timer ts;
2.39 + {
2.40 + std::cout << "physical blocking flow augmentation ..." << std::endl;
2.41 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.42 ts.reset();
2.43 -
2.44 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.45 int i=0;
2.46 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
2.47 -
2.48 std::cout << "elapsed time: " << ts << std::endl;
2.49 std::cout << "number of augmentation phases: " << i << std::endl;
2.50 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.51 }
2.52
2.53 {
2.54 - std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
2.55 - Graph::EdgeMap<int> flow(G); //0 flow
2.56 -
2.57 - Timer ts;
2.58 + std::cout << "faster physical blocking flow augmentation ..." << std::endl;
2.59 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.60 ts.reset();
2.61 -
2.62 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.63 int i=0;
2.64 - while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
2.65 -
2.66 + while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
2.67 std::cout << "elapsed time: " << ts << std::endl;
2.68 std::cout << "number of augmentation phases: " << i << std::endl;
2.69 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.70 }
2.71
2.72 {
2.73 - std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
2.74 - Graph::EdgeMap<int> flow(G); //0 flow
2.75 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
2.76 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.77 + ts.reset();
2.78 + int i=0;
2.79 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
2.80 + std::cout << "elapsed time: " << ts << std::endl;
2.81 + std::cout << "number of augmentation phases: " << i << std::endl;
2.82 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.83 + }
2.84
2.85 - Timer ts;
2.86 + {
2.87 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
2.88 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.89 ts.reset();
2.90 -
2.91 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.92 int i=0;
2.93 while (max_flow_test.augmentOnShortestPath()) { ++i; }
2.94 -
2.95 std::cout << "elapsed time: " << ts << std::endl;
2.96 std::cout << "number of augmentation phases: " << i << std::endl;
2.97 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.98 @@ -93,55 +106,71 @@
2.99 std::ifstream ins(in.c_str());
2.100 readDimacsMaxFlow(ins, G, s, t, cap);
2.101
2.102 + Timer ts;
2.103 + Graph::EdgeMap<int> flow(G); //0 flow
2.104 + Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
2.105 + pre_flow_test(G, s, t, cap, flow);
2.106 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
2.107 + max_flow_test(G, s, t, cap, flow);
2.108 +
2.109 + std::cout << "SmatrGraph ..." << std::endl;
2.110 +
2.111 {
2.112 - std::cout << "SmartGraph..." << std::endl;
2.113 - std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
2.114 - Graph::EdgeMap<int> flow(G); //0 flow
2.115 + std::cout << "preflow ..." << std::endl;
2.116 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.117 + ts.reset();
2.118 + pre_flow_test.run();
2.119 + std::cout << "elapsed time: " << ts << std::endl;
2.120 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
2.121 + }
2.122
2.123 - Timer ts;
2.124 + {
2.125 + std::cout << "physical blocking flow augmentation ..." << std::endl;
2.126 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.127 ts.reset();
2.128 -
2.129 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.130 int i=0;
2.131 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
2.132 -
2.133 std::cout << "elapsed time: " << ts << std::endl;
2.134 std::cout << "number of augmentation phases: " << i << std::endl;
2.135 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.136 }
2.137
2.138 {
2.139 - std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
2.140 - Graph::EdgeMap<int> flow(G); //0 flow
2.141 -
2.142 - Timer ts;
2.143 + std::cout << "faster physical blocking flow augmentation ..." << std::endl;
2.144 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.145 ts.reset();
2.146 -
2.147 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.148 int i=0;
2.149 - while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
2.150 -
2.151 + while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
2.152 std::cout << "elapsed time: " << ts << std::endl;
2.153 std::cout << "number of augmentation phases: " << i << std::endl;
2.154 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.155 }
2.156
2.157 {
2.158 - std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
2.159 - Graph::EdgeMap<int> flow(G); //0 flow
2.160 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
2.161 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.162 + ts.reset();
2.163 + int i=0;
2.164 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
2.165 + std::cout << "elapsed time: " << ts << std::endl;
2.166 + std::cout << "number of augmentation phases: " << i << std::endl;
2.167 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.168 + }
2.169
2.170 - Timer ts;
2.171 + {
2.172 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
2.173 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.174 ts.reset();
2.175 -
2.176 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.177 int i=0;
2.178 while (max_flow_test.augmentOnShortestPath()) { ++i; }
2.179 -
2.180 std::cout << "elapsed time: " << ts << std::endl;
2.181 std::cout << "number of augmentation phases: " << i << std::endl;
2.182 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.183 }
2.184 }
2.185
2.186 +
2.187 +
2.188 +
2.189 return 0;
2.190 }
3.1 --- a/src/work/marci/makefile Thu Apr 15 20:19:26 2004 +0000
3.2 +++ b/src/work/marci/makefile Thu Apr 15 20:50:03 2004 +0000
3.3 @@ -11,8 +11,8 @@
3.4 LEDAINCLUDE ?= -I$(LEDAROOT)/incl
3.5 CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic -ftemplate-depth-30
3.6
3.7 -LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
3.8 -BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test
3.9 +LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
3.10 +BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg
3.11 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
3.12
3.13 all: $(BINARIES)