lemon-0.x: src/test/minlengthpaths

     1 #include <iostream>

     2 #include <hugo/list_graph.h>

     3 #include <hugo/minlengthpaths.h>

     4 #include <path.h>

     6 using namespace std;

     7 using namespace hugo;

    11 bool passed = true;

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

    14   passed = passed && rc;

    15   if(!rc) {

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

    19   }

    20 }

    24 int main()

    25 {

    27   typedef ListGraph::Node Node;

    28   typedef ListGraph::Edge Edge;

    30   ListGraph graph;

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

    34   Node s=graph.addNode();

    35   Node v1=graph.addNode();

    36   Node v2=graph.addNode();

    37   Node v3=graph.addNode();

    38   Node v4=graph.addNode();

    39   Node v5=graph.addNode();

    40   Node t=graph.addNode();

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

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

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

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

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

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

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

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

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

    54   length.set(s_v1, 6);

    55   length.set(v1_v2, 4);

    56   length.set(s_v3, 10);

    57   length.set(v2_v4, 5);

    58   length.set(v2_v5, 1);

    59   length.set(v3_v5, 5);

    60   length.set(v4_t, 8);

    61   length.set(v5_t, 8);

    63   std::cout << "Minlengthpaths algorithm test..." << std::endl;

    66   int k=3;

    67   MinLengthPaths< ListGraph, ListGraph::EdgeMap<int> >

    68     surb_test(graph, length);

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

    72   check(  surb_test.checkComplementarySlackness(), "Complementary slackness conditions are not met.");

    74   typedef DirPath<ListGraph> DPath;

    75   DPath P(graph);

    77   /*

    78   surb_test.getPath(P,0);

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

    80   cout<<P.length()<<endl;

    81   surb_test.getPath(P,1);

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

    83   cout<<P.length()<<endl;

    84   */

    86   k=1;

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

    89   check(  surb_test.checkComplementarySlackness(), "Complementary slackness conditions are not met.");

    91   surb_test.getPath(P,0);

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

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

    95        << endl;

    97   return passed ? 0 : 1;

    99 }

author	athos
	Tue, 11 May 2004 16:15:18 +0000
changeset 610	4ce8c695e748
child 611	83530dad618a
permissions	-rw-r--r--