lemon-0.x: src/work/athos/mincostflows

     1 #include <iostream>

     2 #include <list_graph.h>

     3 #include <mincostflows.h>

     4 //#include <path.h>

     5 //#include <maps.h>

     7 using namespace std;

     8 using namespace hugo;

    12 bool passed = true;

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

    15   passed = passed && rc;

    16   if(!rc) {

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

    20   }

    21 }

    25 int main()

    26 {

    28   typedef ListGraph::Node Node;

    29   typedef ListGraph::Edge Edge;

    31   ListGraph graph;

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

    35   Node s=graph.addNode();

    36   Node v1=graph.addNode();

    37   Node v2=graph.addNode();

    38   Node v3=graph.addNode();

    39   Node v4=graph.addNode();

    40   Node v5=graph.addNode();

    41   Node t=graph.addNode();

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

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

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

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

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

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

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

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

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

    55   length.set(s_v1, 6);

    56   length.set(v1_v2, 4);

    57   length.set(s_v3, 10);

    58   length.set(v2_v4, 5);

    59   length.set(v2_v5, 1);

    60   length.set(v3_v5, 5);

    61   length.set(v4_t, 8);

    62   length.set(v5_t, 8);

    64   ConstMap<Edge, int> const1map(1);

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

    68   int k=3;

    69   MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ConstMap<Edge, int> >

    70     surb_test(graph, length, const1map);

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

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

    76   k=1;

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

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

    81   //cout << surb_test.run(s,t,k) << surb_test.totalLength()<<endl;

    82   /*

    83   typedef DirPath<ListGraph> DPath;

    84   DPath P(graph);

    86   surb_test.getPath(P,0);

    87   check(P.length() == 4, "First path should contain 4 edges.");

    89   surb_test.getPath(P,1);

    90   check(P.length() == 3, "Second path: 3 edges.");

    92   k=1;

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

    95   surb_test.getPath(P,0);

    96   check(P.length() == 4, "First path should contain 4 edges.");

    97   */

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

    99        << endl;

   101   return passed ? 0 : 1;

   103 }

author	marci
	Fri, 07 May 2004 10:57:31 +0000
changeset 576	d00c33d07114
parent 551	d167149bde95
permissions	-rw-r--r--