123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297 |
- //=======================================================================
- // Copyright (C) 2005 Jong Soo Park <jongsoo.park -at- gmail.com>
- //
- // Distributed under the Boost Software License, Version 1.0. (See
- // accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //=======================================================================
- #include <boost/test/minimal.hpp>
- #include <iostream>
- #include <algorithm>
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/dominator_tree.hpp>
- using namespace std;
- struct DominatorCorrectnessTestSet
- {
- typedef pair<int, int> edge;
- int numOfVertices;
- vector<edge> edges;
- vector<int> correctIdoms;
- };
- using namespace boost;
- typedef adjacency_list<
- listS,
- listS,
- bidirectionalS,
- property<vertex_index_t, std::size_t>, no_property> G;
- int test_main(int, char*[])
- {
- typedef DominatorCorrectnessTestSet::edge edge;
- DominatorCorrectnessTestSet testSet[7];
- // Tarjan's paper
- testSet[0].numOfVertices = 13;
- testSet[0].edges.push_back(edge(0, 1));
- testSet[0].edges.push_back(edge(0, 2));
- testSet[0].edges.push_back(edge(0, 3));
- testSet[0].edges.push_back(edge(1, 4));
- testSet[0].edges.push_back(edge(2, 1));
- testSet[0].edges.push_back(edge(2, 4));
- testSet[0].edges.push_back(edge(2, 5));
- testSet[0].edges.push_back(edge(3, 6));
- testSet[0].edges.push_back(edge(3, 7));
- testSet[0].edges.push_back(edge(4, 12));
- testSet[0].edges.push_back(edge(5, 8));
- testSet[0].edges.push_back(edge(6, 9));
- testSet[0].edges.push_back(edge(7, 9));
- testSet[0].edges.push_back(edge(7, 10));
- testSet[0].edges.push_back(edge(8, 5));
- testSet[0].edges.push_back(edge(8, 11));
- testSet[0].edges.push_back(edge(9, 11));
- testSet[0].edges.push_back(edge(10, 9));
- testSet[0].edges.push_back(edge(11, 0));
- testSet[0].edges.push_back(edge(11, 9));
- testSet[0].edges.push_back(edge(12, 8));
- testSet[0].correctIdoms.push_back((numeric_limits<int>::max)());
- testSet[0].correctIdoms.push_back(0);
- testSet[0].correctIdoms.push_back(0);
- testSet[0].correctIdoms.push_back(0);
- testSet[0].correctIdoms.push_back(0);
- testSet[0].correctIdoms.push_back(0);
- testSet[0].correctIdoms.push_back(3);
- testSet[0].correctIdoms.push_back(3);
- testSet[0].correctIdoms.push_back(0);
- testSet[0].correctIdoms.push_back(0);
- testSet[0].correctIdoms.push_back(7);
- testSet[0].correctIdoms.push_back(0);
- testSet[0].correctIdoms.push_back(4);
- // Appel. p441. figure 19.4
- testSet[1].numOfVertices = 7;
- testSet[1].edges.push_back(edge(0, 1));
- testSet[1].edges.push_back(edge(1, 2));
- testSet[1].edges.push_back(edge(1, 3));
- testSet[1].edges.push_back(edge(2, 4));
- testSet[1].edges.push_back(edge(2, 5));
- testSet[1].edges.push_back(edge(4, 6));
- testSet[1].edges.push_back(edge(5, 6));
- testSet[1].edges.push_back(edge(6, 1));
- testSet[1].correctIdoms.push_back((numeric_limits<int>::max)());
- testSet[1].correctIdoms.push_back(0);
- testSet[1].correctIdoms.push_back(1);
- testSet[1].correctIdoms.push_back(1);
- testSet[1].correctIdoms.push_back(2);
- testSet[1].correctIdoms.push_back(2);
- testSet[1].correctIdoms.push_back(2);
- // Appel. p449. figure 19.8
- testSet[2].numOfVertices = 13,
- testSet[2].edges.push_back(edge(0, 1));
- testSet[2].edges.push_back(edge(0, 2));
- testSet[2].edges.push_back(edge(1, 3));
- testSet[2].edges.push_back(edge(1, 6));
- testSet[2].edges.push_back(edge(2, 4));
- testSet[2].edges.push_back(edge(2, 7));
- testSet[2].edges.push_back(edge(3, 5));
- testSet[2].edges.push_back(edge(3, 6));
- testSet[2].edges.push_back(edge(4, 7));
- testSet[2].edges.push_back(edge(4, 2));
- testSet[2].edges.push_back(edge(5, 8));
- testSet[2].edges.push_back(edge(5, 10));
- testSet[2].edges.push_back(edge(6, 9));
- testSet[2].edges.push_back(edge(7, 12));
- testSet[2].edges.push_back(edge(8, 11));
- testSet[2].edges.push_back(edge(9, 8));
- testSet[2].edges.push_back(edge(10, 11));
- testSet[2].edges.push_back(edge(11, 1));
- testSet[2].edges.push_back(edge(11, 12));
- testSet[2].correctIdoms.push_back((numeric_limits<int>::max)());
- testSet[2].correctIdoms.push_back(0);
- testSet[2].correctIdoms.push_back(0);
- testSet[2].correctIdoms.push_back(1);
- testSet[2].correctIdoms.push_back(2);
- testSet[2].correctIdoms.push_back(3);
- testSet[2].correctIdoms.push_back(1);
- testSet[2].correctIdoms.push_back(2);
- testSet[2].correctIdoms.push_back(1);
- testSet[2].correctIdoms.push_back(6);
- testSet[2].correctIdoms.push_back(5);
- testSet[2].correctIdoms.push_back(1);
- testSet[2].correctIdoms.push_back(0);
- testSet[3].numOfVertices = 8,
- testSet[3].edges.push_back(edge(0, 1));
- testSet[3].edges.push_back(edge(1, 2));
- testSet[3].edges.push_back(edge(1, 3));
- testSet[3].edges.push_back(edge(2, 7));
- testSet[3].edges.push_back(edge(3, 4));
- testSet[3].edges.push_back(edge(4, 5));
- testSet[3].edges.push_back(edge(4, 6));
- testSet[3].edges.push_back(edge(5, 7));
- testSet[3].edges.push_back(edge(6, 4));
- testSet[3].correctIdoms.push_back((numeric_limits<int>::max)());
- testSet[3].correctIdoms.push_back(0);
- testSet[3].correctIdoms.push_back(1);
- testSet[3].correctIdoms.push_back(1);
- testSet[3].correctIdoms.push_back(3);
- testSet[3].correctIdoms.push_back(4);
- testSet[3].correctIdoms.push_back(4);
- testSet[3].correctIdoms.push_back(1);
-
- // Muchnick. p256. figure 8.21
- testSet[4].numOfVertices = 8,
- testSet[4].edges.push_back(edge(0, 1));
- testSet[4].edges.push_back(edge(1, 2));
- testSet[4].edges.push_back(edge(2, 3));
- testSet[4].edges.push_back(edge(2, 4));
- testSet[4].edges.push_back(edge(3, 2));
- testSet[4].edges.push_back(edge(4, 5));
- testSet[4].edges.push_back(edge(4, 6));
- testSet[4].edges.push_back(edge(5, 7));
- testSet[4].edges.push_back(edge(6, 7));
- testSet[4].correctIdoms.push_back((numeric_limits<int>::max)());
- testSet[4].correctIdoms.push_back(0);
- testSet[4].correctIdoms.push_back(1);
- testSet[4].correctIdoms.push_back(2);
- testSet[4].correctIdoms.push_back(2);
- testSet[4].correctIdoms.push_back(4);
- testSet[4].correctIdoms.push_back(4);
- testSet[4].correctIdoms.push_back(4);
- // Muchnick. p253. figure 8.18
- testSet[5].numOfVertices = 8,
- testSet[5].edges.push_back(edge(0, 1));
- testSet[5].edges.push_back(edge(0, 2));
- testSet[5].edges.push_back(edge(1, 6));
- testSet[5].edges.push_back(edge(2, 3));
- testSet[5].edges.push_back(edge(2, 4));
- testSet[5].edges.push_back(edge(3, 7));
- testSet[5].edges.push_back(edge(5, 7));
- testSet[5].edges.push_back(edge(6, 7));
- testSet[5].correctIdoms.push_back((numeric_limits<int>::max)());
- testSet[5].correctIdoms.push_back(0);
- testSet[5].correctIdoms.push_back(0);
- testSet[5].correctIdoms.push_back(2);
- testSet[5].correctIdoms.push_back(2);
- testSet[5].correctIdoms.push_back((numeric_limits<int>::max)());
- testSet[5].correctIdoms.push_back(1);
- testSet[5].correctIdoms.push_back(0);
- // Cytron's paper, fig. 9
- testSet[6].numOfVertices = 14,
- testSet[6].edges.push_back(edge(0, 1));
- testSet[6].edges.push_back(edge(0, 13));
- testSet[6].edges.push_back(edge(1, 2));
- testSet[6].edges.push_back(edge(2, 3));
- testSet[6].edges.push_back(edge(2, 7));
- testSet[6].edges.push_back(edge(3, 4));
- testSet[6].edges.push_back(edge(3, 5));
- testSet[6].edges.push_back(edge(4, 6));
- testSet[6].edges.push_back(edge(5, 6));
- testSet[6].edges.push_back(edge(6, 8));
- testSet[6].edges.push_back(edge(7, 8));
- testSet[6].edges.push_back(edge(8, 9));
- testSet[6].edges.push_back(edge(9, 10));
- testSet[6].edges.push_back(edge(9, 11));
- testSet[6].edges.push_back(edge(10, 11));
- testSet[6].edges.push_back(edge(11, 9));
- testSet[6].edges.push_back(edge(11, 12));
- testSet[6].edges.push_back(edge(12, 2));
- testSet[6].edges.push_back(edge(12, 13));
- testSet[6].correctIdoms.push_back((numeric_limits<int>::max)());
- testSet[6].correctIdoms.push_back(0);
- testSet[6].correctIdoms.push_back(1);
- testSet[6].correctIdoms.push_back(2);
- testSet[6].correctIdoms.push_back(3);
- testSet[6].correctIdoms.push_back(3);
- testSet[6].correctIdoms.push_back(3);
- testSet[6].correctIdoms.push_back(2);
- testSet[6].correctIdoms.push_back(2);
- testSet[6].correctIdoms.push_back(8);
- testSet[6].correctIdoms.push_back(9);
- testSet[6].correctIdoms.push_back(9);
- testSet[6].correctIdoms.push_back(11);
- testSet[6].correctIdoms.push_back(0);
- for (size_t i = 0; i < sizeof(testSet)/sizeof(testSet[0]); ++i)
- {
- const int numOfVertices = testSet[i].numOfVertices;
- G g(
- testSet[i].edges.begin(), testSet[i].edges.end(),
- numOfVertices);
- typedef graph_traits<G>::vertex_descriptor Vertex;
- typedef property_map<G, vertex_index_t>::type IndexMap;
- typedef
- iterator_property_map<vector<Vertex>::iterator, IndexMap>
- PredMap;
- vector<Vertex> domTreePredVector, domTreePredVector2;
- IndexMap indexMap(get(vertex_index, g));
- graph_traits<G>::vertex_iterator uItr, uEnd;
- int j = 0;
- for (boost::tie(uItr, uEnd) = vertices(g); uItr != uEnd; ++uItr, ++j)
- {
- put(indexMap, *uItr, j);
- }
- // Lengauer-Tarjan dominator tree algorithm
- domTreePredVector =
- vector<Vertex>(num_vertices(g), graph_traits<G>::null_vertex());
- PredMap domTreePredMap =
- make_iterator_property_map(domTreePredVector.begin(), indexMap);
- lengauer_tarjan_dominator_tree(g, vertex(0, g), domTreePredMap);
- vector<int> idom(num_vertices(g));
- for (boost::tie(uItr, uEnd) = vertices(g); uItr != uEnd; ++uItr)
- {
- if (get(domTreePredMap, *uItr) != graph_traits<G>::null_vertex())
- idom[get(indexMap, *uItr)] =
- get(indexMap, get(domTreePredMap, *uItr));
- else
- idom[get(indexMap, *uItr)] = (numeric_limits<int>::max)();
- }
- copy(idom.begin(), idom.end(), ostream_iterator<int>(cout, " "));
- cout << endl;
- // dominator tree correctness test
- BOOST_CHECK(std::equal(idom.begin(), idom.end(), testSet[i].correctIdoms.begin()));
- // compare results of fast version and slow version of dominator tree
- domTreePredVector2 =
- vector<Vertex>(num_vertices(g), graph_traits<G>::null_vertex());
- domTreePredMap =
- make_iterator_property_map(domTreePredVector2.begin(), indexMap);
- iterative_bit_vector_dominator_tree(g, vertex(0, g), domTreePredMap);
- vector<int> idom2(num_vertices(g));
- for (boost::tie(uItr, uEnd) = vertices(g); uItr != uEnd; ++uItr)
- {
- if (get(domTreePredMap, *uItr) != graph_traits<G>::null_vertex())
- idom2[get(indexMap, *uItr)] =
- get(indexMap, get(domTreePredMap, *uItr));
- else
- idom2[get(indexMap, *uItr)] = (numeric_limits<int>::max)();
- }
- copy(idom2.begin(), idom2.end(), ostream_iterator<int>(cout, " "));
- cout << endl;
- size_t k;
- for (k = 0; k < num_vertices(g); ++k)
- BOOST_CHECK(domTreePredVector[k] == domTreePredVector2[k]);
- }
- return 0;
- }
|