lemon-0.x: src/work/jacint/flow_test.cc@6c8adcd6b482

     1 #include <iostream>

     2 #include <vector>

     3 #include <string>

     5 #include <list_graph.hh>

     6 #include <preflow_push_hl.h>

     7 #include <preflow_push_max_flow.h>

     8 #include <reverse_bfs.h>

     9 //#include <dijkstra.h>

    11 using namespace marci;

    14 int main (int, char*[])

    15 {

    16   typedef ListGraph::NodeIt NodeIt;

    17   typedef ListGraph::EdgeIt EdgeIt;

    18   typedef ListGraph::EachNodeIt EachNodeIt;

    19   typedef ListGraph::EachEdgeIt EachEdgeIt;

    20   typedef ListGraph::OutEdgeIt OutEdgeIt;

    21   typedef ListGraph::InEdgeIt InEdgeIt;

    23   ListGraph flow_test;

    25     //Ahuja könyv példája, maxflowvalue=13

    26   NodeIt s=flow_test.addNode();

    27   NodeIt v1=flow_test.addNode();

    28   NodeIt v2=flow_test.addNode();

    29   NodeIt v3=flow_test.addNode();

    30   NodeIt v4=flow_test.addNode();

    31   NodeIt v5=flow_test.addNode();

    32   NodeIt t=flow_test.addNode();

    34   ListGraph::NodeMap<std::string> Node_name(flow_test);

    35   Node_name.set(s, "s");

    36   Node_name.set(v1, "v1");

    37   Node_name.set(v2, "v2");

    38   Node_name.set(v3, "v3");

    39   Node_name.set(v4, "v4");

    40   Node_name.set(v5, "v5");

    41   Node_name.set(t, "t");

    43   EdgeIt s_v1=flow_test.addEdge(s, v1);

    44   EdgeIt s_v2=flow_test.addEdge(s, v2);

    45   EdgeIt s_v3=flow_test.addEdge(s, v3);

    46   EdgeIt v2_v4=flow_test.addEdge(v2, v4);

    47   EdgeIt v2_v5=flow_test.addEdge(v2, v5);

    48   EdgeIt v3_v5=flow_test.addEdge(v3, v5);

    49   EdgeIt v4_t=flow_test.addEdge(v4, t);

    50   EdgeIt v5_t=flow_test.addEdge(v5, t);

    51   EdgeIt v2_s=flow_test.addEdge(v2, s);

    53    ListGraph::EdgeMap<int> cap(flow_test);

    54   cap.set(s_v1, 0);

    55   cap.set(s_v2, 10);

    56   cap.set(s_v3, 10);

    57   cap.set(v2_v4, 5);

    58   cap.set(v2_v5, 8);

    59   cap.set(v3_v5, 5);

    60   cap.set(v4_t, 8);

    61   cap.set(v5_t, 8);

    62   cap.set(v2_s, 0);

    66   //Marci példája, maxflowvalue=23

    67   /*  NodeIt s=flow_test.addNode();

    68   NodeIt v1=flow_test.addNode();

    69   NodeIt v2=flow_test.addNode();

    70   NodeIt v3=flow_test.addNode();

    71   NodeIt v4=flow_test.addNode();

    72   NodeIt t=flow_test.addNode();

    73   NodeIt w=flow_test.addNode();

    76   NodeMap<ListGraph, std::string> Node_name(flow_test);

    77   Node_name.set(s, "s");

    78   Node_name.set(v1, "v1");

    79   Node_name.set(v2, "v2");

    80   Node_name.set(v3, "v3");

    81   Node_name.set(v4, "v4");

    82   Node_name.set(t, "t");

    83   Node_name.set(w, "w");

    85   EdgeIt s_v1=flow_test.addEdge(s, v1);

    86   EdgeIt s_v2=flow_test.addEdge(s, v2);

    87   EdgeIt v1_v2=flow_test.addEdge(v1, v2);

    88   EdgeIt v2_v1=flow_test.addEdge(v2, v1);

    89   EdgeIt v1_v3=flow_test.addEdge(v1, v3);

    90   EdgeIt v3_v2=flow_test.addEdge(v3, v2);

    91   EdgeIt v2_v4=flow_test.addEdge(v2, v4);

    92   EdgeIt v4_v3=flow_test.addEdge(v4, v3);

    93   EdgeIt v3_t=flow_test.addEdge(v3, t);

    94   EdgeIt v4_t=flow_test.addEdge(v4, t);

    95   EdgeIt v3_v3=flow_test.addEdge(v3, v3);

    96   EdgeIt s_w=flow_test.addEdge(s, w);

    97   //  EdgeIt v2_s=flow_test.addEdge(v2, s);

   101   EdgeMap<ListGraph, int> cap(flow_test);  //serves as length in dijkstra

   102   cap.set(s_v1, 16);

   103   cap.set(s_v2, 13);

   104   cap.set(v1_v2, 10);

   105   cap.set(v2_v1, 4);

   106   cap.set(v1_v3, 12);

   107   cap.set(v3_v2, 9);

   108   cap.set(v2_v4, 14);

   109   cap.set(v4_v3, 7);

   110   cap.set(v3_t, 20);

   111   cap.set(v4_t, 4);

   112   cap.set(v3_v3, 4);

   113   cap.set(s_w, 4);

   114   //  cap.set(v2_s, 0);

   116 */

   118   //pelda 3, maxflowvalue=4

   119   /*      NodeIt s=flow_test.addNode();

   120   NodeIt v1=flow_test.addNode();

   121   NodeIt v2=flow_test.addNode();

   122   NodeIt t=flow_test.addNode();

   123   NodeIt w=flow_test.addNode();

   125   NodeMap<ListGraph, std::string> Node_name(flow_test);

   126   Node_name.set(s, "s");

   127   Node_name.set(v1, "v1");

   128   Node_name.set(v2, "v2");

   129   Node_name.set(t, "t");

   130   Node_name.set(w, "w");

   132   EdgeIt s_v1=flow_test.addEdge(s, v1);

   133   EdgeIt v1_v2=flow_test.addEdge(v1, v2);

   134   EdgeIt v2_t=flow_test.addEdge(v2, t);

   135   EdgeIt v1_v1=flow_test.addEdge(v1, v1);

   136   EdgeIt s_w=flow_test.addEdge(s, w);

   139   EdgeMap<ListGraph, int> cap(flow_test);

   141   cap.set(s_v1, 16);

   142   cap.set(v1_v2, 10);

   143   cap.set(v2_t, 4);

   144   cap.set(v1_v1, 3);

   145   cap.set(s_w, 5);

   146   */

   150   /*

   151   std::cout << "Testing reverse_bfs..." << std::endl;

   153   reverse_bfs<ListGraph> bfs_test(flow_test, t);

   155   bfs_test.run();

   157   for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {

   158     std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;

   159     }

   161   */

   165   std::cout << "Testing preflow_push_hl..." << std::endl;

   167   preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap);

   169   preflow_push_test.run();

   171   std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;

   173   std::cout<< "The flow on Edge s-v1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl;

   175    ListGraph::EdgeMap<int> flow=preflow_push_test.allflow();

   176   for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) {

   177     std::cout <<"Flow on Edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;

   178     }

   180   std::cout << "A minimum cut: " <<std::endl;

   181    ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut();

   183   for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {

   184       if (mincut.get(v)) std::cout <<Node_name.get(v)<< " ";

   185     }

   187   std::cout<<"\n\n"<<std::endl;

   192   std::cout << "Testing preflow_push_max_flow..." << std::endl;

   194   preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap);

   196   max_flow_test.run();

   198   std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl;

   200   std::cout << "A minimum cut: " <<std::endl;

   201    ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut();

   203   for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {

   204     if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " ";

   205   }

   207   std::cout << std::endl <<std::endl;

   210   /*

   211     std::cout << "Testing dijkstra..." << std::endl;

   213     NodeIt root=v2;

   215     dijkstra<ListGraph, int> dijkstra_test(flow_test, root, cap);

   217     dijkstra_test.run();

   219     for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {

   220       if (dijkstra_test.reach(w)) {

   221       std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w);

   222       if (dijkstra_test.pred(w).valid()) {

   223       std::cout <<", a shortest path from the root ends with Edge " << dijkstra_test.pred(w) <<std::endl;

   224       } else {

   225        std::cout <<", this is the root."<<std::endl; }

   227       } else {

   228 	cout << w << " is not reachable from " << root <<std::endl;

   229       }

   230     }

   232   */

   234   return 0;

   235 }

author	alpar
	Mon, 16 Feb 2004 16:36:12 +0000
changeset 81	6c8adcd6b482
parent 72	e560867cbe79
child 105	a3c73e9b9b2e
permissions	-rw-r--r--