lemon-0.x: src/work/jacint/edmonds.cc@22ce98f7d0f1

     1 #include <iostream>

     2 #include <vector>

     3 #include <string>

     5 #include <list_graph.h>

     6 #include <edmonds.h>

     8 using namespace hugo;

    10 int main (int, char*[])

    11 {

    12   typedef ListGraph::NodeIt NodeIt;

    13   typedef ListGraph::EdgeIt EdgeIt;

    14   typedef ListGraph::Node Node;

    15   typedef ListGraph::Edge Edge;

    16   typedef ListGraph::OutEdgeIt OutEdgeIt;

    17   typedef ListGraph::InEdgeIt InEdgeIt;

    19   ListGraph flow_test;

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

    22   Node s=flow_test.addNode();

    23   Node v1=flow_test.addNode();

    24   Node v2=flow_test.addNode();

    25   Node v3=flow_test.addNode();

    26   Node v4=flow_test.addNode();

    27   Node v5=flow_test.addNode();

    28   Node t=flow_test.addNode();

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

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

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

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

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

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

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

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

    39   Edge s_v1=flow_test.addEdge(s, v1);

    40   Edge s_v2=flow_test.addEdge(s, v2);

    41   Edge s_v3=flow_test.addEdge(s, v3);

    42   Edge v2_v4=flow_test.addEdge(v2, v4);

    43   Edge v2_v5=flow_test.addEdge(v2, v5);

    44   Edge v3_v5=flow_test.addEdge(v3, v5);

    45   Edge v4_t=flow_test.addEdge(v4, t);

    46   Edge v5_t=flow_test.addEdge(v5, t);

    47   Edge v2_s=flow_test.addEdge(v2, s);

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

    50   cap.set(s_v1, 0);

    51   cap.set(s_v2, 10);

    52   cap.set(s_v3, 10);

    53  cap.set(v2_v4, 5);

    54   cap.set(v2_v5, 8);

    55   cap.set(v3_v5, 5);

    56   cap.set(v4_t, 8);

    57   cap.set(v5_t, 8);

    58   cap.set(v2_s, 0);

    61   Edmonds<ListGraph> edmonds(flow_test);

    62   std::vector<Edge> matching(0);

    63   std::cout<<  edmonds.run(matching);

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

    67     Node s=flow_test.addNode();

    68   Node v1=flow_test.addNode();

    69   Node v2=flow_test.addNode();

    70   Node v3=flow_test.addNode();

    71   Node v4=flow_test.addNode();

    72   Node t=flow_test.addNode();

    73   Node z=flow_test.addNode();

    76    ListGraph::NodeMap<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(z, "z");

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

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

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

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

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

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

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

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

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

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

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

    96   Edge s_z=flow_test.addEdge(s, z);

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

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

   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_z, 4);

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

   116   */

   118   //pelda 3, maxflowvalue=4

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

   120   Node v1=flow_test.addNode();

   121   Node v2=flow_test.addNode();

   122   Node t=flow_test.addNode();

   123   Node 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   Edge s_v1=flow_test.addEdge(s, v1);

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

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

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

   136   Edge 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   */

   164   /*

   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;

   208   */

   210   return 0;

   211 }

author	jacint
	Wed, 05 May 2004 17:23:04 +0000
changeset 534	22ce98f7d0f1
permissions	-rw-r--r--