Changeset 334:63703ea7d02f in lemon-0.x for src/work
- Timestamp:
- 04/15/04 22:50:03 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@453
- Location:
- src/work/marci
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/graph_concept.h
r333 r334 110 110 }; 111 111 112 /// This iterator goes trough the outgoing edges of a node.113 114 /// This iterator goes trough the \e outgoing edges of a certain node115 /// of a graph.116 /// Its usage is quite simple, for example you can count the number117 /// of outgoing edges of a node \c n118 /// in graph \c G of type \c Graph as follows.119 /// \code120 ///int count=0;121 ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;122 /// \endcode123 124 class OutEdgeIt : public Edge {125 public:126 /// @warning The default constructor sets the iterator127 /// to an undefined value.128 OutEdgeIt() {}129 /// Initialize the iterator to be invalid130 OutEdgeIt(Invalid) {}131 /// This constructor sets the iterator to first outgoing edge.132 133 /// This constructor set the iterator to the first outgoing edge of134 /// node135 ///@param n the node136 ///@param G the graph137 OutEdgeIt(const GraphSkeleturo & G, Node n) {}138 };139 140 /// This iterator goes trough the incoming edges of a node.141 142 /// This iterator goes trough the \e incoming edges of a certain node143 /// of a graph.144 /// Its usage is quite simple, for example you can count the number145 /// of outgoing edges of a node \c n146 /// in graph \c G of type \c Graph as follows.147 /// \code148 ///int count=0;149 ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;150 /// \endcode151 152 class InEdgeIt : public Edge {153 public:154 /// @warning The default constructor sets the iterator155 /// to an undefined value.156 InEdgeIt() {}157 /// Initialize the iterator to be invalid158 InEdgeIt(Invalid) {}159 InEdgeIt(const GraphSkeleturo &, Node) {}160 };161 112 // class SymEdgeIt : public Edge {}; 162 113 … … 365 316 }; 366 317 318 /// An empty out-edge-iterable graph class. 319 320 /// An empty graph class which provides a function to 321 /// iterate on out-edges of any node. 322 class OutEdgeIterableGraphSkeleturo : public GraphSkeleturo 323 { 324 public: 325 326 /// This iterator goes trough the outgoing edges of a node. 327 328 /// This iterator goes trough the \e outgoing edges of a certain node 329 /// of a graph. 330 /// Its usage is quite simple, for example you can count the number 331 /// of outgoing edges of a node \c n 332 /// in graph \c G of type \c Graph as follows. 333 /// \code 334 ///int count=0; 335 ///for(Graph::OutEdgeIt e(G,n); G.valid(e); G.next(e)) ++count; 336 /// \endcode 337 class OutEdgeIt : public Edge { 338 public: 339 /// @warning The default constructor sets the iterator 340 /// to an undefined value. 341 OutEdgeIt() {} 342 /// Initialize the iterator to be invalid 343 OutEdgeIt(Invalid) {} 344 /// This constructor sets the iterator to first outgoing edge. 345 346 /// This constructor set the iterator to the first outgoing edge of 347 /// node 348 ///@param n the node 349 ///@param G the graph 350 OutEdgeIt(const GraphSkeleturo & G, Node n) {} 351 }; 352 }; 353 354 /// An empty in-edge-iterable graph class. 355 356 /// An empty graph class which provides a function to 357 /// iterate on in-edges of any node. 358 class InEdgeIterableGraphSkeleturo : public GraphSkeleturo 359 { 360 public: 361 362 /// This iterator goes trough the incoming edges of a node. 363 364 /// This iterator goes trough the \e incoming edges of a certain node 365 /// of a graph. 366 /// Its usage is quite simple, for example you can count the number 367 /// of incoming edges of a node \c n 368 /// in graph \c G of type \c Graph as follows. 369 /// \code 370 ///int count=0; 371 ///for(Graph::InEdgeIt e(G,n); G.valid(e); G.next(e)) ++count; 372 /// \endcode 373 class InEdgeIt : public Edge { 374 public: 375 /// @warning The default constructor sets the iterator 376 /// to an undefined value. 377 InEdgeIt() {} 378 /// Initialize the iterator to be invalid 379 InEdgeIt(Invalid) {} 380 /// This constructor sets the iterator to first incomig edge. 381 382 /// This constructor set the iterator to the first incomig edge of 383 /// node 384 ///@param n the node 385 ///@param G the graph 386 InEdgeIt(const GraphSkeleturo & G, Node n) {} 387 }; 388 }; 389 390 367 391 /// An empty node-eraseable graph class. 368 392 -
src/work/marci/lg_vs_sg.cc
r174 r334 8 8 #include <dimacs.h> 9 9 #include <edmonds_karp.h> 10 #include <preflow.h> 10 11 #include <time_measure.h> 11 #include < graph_wrapper.h>12 #include <for_each_macros.h> 12 13 13 14 using namespace hugo; … … 32 33 readDimacsMaxFlow(ins, G, s, t, cap); 33 34 35 Timer ts; 36 Graph::EdgeMap<int> flow(G); //0 flow 37 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 38 pre_flow_test(G, s, t, cap, flow); 39 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 40 max_flow_test(G, s, t, cap, flow); 41 42 std::cout << "ListGraph ..." << std::endl; 43 34 44 { 35 std::cout << "ListGraph..." << std::endl; 36 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; 37 Graph::EdgeMap<int> flow(G); //0 flow 45 std::cout << "preflow ..." << std::endl; 46 ts.reset(); 47 pre_flow_test.run(); 48 std::cout << "elapsed time: " << ts << std::endl; 49 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; 50 } 38 51 39 Timer ts; 52 { 53 std::cout << "physical blocking flow augmentation ..." << std::endl; 54 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 40 55 ts.reset(); 41 42 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);43 56 int i=0; 44 57 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } 45 46 58 std::cout << "elapsed time: " << ts << std::endl; 47 59 std::cout << "number of augmentation phases: " << i << std::endl; … … 50 62 51 63 { 52 std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl; 53 Graph::EdgeMap<int> flow(G); //0 flow 54 55 Timer ts; 64 std::cout << "faster physical blocking flow augmentation ..." << std::endl; 65 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 56 66 ts.reset(); 57 58 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);59 67 int i=0; 60 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } 61 68 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } 62 69 std::cout << "elapsed time: " << ts << std::endl; 63 70 std::cout << "number of augmentation phases: " << i << std::endl; … … 66 73 67 74 { 68 std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl; 69 Graph::EdgeMap<int> flow(G); //0 flow 75 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; 76 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 77 ts.reset(); 78 int i=0; 79 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } 80 std::cout << "elapsed time: " << ts << std::endl; 81 std::cout << "number of augmentation phases: " << i << std::endl; 82 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 83 } 70 84 71 Timer ts; 85 { 86 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; 87 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 72 88 ts.reset(); 73 74 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);75 89 int i=0; 76 90 while (max_flow_test.augmentOnShortestPath()) { ++i; } 77 78 91 std::cout << "elapsed time: " << ts << std::endl; 79 92 std::cout << "number of augmentation phases: " << i << std::endl; … … 94 107 readDimacsMaxFlow(ins, G, s, t, cap); 95 108 109 Timer ts; 110 Graph::EdgeMap<int> flow(G); //0 flow 111 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 112 pre_flow_test(G, s, t, cap, flow); 113 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 114 max_flow_test(G, s, t, cap, flow); 115 116 std::cout << "SmatrGraph ..." << std::endl; 117 96 118 { 97 std::cout << "SmartGraph..." << std::endl; 98 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; 99 Graph::EdgeMap<int> flow(G); //0 flow 119 std::cout << "preflow ..." << std::endl; 120 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 121 ts.reset(); 122 pre_flow_test.run(); 123 std::cout << "elapsed time: " << ts << std::endl; 124 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; 125 } 100 126 101 Timer ts; 127 { 128 std::cout << "physical blocking flow augmentation ..." << std::endl; 129 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 102 130 ts.reset(); 103 104 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);105 131 int i=0; 106 132 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } 107 108 133 std::cout << "elapsed time: " << ts << std::endl; 109 134 std::cout << "number of augmentation phases: " << i << std::endl; … … 112 137 113 138 { 114 std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl; 115 Graph::EdgeMap<int> flow(G); //0 flow 116 117 Timer ts; 139 std::cout << "faster physical blocking flow augmentation ..." << std::endl; 140 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 118 141 ts.reset(); 119 120 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);121 142 int i=0; 122 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } 123 143 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } 124 144 std::cout << "elapsed time: " << ts << std::endl; 125 145 std::cout << "number of augmentation phases: " << i << std::endl; … … 128 148 129 149 { 130 std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl; 131 Graph::EdgeMap<int> flow(G); //0 flow 150 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; 151 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 152 ts.reset(); 153 int i=0; 154 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } 155 std::cout << "elapsed time: " << ts << std::endl; 156 std::cout << "number of augmentation phases: " << i << std::endl; 157 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 158 } 132 159 133 Timer ts; 160 { 161 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; 162 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 134 163 ts.reset(); 135 136 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);137 164 int i=0; 138 165 while (max_flow_test.augmentOnShortestPath()) { ++i; } 139 140 166 std::cout << "elapsed time: " << ts << std::endl; 141 167 std::cout << "number of augmentation phases: " << i << std::endl; … … 144 170 } 145 171 172 173 174 146 175 return 0; 147 176 } -
src/work/marci/makefile
r330 r334 12 12 CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic -ftemplate-depth-30 13 13 14 LEDABINARIES = l g_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo15 BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test 14 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo 15 BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg 16 16 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda 17 17
Note: See TracChangeset
for help on using the changeset viewer.