src/test/minlengthpaths_test.cc
author marci
Thu, 02 Sep 2004 16:59:30 +0000
changeset 789 65c5c7d37578
parent 610 4ce8c695e748
child 790 2b9a43c0d64e
permissions -rw-r--r--
.
     1 #include <iostream>
     2 #include <hugo/list_graph.h>
     3 #include <hugo/minlengthpaths.h>
     4 #include <path.h>
     5 #include "test_tools.h"
     6 
     7 using namespace std;
     8 using namespace hugo;
     9 
    10 
    11 
    12 bool passed = true;
    13 
    14 
    15 int main()
    16 {
    17 
    18   typedef ListGraph::Node Node;
    19   typedef ListGraph::Edge Edge;
    20 
    21   ListGraph graph;
    22 
    23   //Ahuja könyv példája
    24 
    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();
    32 
    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);
    41   
    42 
    43   ListGraph::EdgeMap<int> length(graph);
    44 
    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);
    53 
    54   std::cout << "Minlengthpaths algorithm test..." << std::endl;
    55 
    56   
    57   int k=3;
    58   MinLengthPaths< ListGraph, ListGraph::EdgeMap<int> >
    59     surb_test(graph, length);
    60 
    61   check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,"Two paths, total length should be 46");
    62 
    63   check(  surb_test.checkComplementarySlackness(), "Complementary slackness conditions are not met.");
    64 
    65   typedef DirPath<ListGraph> DPath;
    66   DPath P(graph);
    67 
    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   */  
    76 
    77   k=1;
    78   check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
    79 
    80   check(  surb_test.checkComplementarySlackness(), "Complementary slackness conditions are not met.");
    81  
    82   surb_test.getPath(P,0);
    83   check(P.length() == 4, "First path should contain 4 edges.");  
    84 
    85   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
    86        << endl;
    87 
    88   return passed ? 0 : 1;
    89 
    90 }