Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/test/suurballe_test.cc
changeset 1005 63ccf7136641
parent 921 818510fa3d99
child 1164 80bb73097736
equal deleted inserted replaced
2:d951b6e0d175 3:f911a091a23e 
    18 #include <lemon/list_graph.h>
 
    18 #include <lemon/list_graph.h>
 
    19 #include <lemon/suurballe.h>
 
    19 #include <lemon/suurballe.h>
 
    20 //#include <path.h>
 
    20 //#include <path.h>
 
    21 #include "test_tools.h"
 
    21 #include "test_tools.h"
 
    22 
    22 
    23 using namespace std;
 
       
    24 using namespace lemon;
 
    23 using namespace lemon;
 
    25 
       
    26 
    24 
    27 
    25 
    28 bool passed = true;
 
    26 bool passed = true;
 
    29 
    27 
    30 
    28 
    31 int main()
 
    29 int main()
 
    32 {
 
    30 {
 
       
    31   typedef ListGraph Graph;
 
       
    32   typedef Graph::Node Node;
 
       
    33   typedef Graph::Edge Edge;
 
    33 
    34 
    34   typedef ListGraph::Node Node;
 
    35   Graph graph;
 
    35   typedef ListGraph::Edge Edge;
 
       
    36 
       
    37   ListGraph graph;
 
       
    38 
    36 
    39   //Ahuja könyv példája
 
    37   //Ahuja könyv példája
 
    40 
    38 
    41   Node s=graph.addNode();
 
    39   Node s=graph.addNode();
 
    42   Node v1=graph.addNode();  
    40   Node v1=graph.addNode();  
    54   Edge v3_v5=graph.addEdge(v3, v5);
 
    52   Edge v3_v5=graph.addEdge(v3, v5);
 
    55   Edge v4_t=graph.addEdge(v4, t);
 
    53   Edge v4_t=graph.addEdge(v4, t);
 
    56   Edge v5_t=graph.addEdge(v5, t);
 
    54   Edge v5_t=graph.addEdge(v5, t);
 
    57   
    55   
    58 
    56 
    59   ListGraph::EdgeMap<int> length(graph);
 
    57   Graph::EdgeMap<int> length(graph);
 
    60 
    58 
    61   length.set(s_v1, 6);
 
    59   length.set(s_v1, 6);
 
    62   length.set(v1_v2, 4);
 
    60   length.set(v1_v2, 4);
 
    63   length.set(s_v3, 10);
 
    61   length.set(s_v3, 10);
 
    64   length.set(v2_v4, 5);
 
    62   length.set(v2_v4, 5);
 
    69 
    67 
    70   std::cout << "Minlengthpaths algorithm test..." << std::endl;
 
    68   std::cout << "Minlengthpaths algorithm test..." << std::endl;
 
    71 
    69 
    72   
    70   
    73   int k=3;
 
    71   int k=3;
 
    74   Suurballe< ListGraph, ListGraph::EdgeMap<int> >
 
    72   Suurballe< Graph, Graph::EdgeMap<int> >
 
    75     surb_test(graph, length);
 
    73     surb_test(graph, length, s, t);
 
    76 
    74 
    77   check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,
 
    75   check(  surb_test.run(k) == 2 && surb_test.totalLength() == 46,
 
    78 	  "Two paths, total length should be 46");
 
    76 	  "Two paths, total length should be 46");
 
    79 
    77 
    80   check(  surb_test.checkComplementarySlackness(),
 
    78   check(  surb_test.checkComplementarySlackness(),
 
    81 	  "Complementary slackness conditions are not met.");
 
    79 	  "Complementary slackness conditions are not met.");
 
    82 
    80 
    83   //  typedef DirPath<ListGraph> DPath;
 
    81   //  typedef DirPath<Graph> DPath;
 
    84   //  DPath P(graph);
 
    82   //  DPath P(graph);
 
    85 
    83 
    86   /*
 
    84   /*
 
    87   surb_test.getPath(P,0);
 
    85   surb_test.getPath(P,0);
 
    88   check(P.length() == 4, "First path should contain 4 edges.");  
    86   check(P.length() == 4, "First path should contain 4 edges.");  
    89   cout<<P.length()<<endl;
 
    87   std::cout<<P.length()<<std::endl;
 
    90   surb_test.getPath(P,1);
 
    88   surb_test.getPath(P,1);
 
    91   check(P.length() == 3, "Second path: 3 edges.");
 
    89   check(P.length() == 3, "Second path: 3 edges.");
 
    92   cout<<P.length()<<endl;
 
    90   std::cout<<P.length()<<std::endl;
 
    93   */  
    91   */  
    94 
    92 
    95   k=1;
 
    93   k=1;
 
    96   check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,
 
    94   check(  surb_test.run(k) == 1 && surb_test.totalLength() == 19,
 
    97 	  "One path, total length should be 19");
 
    95 	  "One path, total length should be 19");
 
    98 
    96 
    99   check(  surb_test.checkComplementarySlackness(),
 
    97   check(  surb_test.checkComplementarySlackness(),
 
   100 	  "Complementary slackness conditions are not met.");
 
    98 	  "Complementary slackness conditions are not met.");
 
   101  
    99  
   102   //  surb_test.getPath(P,0);
 
   100   //  surb_test.getPath(P,0);
 
   103   //  check(P.length() == 4, "First path should contain 4 edges.");  
   101   //  check(P.length() == 4, "First path should contain 4 edges.");  
   104 
   102 
   105   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
 
   103   std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
 
   106        << endl;
 
   104 	    << std::endl;
 
   107 
   105 
   108   return passed ? 0 : 1;
 
   106   return passed ? 0 : 1;
 
   109 
   107 
   110 }
 
   108 }
lemon-0.x