src/test/suurballe_test.cc
author klao
Fri, 05 Nov 2004 00:31:49 +0000
changeset 962 1a770e9f80b2
parent 921 818510fa3d99
child 1164 80bb73097736
permissions -rw-r--r--
Undirect graph implementation.
Not yet done, untested.
     1 /* -*- C++ -*-
     2  * src/test/suurballe_test.cc - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Combinatorial Optimization Research Group, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #include <iostream>
    18 #include <lemon/list_graph.h>
    19 #include <lemon/suurballe.h>
    20 //#include <path.h>
    21 #include "test_tools.h"
    22 
    23 using namespace lemon;
    24 
    25 
    26 bool passed = true;
    27 
    28 
    29 int main()
    30 {
    31   typedef ListGraph Graph;
    32   typedef Graph::Node Node;
    33   typedef Graph::Edge Edge;
    34 
    35   Graph graph;
    36 
    37   //Ahuja könyv példája
    38 
    39   Node s=graph.addNode();
    40   Node v1=graph.addNode();  
    41   Node v2=graph.addNode();
    42   Node v3=graph.addNode();
    43   Node v4=graph.addNode();
    44   Node v5=graph.addNode();
    45   Node t=graph.addNode();
    46 
    47   Edge s_v1=graph.addEdge(s, v1);
    48   Edge v1_v2=graph.addEdge(v1, v2);
    49   Edge s_v3=graph.addEdge(s, v3);
    50   Edge v2_v4=graph.addEdge(v2, v4);
    51   Edge v2_v5=graph.addEdge(v2, v5);
    52   Edge v3_v5=graph.addEdge(v3, v5);
    53   Edge v4_t=graph.addEdge(v4, t);
    54   Edge v5_t=graph.addEdge(v5, t);
    55   
    56 
    57   Graph::EdgeMap<int> length(graph);
    58 
    59   length.set(s_v1, 6);
    60   length.set(v1_v2, 4);
    61   length.set(s_v3, 10);
    62   length.set(v2_v4, 5);
    63   length.set(v2_v5, 1);
    64   length.set(v3_v5, 5);
    65   length.set(v4_t, 8);
    66   length.set(v5_t, 8);
    67 
    68   std::cout << "Minlengthpaths algorithm test..." << std::endl;
    69 
    70   
    71   int k=3;
    72   Suurballe< Graph, Graph::EdgeMap<int> >
    73     surb_test(graph, length, s, t);
    74 
    75   check(  surb_test.run(k) == 2 && surb_test.totalLength() == 46,
    76 	  "Two paths, total length should be 46");
    77 
    78   check(  surb_test.checkComplementarySlackness(),
    79 	  "Complementary slackness conditions are not met.");
    80 
    81   //  typedef DirPath<Graph> DPath;
    82   //  DPath P(graph);
    83 
    84   /*
    85   surb_test.getPath(P,0);
    86   check(P.length() == 4, "First path should contain 4 edges.");  
    87   std::cout<<P.length()<<std::endl;
    88   surb_test.getPath(P,1);
    89   check(P.length() == 3, "Second path: 3 edges.");
    90   std::cout<<P.length()<<std::endl;
    91   */  
    92 
    93   k=1;
    94   check(  surb_test.run(k) == 1 && surb_test.totalLength() == 19,
    95 	  "One path, total length should be 19");
    96 
    97   check(  surb_test.checkComplementarySlackness(),
    98 	  "Complementary slackness conditions are not met.");
    99  
   100   //  surb_test.getPath(P,0);
   101   //  check(P.length() == 4, "First path should contain 4 edges.");  
   102 
   103   std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
   104 	    << std::endl;
   105 
   106   return passed ? 0 : 1;
   107 
   108 }