boost_1_45_0/libs/graph/test/dominator_tree_test.cpp

//=======================================================================
// 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;
}