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

     1 #include <iostream>

     2 #include <list_graph.h>

     3 #include <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   typedef DirPath<ListGraph> DPath;

    73   DPath P(graph);

    75   surb_test.getPath(P,0);

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

    78   surb_test.getPath(P,1);

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

    81   k=1;

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

    84   surb_test.getPath(P,0);

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

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

    88        << endl;

    90   return passed ? 0 : 1;

    92 }

author	athos
	Tue, 04 May 2004 09:33:21 +0000
changeset 520	e4a6300616f9
child 607	327f7cf13843
permissions	-rw-r--r--