1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/suurballe_test.cc Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,108 @@
1.4 +/* -*- C++ -*-
1.5 + * test/suurballe_test.cc - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#include <iostream>
1.21 +#include <lemon/list_graph.h>
1.22 +#include <lemon/suurballe.h>
1.23 +//#include <path.h>
1.24 +#include "test_tools.h"
1.25 +
1.26 +using namespace lemon;
1.27 +
1.28 +
1.29 +bool passed = true;
1.30 +
1.31 +
1.32 +int main()
1.33 +{
1.34 + typedef ListGraph Graph;
1.35 + typedef Graph::Node Node;
1.36 + typedef Graph::Edge Edge;
1.37 +
1.38 + Graph graph;
1.39 +
1.40 + //Ahuja könyv példája
1.41 +
1.42 + Node s=graph.addNode();
1.43 + Node v1=graph.addNode();
1.44 + Node v2=graph.addNode();
1.45 + Node v3=graph.addNode();
1.46 + Node v4=graph.addNode();
1.47 + Node v5=graph.addNode();
1.48 + Node t=graph.addNode();
1.49 +
1.50 + Edge s_v1=graph.addEdge(s, v1);
1.51 + Edge v1_v2=graph.addEdge(v1, v2);
1.52 + Edge s_v3=graph.addEdge(s, v3);
1.53 + Edge v2_v4=graph.addEdge(v2, v4);
1.54 + Edge v2_v5=graph.addEdge(v2, v5);
1.55 + Edge v3_v5=graph.addEdge(v3, v5);
1.56 + Edge v4_t=graph.addEdge(v4, t);
1.57 + Edge v5_t=graph.addEdge(v5, t);
1.58 +
1.59 +
1.60 + Graph::EdgeMap<int> length(graph);
1.61 +
1.62 + length.set(s_v1, 6);
1.63 + length.set(v1_v2, 4);
1.64 + length.set(s_v3, 10);
1.65 + length.set(v2_v4, 5);
1.66 + length.set(v2_v5, 1);
1.67 + length.set(v3_v5, 5);
1.68 + length.set(v4_t, 8);
1.69 + length.set(v5_t, 8);
1.70 +
1.71 + std::cout << "Minlengthpaths algorithm test..." << std::endl;
1.72 +
1.73 +
1.74 + int k=3;
1.75 + Suurballe< Graph, Graph::EdgeMap<int> >
1.76 + surb_test(graph, length, s, t);
1.77 +
1.78 + check( surb_test.run(k) == 2 && surb_test.totalLength() == 46,
1.79 + "Two paths, total length should be 46");
1.80 +
1.81 + check( surb_test.checkComplementarySlackness(),
1.82 + "Complementary slackness conditions are not met.");
1.83 +
1.84 + // typedef DirPath<Graph> DPath;
1.85 + // DPath P(graph);
1.86 +
1.87 + /*
1.88 + surb_test.getPath(P,0);
1.89 + check(P.length() == 4, "First path should contain 4 edges.");
1.90 + std::cout<<P.length()<<std::endl;
1.91 + surb_test.getPath(P,1);
1.92 + check(P.length() == 3, "Second path: 3 edges.");
1.93 + std::cout<<P.length()<<std::endl;
1.94 + */
1.95 +
1.96 + k=1;
1.97 + check( surb_test.run(k) == 1 && surb_test.totalLength() == 19,
1.98 + "One path, total length should be 19");
1.99 +
1.100 + check( surb_test.checkComplementarySlackness(),
1.101 + "Complementary slackness conditions are not met.");
1.102 +
1.103 + // surb_test.getPath(P,0);
1.104 + // check(P.length() == 4, "First path should contain 4 edges.");
1.105 +
1.106 + std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
1.107 + << std::endl;
1.108 +
1.109 + return passed ? 0 : 1;
1.110 +
1.111 +}