src/test/minlengthpaths_test.cc
author jacint
Mon, 13 Sep 2004 10:50:28 +0000
changeset 833 512e5fd7d38b
parent 790 2b9a43c0d64e
permissions -rw-r--r--
preflow test
athos@610
     1
#include <iostream>
athos@610
     2
#include <hugo/list_graph.h>
athos@610
     3
#include <hugo/minlengthpaths.h>
alpar@790
     4
//#include <path.h>
athos@611
     5
#include "test_tools.h"
athos@610
     6
athos@610
     7
using namespace std;
athos@610
     8
using namespace hugo;
athos@610
     9
athos@610
    10
athos@610
    11
athos@610
    12
bool passed = true;
athos@610
    13
athos@610
    14
athos@610
    15
int main()
athos@610
    16
{
athos@610
    17
athos@610
    18
  typedef ListGraph::Node Node;
athos@610
    19
  typedef ListGraph::Edge Edge;
athos@610
    20
athos@610
    21
  ListGraph graph;
athos@610
    22
athos@610
    23
  //Ahuja könyv példája
athos@610
    24
athos@610
    25
  Node s=graph.addNode();
athos@610
    26
  Node v1=graph.addNode();  
athos@610
    27
  Node v2=graph.addNode();
athos@610
    28
  Node v3=graph.addNode();
athos@610
    29
  Node v4=graph.addNode();
athos@610
    30
  Node v5=graph.addNode();
athos@610
    31
  Node t=graph.addNode();
athos@610
    32
athos@610
    33
  Edge s_v1=graph.addEdge(s, v1);
athos@610
    34
  Edge v1_v2=graph.addEdge(v1, v2);
athos@610
    35
  Edge s_v3=graph.addEdge(s, v3);
athos@610
    36
  Edge v2_v4=graph.addEdge(v2, v4);
athos@610
    37
  Edge v2_v5=graph.addEdge(v2, v5);
athos@610
    38
  Edge v3_v5=graph.addEdge(v3, v5);
athos@610
    39
  Edge v4_t=graph.addEdge(v4, t);
athos@610
    40
  Edge v5_t=graph.addEdge(v5, t);
athos@610
    41
  
athos@610
    42
athos@610
    43
  ListGraph::EdgeMap<int> length(graph);
athos@610
    44
athos@610
    45
  length.set(s_v1, 6);
athos@610
    46
  length.set(v1_v2, 4);
athos@610
    47
  length.set(s_v3, 10);
athos@610
    48
  length.set(v2_v4, 5);
athos@610
    49
  length.set(v2_v5, 1);
athos@610
    50
  length.set(v3_v5, 5);
athos@610
    51
  length.set(v4_t, 8);
athos@610
    52
  length.set(v5_t, 8);
athos@610
    53
athos@610
    54
  std::cout << "Minlengthpaths algorithm test..." << std::endl;
athos@610
    55
athos@610
    56
  
athos@610
    57
  int k=3;
athos@610
    58
  MinLengthPaths< ListGraph, ListGraph::EdgeMap<int> >
athos@610
    59
    surb_test(graph, length);
athos@610
    60
alpar@791
    61
  check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,
alpar@791
    62
	  "Two paths, total length should be 46");
athos@610
    63
alpar@791
    64
  check(  surb_test.checkComplementarySlackness(),
alpar@791
    65
	  "Complementary slackness conditions are not met.");
athos@610
    66
alpar@790
    67
  //  typedef DirPath<ListGraph> DPath;
alpar@790
    68
  //  DPath P(graph);
athos@610
    69
athos@610
    70
  /*
athos@610
    71
  surb_test.getPath(P,0);
athos@610
    72
  check(P.length() == 4, "First path should contain 4 edges.");  
athos@610
    73
  cout<<P.length()<<endl;
athos@610
    74
  surb_test.getPath(P,1);
athos@610
    75
  check(P.length() == 3, "Second path: 3 edges.");
athos@610
    76
  cout<<P.length()<<endl;
athos@610
    77
  */  
athos@610
    78
athos@610
    79
  k=1;
alpar@791
    80
  check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,
alpar@791
    81
	  "One path, total length should be 19");
athos@610
    82
alpar@791
    83
  check(  surb_test.checkComplementarySlackness(),
alpar@791
    84
	  "Complementary slackness conditions are not met.");
athos@610
    85
 
alpar@790
    86
  //  surb_test.getPath(P,0);
alpar@790
    87
  //  check(P.length() == 4, "First path should contain 4 edges.");  
athos@610
    88
athos@610
    89
  cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
athos@610
    90
       << endl;
athos@610
    91
athos@610
    92
  return passed ? 0 : 1;
athos@610
    93
athos@610
    94
}