lemon-0.x: src/test/mincostflows

     1 #include <iostream>

     2 #include "test_tools.h"

     3 #include <hugo/list_graph.h>

     4 #include <hugo/mincostflows.h>

     5 //#include <path.h>

     6 //#include <maps.h>

     8 using namespace std;

     9 using namespace hugo;

    13 bool passed = true;

    14 /*

    15 void check(bool rc, char *msg="") {

    16   passed = passed && rc;

    17   if(!rc) {

    18     std::cerr << "Test failed! ("<< msg << ")" << std::endl; \

    21   }

    22 }

    23 */

    26 int main()

    27 {

    29   typedef ListGraph::Node Node;

    30   typedef ListGraph::Edge Edge;

    32   ListGraph graph;

    34   //Ahuja könyv példája

    36   Node s=graph.addNode();

    37   Node v1=graph.addNode();

    38   Node v2=graph.addNode();

    39   Node v3=graph.addNode();

    40   Node v4=graph.addNode();

    41   Node v5=graph.addNode();

    42   Node t=graph.addNode();

    44   Edge s_v1=graph.addEdge(s, v1);

    45   Edge v1_v2=graph.addEdge(v1, v2);

    46   Edge s_v3=graph.addEdge(s, v3);

    47   Edge v2_v4=graph.addEdge(v2, v4);

    48   Edge v2_v5=graph.addEdge(v2, v5);

    49   Edge v3_v5=graph.addEdge(v3, v5);

    50   Edge v4_t=graph.addEdge(v4, t);

    51   Edge v5_t=graph.addEdge(v5, t);

    54   ListGraph::EdgeMap<int> length(graph);

    56   length.set(s_v1, 6);

    57   length.set(v1_v2, 4);

    58   length.set(s_v3, 10);

    59   length.set(v2_v4, 5);

    60   length.set(v2_v5, 1);

    61   length.set(v3_v5, 4);

    62   length.set(v4_t, 8);

    63   length.set(v5_t, 8);

    65   ListGraph::EdgeMap<int> capacity(graph);

    67   capacity.set(s_v1, 2);

    68   capacity.set(v1_v2, 2);

    69   capacity.set(s_v3, 1);

    70   capacity.set(v2_v4, 1);

    71   capacity.set(v2_v5, 1);

    72   capacity.set(v3_v5, 1);

    73   capacity.set(v4_t, 1);

    74   capacity.set(v5_t, 2);

    76   //  ConstMap<Edge, int> const1map(1);

    77   std::cout << "Mincostflows algorithm test..." << std::endl;

    79   MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> >

    80     surb_test(graph, length, capacity);

    82   int k=1;

    84   check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");

    86   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");

    88   k=2;

    90   check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");

    92   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");

    95   k=4;

    97   check(  surb_test.run(s,t,k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");

    99   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");

   102   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")

   103        << endl;

   105   return passed ? 0 : 1;

   107 }

author	hegyi
	Tue, 07 Sep 2004 13:55:35 +0000
changeset 815	468c9ec86928
parent 611	83530dad618a
permissions	-rw-r--r--