| 1 | #define BOOST_TEST_MODULE yen_ksp
|
|---|
| 2 |
|
|---|
| 3 | #include "yen_ksp.hpp"
|
|---|
| 4 |
|
|---|
| 5 | #include <boost/graph/adjacency_list.hpp>
|
|---|
| 6 | #include <boost/graph/filtered_graph.hpp>
|
|---|
| 7 | #include <boost/test/unit_test.hpp>
|
|---|
| 8 |
|
|---|
| 9 | #include <list>
|
|---|
| 10 |
|
|---|
| 11 | typedef
|
|---|
| 12 | boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
|
|---|
| 13 | boost::no_property,
|
|---|
| 14 | boost::property<boost::edge_weight_t, int> >
|
|---|
| 15 | Graph;
|
|---|
| 16 |
|
|---|
| 17 | typedef Graph::edge_descriptor Edge;
|
|---|
| 18 | typedef Graph::vertex_descriptor Vertex;
|
|---|
| 19 | typedef std::list<Edge> Path;
|
|---|
| 20 | typedef boost::exclude_filter<Edge> eef_type;
|
|---|
| 21 |
|
|---|
| 22 | using namespace std;
|
|---|
| 23 |
|
|---|
| 24 | // Add an edge, test it, and set weight.
|
|---|
| 25 | Edge
|
|---|
| 26 | ade(Graph &g, Vertex s, Vertex d, int w)
|
|---|
| 27 | {
|
|---|
| 28 | Edge e;
|
|---|
| 29 | bool success;
|
|---|
| 30 |
|
|---|
| 31 | boost::tie(e, success) = add_edge(s, d, g);
|
|---|
| 32 | assert(success);
|
|---|
| 33 |
|
|---|
| 34 | boost::get(boost::edge_weight, g, e) = w;
|
|---|
| 35 |
|
|---|
| 36 | return e;
|
|---|
| 37 | }
|
|---|
| 38 |
|
|---|
| 39 | pair<Edge, Edge>
|
|---|
| 40 | aue(Graph &g, Vertex s, Vertex d, int w)
|
|---|
| 41 | {
|
|---|
| 42 | return make_pair(ade(g, s, d, w), ade(g, d, s, w));
|
|---|
| 43 | }
|
|---|
| 44 |
|
|---|
| 45 | bool
|
|---|
| 46 | check_path(const std::list<std::pair<int, Path>> &r, int w, const Path &p)
|
|---|
| 47 | {
|
|---|
| 48 | for(auto const &ele: r)
|
|---|
| 49 | if (ele.first == w && ele.second == p)
|
|---|
| 50 | return true;
|
|---|
| 51 |
|
|---|
| 52 | return false;
|
|---|
| 53 | }
|
|---|
| 54 |
|
|---|
| 55 | // a
|
|---|
| 56 | // /|\
|
|---|
| 57 | // 1 | 1 --1--
|
|---|
| 58 | // / | \ / \
|
|---|
| 59 | // b 2 c d
|
|---|
| 60 | // \ | / \ /
|
|---|
| 61 | // 2 | 1 --10--
|
|---|
| 62 | // \|/
|
|---|
| 63 | // e
|
|---|
| 64 |
|
|---|
| 65 | BOOST_AUTO_TEST_CASE(yen_ksp_test)
|
|---|
| 66 | {
|
|---|
| 67 | Graph g(5);
|
|---|
| 68 |
|
|---|
| 69 | // Vertexes
|
|---|
| 70 | auto i = vertices(g).first;
|
|---|
| 71 | Vertex a = *i++;
|
|---|
| 72 | Vertex b = *i++;
|
|---|
| 73 | Vertex c = *i++;
|
|---|
| 74 | Vertex d = *i++;
|
|---|
| 75 | Vertex e = *i;
|
|---|
| 76 |
|
|---|
| 77 | // Edges
|
|---|
| 78 | Edge ab, ba;
|
|---|
| 79 | Edge ae, ea;
|
|---|
| 80 | Edge ac, ca;
|
|---|
| 81 | Edge be, eb;
|
|---|
| 82 | Edge cd1, dc1;
|
|---|
| 83 | Edge cd2, dc2;
|
|---|
| 84 | Edge ce, ec;
|
|---|
| 85 |
|
|---|
| 86 | tie(ab, ba) = aue(g, a, b, 1);
|
|---|
| 87 | tie(ae, ea) = aue(g, a, e, 2);
|
|---|
| 88 | tie(ac, ca) = aue(g, a, c, 1);
|
|---|
| 89 | tie(be, eb) = aue(g, b, e, 2);
|
|---|
| 90 | tie(cd1, dc1) = aue(g, c, d, 1);
|
|---|
| 91 | tie(cd2, dc2) = aue(g, c, d, 10);
|
|---|
| 92 | tie(ce, ec) = aue(g, c, e, 1);
|
|---|
| 93 |
|
|---|
| 94 | std::list<std::pair<int, Path>> r;
|
|---|
| 95 |
|
|---|
| 96 | r = boost::yen_ksp(g, b, d);
|
|---|
| 97 |
|
|---|
| 98 | BOOST_CHECK(check_path(r, 3, Path{ba, ac, cd1}));
|
|---|
| 99 | BOOST_CHECK(check_path(r, 12, Path{ba, ac, cd2}));
|
|---|
| 100 |
|
|---|
| 101 | BOOST_CHECK(check_path(r, 4, Path{be, ec, cd1}));
|
|---|
| 102 | BOOST_CHECK(check_path(r, 13, Path{be, ec, cd2}));
|
|---|
| 103 |
|
|---|
| 104 | BOOST_CHECK(check_path(r, 5, Path{ba, ae, ec, cd1}));
|
|---|
| 105 | BOOST_CHECK(check_path(r, 14, Path{ba, ae, ec, cd2}));
|
|---|
| 106 |
|
|---|
| 107 | BOOST_CHECK(check_path(r, 6, Path{be, ea, ac, cd1}));
|
|---|
| 108 | BOOST_CHECK(check_path(r, 15, Path{be, ea, ac, cd2}));
|
|---|
| 109 | }
|
|---|
