Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/proba.cc
changeset 38 edea2e1dc6ef
parent 23 a72cac00e274
equal deleted inserted replaced
0:ba366d9d0c3c 1:009eb5d9d098 
     6 #include <marci_graph_traits.hh>
 
     6 #include <marci_graph_traits.hh>
 
     7 #include <marci_property_vector.hh>
 
     7 #include <marci_property_vector.hh>
 
     8 #include <preflow_push_hl.hh>
 
     8 #include <preflow_push_hl.hh>
 
     9 #include <preflow_push_max_flow.hh>
 
     9 #include <preflow_push_max_flow.hh>
 
    10 #include <reverse_bfs.hh>
 
    10 #include <reverse_bfs.hh>
 
       
    11 //#include <dijkstra.hh>
 
    11 
    12 
    12 using namespace marci;
 
    13 using namespace marci;
 
    13 
    14 
    14 
    15 
    15 int main (int, char*[])
 
    16 int main (int, char*[])
 
    22   typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;
 
    23   typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;
 
    23   typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;
 
    24   typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;
 
    24 
    25 
    25   list_graph flow_test;
 
    26   list_graph flow_test;
 
    26  
    27  
    27   //Ahuja könyv példája, maxflowvalue=13
 
    28   /*  //Ahuja könyv példája, maxflowvalue=13
 
    28   node_iterator s=flow_test.add_node();
 
    29   node_iterator s=flow_test.add_node();
 
    29   node_iterator v1=flow_test.add_node();
 
    30   node_iterator v1=flow_test.add_node();
 
    30   node_iterator v2=flow_test.add_node();
 
    31   node_iterator v2=flow_test.add_node();
 
    31   node_iterator v3=flow_test.add_node();
 
    32   node_iterator v3=flow_test.add_node();
 
    32   node_iterator v4=flow_test.add_node();
 
    33   node_iterator v4=flow_test.add_node();
 
    43   node_name.put(t, "t");
 
    44   node_name.put(t, "t");
 
    44 
    45 
    45   edge_iterator s_v1=flow_test.add_edge(s, v1);
 
    46   edge_iterator s_v1=flow_test.add_edge(s, v1);
 
    46   edge_iterator s_v2=flow_test.add_edge(s, v2);
 
    47   edge_iterator s_v2=flow_test.add_edge(s, v2);
 
    47   edge_iterator s_v3=flow_test.add_edge(s, v3);
 
    48   edge_iterator s_v3=flow_test.add_edge(s, v3);
 
    48   
       
    49   edge_iterator v2_v4=flow_test.add_edge(v2, v4);
 
    49   edge_iterator v2_v4=flow_test.add_edge(v2, v4);
 
    50   edge_iterator v2_v5=flow_test.add_edge(v2, v5);
 
    50   edge_iterator v2_v5=flow_test.add_edge(v2, v5);
 
    51 
       
    52   edge_iterator v3_v5=flow_test.add_edge(v3, v5);
 
    51   edge_iterator v3_v5=flow_test.add_edge(v3, v5);
 
    53 
       
    54   edge_iterator v4_t=flow_test.add_edge(v4, t);
 
    52   edge_iterator v4_t=flow_test.add_edge(v4, t);
 
    55   edge_iterator v5_t=flow_test.add_edge(v5, t);
 
    53   edge_iterator v5_t=flow_test.add_edge(v5, t);
 
       
    54   edge_iterator v2_s=flow_test.add_edge(v2, s);
 
    56   
    55   
    57   edge_property_vector<list_graph, int> cap(flow_test);  
    56   edge_property_vector<list_graph, int> cap(flow_test);  
    58   cap.put(s_v1, 0);
 
    57   cap.put(s_v1, 0);
 
    59   cap.put(s_v2, 10);
 
    58   cap.put(s_v2, 10);
 
    60   cap.put(s_v3, 10);
 
    59   cap.put(s_v3, 10);
 
    61   cap.put(v2_v4, 5);
 
    60   cap.put(v2_v4, 5);
 
    62   cap.put(v2_v5, 8);
 
    61   cap.put(v2_v5, 8);
 
    63   cap.put(v3_v5, 5);
 
    62   cap.put(v3_v5, 5);
 
    64   cap.put(v4_t, 8);
 
    63   cap.put(v4_t, 8);
 
    65   cap.put(v5_t, 8);
 
    64   cap.put(v5_t, 8);
 
    66 
    65   cap.put(v2_s, 0);
 
       
    66 */
 
    67 
    67 
    68   
    68   
    69   //Marci példája, maxflowvalue=23
 
    69   //Marci példája, maxflowvalue=23
 
    70   /*   node_iterator s=flow_test.add_node();
 
    70      node_iterator s=flow_test.add_node();
 
    71   node_iterator v1=flow_test.add_node();
 
    71   node_iterator v1=flow_test.add_node();
 
    72   node_iterator v2=flow_test.add_node();
 
    72   node_iterator v2=flow_test.add_node();
 
    73   node_iterator v3=flow_test.add_node();
 
    73   node_iterator v3=flow_test.add_node();
 
    74   node_iterator v4=flow_test.add_node();
 
    74   node_iterator v4=flow_test.add_node();
 
    75   node_iterator t=flow_test.add_node();
 
    75   node_iterator t=flow_test.add_node();
 
    95   edge_iterator v4_v3=flow_test.add_edge(v4, v3);
 
    95   edge_iterator v4_v3=flow_test.add_edge(v4, v3);
 
    96   edge_iterator v3_t=flow_test.add_edge(v3, t);
 
    96   edge_iterator v3_t=flow_test.add_edge(v3, t);
 
    97   edge_iterator v4_t=flow_test.add_edge(v4, t);
 
    97   edge_iterator v4_t=flow_test.add_edge(v4, t);
 
    98   edge_iterator v3_v3=flow_test.add_edge(v3, v3);
 
    98   edge_iterator v3_v3=flow_test.add_edge(v3, v3);
 
    99   edge_iterator s_w=flow_test.add_edge(s, w);
 
    99   edge_iterator s_w=flow_test.add_edge(s, w);
 
       
   100   edge_iterator v2_s=flow_test.add_edge(v2, s);
 
   100   
   101   
   101 
   102 
   102 
   103 
   103   edge_property_vector<list_graph, int> cap(flow_test);  
   104   edge_property_vector<list_graph, int> cap(flow_test);  
   104   cap.put(s_v1, 16);
 
   105   cap.put(s_v1, 16);
 
   111   cap.put(v4_v3, 7);
 
   112   cap.put(v4_v3, 7);
 
   112   cap.put(v3_t, 20);
 
   113   cap.put(v3_t, 20);
 
   113   cap.put(v4_t, 4);
 
   114   cap.put(v4_t, 4);
 
   114   cap.put(v3_v3, 4);
 
   115   cap.put(v3_v3, 4);
 
   115   cap.put(s_w, 4);
 
   116   cap.put(s_w, 4);
 
   116   */
 
   117   cap.put(v2_s, 0);
 
   117 
   118 
   118 
   119 
   119   //pelda 3, maxflowvalue=4
 
   120   //pelda 3, maxflowvalue=4
 
   120   /*    node_iterator s=flow_test.add_node();
 
   121   /*    node_iterator s=flow_test.add_node();
 
   121   node_iterator v1=flow_test.add_node();
 
   122   node_iterator v1=flow_test.add_node();
 
   153   
   154   
   154   reverse_bfs<list_graph> bfs_test(flow_test, t);
 
   155   reverse_bfs<list_graph> bfs_test(flow_test, t);
 
   155 
   156 
   156   bfs_test.run();
 
   157   bfs_test.run();
 
   157 
   158 
   158   for (each_node_iterator w=flow_test.first_node(); w.is_valid(); ++w) {
 
   159   for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
 
   159     std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
 
   160     std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
 
   160     }
 
   161     }
 
   161 
   162 
   162 
   163 
   163 
   164 
   172   std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;
 
   173   std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;
 
   173 
   174 
   174   std::cout<< "The flow on edge s-v1 is "<< preflow_push_test.flowonedge(s_v1) << "."<<std::endl;
 
   175   std::cout<< "The flow on edge s-v1 is "<< preflow_push_test.flowonedge(s_v1) << "."<<std::endl;
 
   175 
   176 
   176   edge_property_vector<list_graph, int> flow=preflow_push_test.allflow();  
   177   edge_property_vector<list_graph, int> flow=preflow_push_test.allflow();  
   177   for (each_edge_iterator e=flow_test.first_edge(); e.is_valid(); ++e) {
 
   178   for (each_edge_iterator e=flow_test.first_edge(); e.valid(); ++e) {
 
   178     std::cout <<"Flow on edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
 
   179     std::cout <<"Flow on edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
 
   179     }
 
   180     }
 
   180 
   181 
   181   std::cout << "A minimum cut: " <<std::endl;  
   182   std::cout << "A minimum cut: " <<std::endl;  
   182   node_property_vector<list_graph, bool> mincut=preflow_push_test.mincut();
 
   183   node_property_vector<list_graph, bool> mincut=preflow_push_test.mincut();
 
   183 
   184 
   184   for (each_node_iterator v=flow_test.first_node(); v.is_valid(); ++v) {
 
   185   for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
 
   185       if (mincut.get(v)) std::cout <<node_name.get(v)<< " ";
 
   186       if (mincut.get(v)) std::cout <<node_name.get(v)<< " ";
 
   186     }
 
   187     }
 
   187   
   188   
   188   std::cout<<"\n\n"<<std::endl;
 
   189   std::cout<<"\n\n"<<std::endl;
 
   189 
   190 
   199   std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl;
 
   200   std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl;
 
   200 
   201 
   201   std::cout << "A minimum cut: " <<std::endl;  
   202   std::cout << "A minimum cut: " <<std::endl;  
   202   node_property_vector<list_graph, bool> mincut2=max_flow_test.mincut();
 
   203   node_property_vector<list_graph, bool> mincut2=max_flow_test.mincut();
 
   203 
   204 
   204   for (each_node_iterator v=flow_test.first_node(); v.is_valid(); ++v) {
 
   205   for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
 
   205     if (mincut2.get(v)) std::cout <<node_name.get(v)<< " ";
 
   206     if (mincut2.get(v)) std::cout <<node_name.get(v)<< " ";
 
   206   }
 
   207   }
 
   207   
   208   
   208   std::cout << std::endl;
 
   209   std::cout << std::endl;
 
   209 
   210 
   210 
   211 
   211 
   212 
       
   213 //    std::cout << "Testing dijkstra..." << std::endl;
 
       
   214   
       
   215 //    dijkstra<list_graph, int> dijkstra_test(flow_test, s, cap);
 
       
   216 
       
   217 //    dijkstra_test.run();
 
       
   218 
       
   219 //    for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
 
       
   220 //      std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w) <<std::endl;
 
       
   221 //      }
 
       
   222 
       
   223 
       
   224 
       
   225 
   212   return 0;
 
   226   return 0;
 
   213 }
 
   227 }
 
   214 
   228 
   215 
   229 
   216 
   230
lemon-0.x