Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/lg_vs_sg.cc
changeset 607 327f7cf13843
parent 555 995bc1f1a3ce
child 640 d426dca0aaf7
equal deleted inserted replaced
6:0d2981d370fc 7:30025afaaa61 
    23   {
 
    23   {
 
    24     typedef ListGraph Graph;
 
    24     typedef ListGraph Graph;
 
    25     typedef Graph::Node Node;
 
    25     typedef Graph::Node Node;
 
    26     typedef Graph::EdgeIt EdgeIt;
 
    26     typedef Graph::EdgeIt EdgeIt;
 
    27 
    27 
    28     Graph G;
 
    28     Graph g;
 
    29     Node s, t;
 
    29     Node s, t;
 
    30     Graph::EdgeMap<int> cap(G);
 
    30     Graph::EdgeMap<int> cap(g);
 
    31     std::ifstream ins(in.c_str());
 
    31     std::ifstream ins(in.c_str());
 
    32     readDimacsMaxFlow(ins, G, s, t, cap);
 
    32     //readDimacsMaxFlow(ins, g, s, t, cap);
 
       
    33     readDimacs(ins, g, cap, s, t);
 
    33 
    34 
    34     Timer ts;
 
    35     Timer ts;
 
    35     Graph::EdgeMap<int> flow(G); //0 flow
 
    36     Graph::EdgeMap<int> flow(g); //0 flow
 
    36     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    37     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    37       max_flow_test(G, s, t, cap, flow/*, true*/);
 
    38       max_flow_test(g, s, t, cap, flow/*, true*/);
 
    38 
    39 
    39     std::cout << "ListGraph ..." << std::endl;
 
    40     std::cout << "ListGraph ..." << std::endl;
 
    40 
    41 
    41     {
 
    42     {
 
    42       std::cout << "preflow ..." << std::endl;
 
    43       std::cout << "preflow ..." << std::endl;
 
    46       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    47       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    47     }
 
    48     }
 
    48 
    49 
    49     {
 
    50     {
 
    50       std::cout << "physical blocking flow augmentation ..." << std::endl;
 
    51       std::cout << "physical blocking flow augmentation ..." << std::endl;
 
    51       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    52       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 
    52       ts.reset();
 
    53       ts.reset();
 
    53       int i=0;
 
    54       int i=0;
 
    54       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
 
    55       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
 
    55       std::cout << "elapsed time: " << ts << std::endl;
 
    56       std::cout << "elapsed time: " << ts << std::endl;
 
    56       std::cout << "number of augmentation phases: " << i << std::endl; 
    57       std::cout << "number of augmentation phases: " << i << std::endl; 
    57       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    58       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    58     }
 
    59     }
 
    59 
    60 
    60 //     {
 
    61 //     {
 
    61 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
 
    62 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
 
    62 //       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    63 //       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 
    63 //       ts.reset();
 
    64 //       ts.reset();
 
    64 //       int i=0;
 
    65 //       int i=0;
 
    65 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
 
    66 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
 
    66 //       std::cout << "elapsed time: " << ts << std::endl;
 
    67 //       std::cout << "elapsed time: " << ts << std::endl;
 
    67 //       std::cout << "number of augmentation phases: " << i << std::endl; 
    68 //       std::cout << "number of augmentation phases: " << i << std::endl; 
    68 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    69 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    69 //     }
 
    70 //     }
 
    70 
    71 
    71     {
 
    72     {
 
    72       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
 
    73       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
 
    73       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    74       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 
    74       ts.reset();
 
    75       ts.reset();
 
    75       int i=0;
 
    76       int i=0;
 
    76       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
 
    77       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
 
    77       std::cout << "elapsed time: " << ts << std::endl;
 
    78       std::cout << "elapsed time: " << ts << std::endl;
 
    78       std::cout << "number of augmentation phases: " << i << std::endl; 
    79       std::cout << "number of augmentation phases: " << i << std::endl; 
    79       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    80       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    80     }
 
    81     }
 
    81 
    82 
    82     {
 
    83     {
 
    83       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
 
    84       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
 
    84       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    85       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 
    85       ts.reset();
 
    86       ts.reset();
 
    86       int i=0;
 
    87       int i=0;
 
    87       while (max_flow_test.augmentOnShortestPath()) { ++i; }
 
    88       while (max_flow_test.augmentOnShortestPath()) { ++i; }
 
    88       std::cout << "elapsed time: " << ts << std::endl;
 
    89       std::cout << "elapsed time: " << ts << std::endl;
 
    89       std::cout << "number of augmentation phases: " << i << std::endl; 
    90       std::cout << "number of augmentation phases: " << i << std::endl; 
    95   {
 
    96   {
 
    96     typedef SmartGraph Graph;
 
    97     typedef SmartGraph Graph;
 
    97     typedef Graph::Node Node;
 
    98     typedef Graph::Node Node;
 
    98     typedef Graph::EdgeIt EdgeIt;
 
    99     typedef Graph::EdgeIt EdgeIt;
 
    99 
   100 
   100     Graph G;
 
   101     Graph g;
 
   101     Node s, t;
 
   102     Node s, t;
 
   102     Graph::EdgeMap<int> cap(G);
 
   103     Graph::EdgeMap<int> cap(g);
 
   103     std::ifstream ins(in.c_str());
 
   104     std::ifstream ins(in.c_str());
 
   104     readDimacsMaxFlow(ins, G, s, t, cap);
 
   105     //readDimacsMaxFlow(ins, g, s, t, cap);
 
       
   106     readDimacs(ins, g, cap, s, t);
 
   105 
   107 
   106     Timer ts;
 
   108     Timer ts;
 
   107     Graph::EdgeMap<int> flow(G); //0 flow
 
   109     Graph::EdgeMap<int> flow(g); //0 flow
 
   108     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
   110     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
   109       max_flow_test(G, s, t, cap, flow/*, true*/);
 
   111       max_flow_test(g, s, t, cap, flow/*, true*/);
 
   110     //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
   112     //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
   111     //  max_flow_test(G, s, t, cap, flow);
 
   113     //  max_flow_test(g, s, t, cap, flow);
 
   112 
   114 
   113     std::cout << "SmatrGraph ..." << std::endl;
 
   115     std::cout << "SmatrGraph ..." << std::endl;
 
   114 
   116 
   115     {
 
   117     {
 
   116       std::cout << "preflow ..." << std::endl;
 
   118       std::cout << "preflow ..." << std::endl;
 
   117       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   119       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 
   118       ts.reset();
 
   120       ts.reset();
 
   119       max_flow_test.run();
 
   121       max_flow_test.run();
 
   120       std::cout << "elapsed time: " << ts << std::endl;
 
   122       std::cout << "elapsed time: " << ts << std::endl;
 
   121       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   123       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   122     }
 
   124     }
 
   123 
   125 
   124     {
 
   126     {
 
   125       std::cout << "physical blocking flow augmentation ..." << std::endl;
 
   127       std::cout << "physical blocking flow augmentation ..." << std::endl;
 
   126       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   128       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 
   127       ts.reset();
 
   129       ts.reset();
 
   128       int i=0;
 
   130       int i=0;
 
   129       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
 
   131       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
 
   130       std::cout << "elapsed time: " << ts << std::endl;
 
   132       std::cout << "elapsed time: " << ts << std::endl;
 
   131       std::cout << "number of augmentation phases: " << i << std::endl; 
   133       std::cout << "number of augmentation phases: " << i << std::endl; 
   132       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   134       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   133     }
 
   135     }
 
   134 
   136 
   135 //     {
 
   137 //     {
 
   136 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
 
   138 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
 
   137 //       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   139 //       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 
   138 //       ts.reset();
 
   140 //       ts.reset();
 
   139 //       int i=0;
 
   141 //       int i=0;
 
   140 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
 
   142 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
 
   141 //       std::cout << "elapsed time: " << ts << std::endl;
 
   143 //       std::cout << "elapsed time: " << ts << std::endl;
 
   142 //       std::cout << "number of augmentation phases: " << i << std::endl; 
   144 //       std::cout << "number of augmentation phases: " << i << std::endl; 
   143 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   145 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   144 //     }
 
   146 //     }
 
   145 
   147 
   146     {
 
   148     {
 
   147       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
 
   149       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
 
   148       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   150       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 
   149       ts.reset();
 
   151       ts.reset();
 
   150       int i=0;
 
   152       int i=0;
 
   151       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
 
   153       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
 
   152       std::cout << "elapsed time: " << ts << std::endl;
 
   154       std::cout << "elapsed time: " << ts << std::endl;
 
   153       std::cout << "number of augmentation phases: " << i << std::endl; 
   155       std::cout << "number of augmentation phases: " << i << std::endl; 
   154       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   156       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   155     }
 
   157     }
 
   156 
   158 
   157     {
 
   159     {
 
   158       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
 
   160       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
 
   159       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   161       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 
   160       ts.reset();
 
   162       ts.reset();
 
   161       int i=0;
 
   163       int i=0;
 
   162       while (max_flow_test.augmentOnShortestPath()) { ++i; }
 
   164       while (max_flow_test.augmentOnShortestPath()) { ++i; }
 
   163       std::cout << "elapsed time: " << ts << std::endl;
 
   165       std::cout << "elapsed time: " << ts << std::endl;
 
   164       std::cout << "number of augmentation phases: " << i << std::endl; 
   166       std::cout << "number of augmentation phases: " << i << std::endl;
lemon-0.x