Changeset 944:4f064aff855e in lemon0.x for src/work/marci/bfsit_vs_byhand.cc
 Timestamp:
 10/16/04 02:20:13 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1293
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/bfsit_vs_byhand.cc
r921 r944 3 3 #include <fstream> 4 4 5 #include <sage_graph.h>5 //#include <sage_graph.h> 6 6 #include <lemon/smart_graph.h> 7 #include <lemon/list_graph.h> 7 8 #include <lemon/dimacs.h> 8 9 #include <lemon/time_measure.h> 9 10 //#include <lemon/for_each_macros.h> 10 #include <bfs_dfs.h> 11 #include <bfs_mm.h> 12 #include <lemon/bfs.h> 11 13 12 14 using namespace lemon; … … 16 18 17 19 int main() { 18 typedef SageGraph Graph; 20 // typedef SageGraph Graph; 21 typedef SmartGraph Graph ; 22 //typedef ListGraph Graph; 19 23 typedef Graph::Node Node; 20 24 typedef Graph::NodeIt NodeIt; … … 24 28 25 29 Graph g; 26 //Node s;27 //Graph::EdgeMap<int> cap(g);28 //readDimacsMaxFlow(std::cin, g, s, t, cap);29 30 readDimacs(std::cin, g); 30 NodeIt s; 31 g.first(s); 31 NodeIt s(g); 32 32 33 33 cout << g.nodeNum() << endl; … … 37 37 cout << "iteration time of bfs written by hand..." << endl; 38 38 Timer ts; 39 ts.reset(); 40 for (int i=0; i<100; ++i) 39 41 { 40 ts.reset();41 42 Graph::NodeMap<bool> reached(g); 42 43 reached.set(s, true); … … 47 48 Node v=bfs_queue.front(); 48 49 bfs_queue.pop(); 49 OutEdgeIt e; 50 for(g.first(e,v); g.valid(e); g.next(e)) { 50 for(OutEdgeIt e(g,v); e!=INVALID; ++e) { 51 51 Node w=g.head(e); 52 52 if (!reached[w]) { … … 57 57 } 58 58 } 59 60 std::cout << ts << std::endl;61 59 } 60 std::cout << ts << std::endl; 62 61 63 62 cout << "iteration time with bfs iterator..." << endl; 63 ts.reset(); 64 for (int i=0; i<100; ++i) 64 65 { 65 ts.reset();66 BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);66 Graph::NodeMap<bool> reached(g); 67 marci::BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g, reached); 67 68 bfs.pushAndSetReached(s); 68 69 pred.set(s, INVALID); 69 70 while (!bfs.finished()) { 70 71 ++bfs; 71 if ( g.valid(bfs)&& bfs.isBNodeNewlyReached())72 if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached()) 72 73 pred.set(bfs.head(), Graph::Edge(bfs)); 73 74 } 74 std::cout << ts << std::endl;75 75 } 76 std::cout << ts << std::endl; 77 78 cout << "iteration time with bfs aplar..." << endl; 79 ts.reset(); 80 for (int i=0; i<100; ++i) 81 { 82 Bfs<Graph> bfs(g); 83 bfs.setPredMap(pred); 84 bfs.run(s); 85 } 86 std::cout << ts << std::endl; 87 76 88 77 89 return 0;
Note: See TracChangeset
for help on using the changeset viewer.