lemon-0.x: src/test/minlengthpaths

     1 #include <iostream>

     2 #include <hugo/list_graph.h>

     3 #include <hugo/minlengthpaths.h>

     4 #include <path.h>

     5 #include "test_tools.h"

     7 using namespace std;

     8 using namespace hugo;

    12 bool passed = true;

    15 int main()

    16 {

    18   typedef ListGraph::Node Node;

    19   typedef ListGraph::Edge Edge;

    21   ListGraph graph;

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

    25   Node s=graph.addNode();

    26   Node v1=graph.addNode();

    27   Node v2=graph.addNode();

    28   Node v3=graph.addNode();

    29   Node v4=graph.addNode();

    30   Node v5=graph.addNode();

    31   Node t=graph.addNode();

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

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

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

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

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

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

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

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

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

    45   length.set(s_v1, 6);

    46   length.set(v1_v2, 4);

    47   length.set(s_v3, 10);

    48   length.set(v2_v4, 5);

    49   length.set(v2_v5, 1);

    50   length.set(v3_v5, 5);

    51   length.set(v4_t, 8);

    52   length.set(v5_t, 8);

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

    57   int k=3;

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

    59     surb_test(graph, length);

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

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

    65   typedef DirPath<ListGraph> DPath;

    66   DPath P(graph);

    68   /*

    69   surb_test.getPath(P,0);

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

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

    72   surb_test.getPath(P,1);

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

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

    75   */

    77   k=1;

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

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

    82   surb_test.getPath(P,0);

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

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

    86        << endl;

    88   return passed ? 0 : 1;

    90 }

author	alpar
	Mon, 19 Jul 2004 13:30:20 +0000
changeset 707	ec034cfade65
parent 610	4ce8c695e748
child 790	2b9a43c0d64e
permissions	-rw-r--r--