sdcc/src/SDCCtree_dec.hpp

   1 // Philipp Klaus Krause, philipp@informatik.uni-frankfurt.de, pkk@spth.de, 2010 - 2011
   2 //
   3 // (c) 2010-2011 Goethe-Universität Frankfurt
   4 //
   5 // This program is free software; you can redistribute it and/or modify it
   6 // under the terms of the GNU General Public License as published by the
   7 // Free Software Foundation; either version 2, or (at your option) any
   8 // later version.
   9 //
  10 // This program is distributed in the hope that it will be useful,
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 // GNU General Public License for more details.
  14 //
  15 // You should have received a copy of the GNU General Public License
  16 // along with this program; if not, write to the Free Software
  17 // Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18 //
  19 //
  20 // Some routines for tree-decompositions.
  21 //
  22 // A tree decomposition is a graph that has a set of vertex indices as bundled property, e.g.:
  23 //
  24 // struct tree_dec_node
  25 // {
  26 //  std::set<unsigned int> bag;
  27 // };
  28 // typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, tree_dec_node> tree_dec_t;
  29 //
  30 // The following are the routines that are most likely to be interesting for outside use:
  31 //
  32 // void nicify(T_t &T)
  33 // Transforms a tree decomposition T into a nice tree decomposition
  34 //
  35 // void thorup_tree_decomposition(T_t &tree_decomposition, const G_t &cfg)
  36 // Creates a tree decomposition T from a graph cfg using Thorup's heuristic.
  37 //
  38 // void tree_decomposition_from_elimination_ordering(T_t &T, std::list<unsigned int>& l, const G_t &G)
  39 // Creates a tree decomposition T of a graph G from an elimination ordering l.
  40 //
  41 // void thorup_elimination_ordering(l_t &l, const J_t &J)
  42 // Creates an elimination ordering l of a graph J using Thorup's heuristic.
  43 //
  44
  45 #include <map>
  46 #include <vector>
  47 #include <set>
  48 #include <stack>
  49 #include <list>
  50
  51 #include <boost/tuple/tuple_io.hpp>
  52 #include <boost/graph/graph_traits.hpp>
  53 #include <boost/graph/graph_utility.hpp>
  54 #include <boost/graph/properties.hpp>
  55 #include <boost/graph/copy.hpp>
  56 #include <boost/graph/adjacency_list.hpp>
  57
  58 #undef RANGE
  59 #undef BLOCK
  60
  61 struct forget_properties
  62 {
  63   template<class T1, class T2>
  64   void operator()(const T1&, const T2&) const
  65   {
  66   }
  67 };
  68
  69 // Thorup algorithm D.
  70 // The use of the multimap makes the complexity of this O(|I|log|I|), which could be reduced to O(|I|).
  71 template <class l_t>
  72 void thorup_D(l_t &l, const std::multimap<unsigned int, unsigned int> &MJ, const std::multimap<unsigned int, unsigned int> &MS, const unsigned int n)
  73 {
  74   std::map<unsigned int, unsigned int> m;
  75
  76   l.clear();
  77
  78   unsigned int i = 0;
  79   for (unsigned int j = n; j > 0;)
  80     {
  81       j--;
  82       if (m.find(j) == m.end())
  83         m[j] = i++;
  84
  85       std::multimap<unsigned int, unsigned int>::const_iterator k, k_end;
  86
  87       for (boost::tie(k, k_end) = MS.equal_range(j); k != k_end; ++k)
  88         if (m.find(k->second) == m.end())
  89           m[k->second] = i++;
  90
  91       for (boost::tie(k, k_end) = MJ.equal_range(j); k != k_end; ++k)
  92         if (m.find(k->second) == m.end())
  93           m[k->second] = i++;
  94     }
  95
  96   std::vector<unsigned int> v(n);
  97
  98   std::map<unsigned int, unsigned int>::iterator mi;
  99
 100   for (mi = m.begin(); mi != m.end(); ++mi)
 101     v[mi->second] = mi->first;
 102
 103   for (i = 0; i < n; i++)
 104     l.push_back(v[i]);
 105 }
 106
 107 // Thorup algorithm E.
 108 // The use of the multimap makes the complexity of this O(|I|log|I|), which could be reduced to O(|I|).
 109 template <class I_t>
 110 void thorup_E(std::multimap<unsigned int, unsigned int> &M, const I_t &I)
 111 {
 112   typedef typename boost::graph_traits<I_t>::adjacency_iterator adjacency_iter_t;
 113   typedef typename boost::property_map<I_t, boost::vertex_index_t>::type index_map;
 114   index_map index = boost::get(boost::vertex_index, I);
 115
 116   std::stack<std::pair<int, unsigned int> > s;
 117
 118   M.clear();
 119
 120   s.push(std::pair<int, unsigned int>(-1, boost::num_vertices(I)));
 121
 122   for (unsigned int i = 0; i < boost::num_vertices(I); i++)
 123     {
 124       unsigned int j = i;
 125       adjacency_iter_t j_curr, j_end;
 126
 127       for (boost::tie(j_curr, j_end) = boost::adjacent_vertices(i, I); j_curr != j_end; ++j_curr)
 128         if (index[*j_curr] > j)
 129           j = index[*j_curr];
 130
 131       if (j == i)
 132         continue;
 133
 134       while (s.top().second <= i)
 135         {
 136           M.insert(std::pair<unsigned int, unsigned int>(s.top().second, s.top().first));
 137           s.pop();
 138         }
 139
 140       unsigned int i2 = i;
 141       while (j >= s.top().second && s.top().second > i2)
 142         {
 143           i2 = s.top().first;
 144           s.pop();
 145         }
 146
 147       s.push(std::pair<int, unsigned int>(i2, j));
 148     }
 149
 150     // Thorup forgot this in his paper. Without it, some maximal chains are omitted.
 151     while(s.size() > 1)
 152     {
 153         M.insert(std::pair<unsigned int, unsigned int>(s.top().second, s.top().first));
 154         s.pop();
 155     }
 156 }
 157
 158 // Heuristically give an elimination ordering for a directed graph.
 159 // For a description of this, including algorithms D and E, see
 160 // Mikkel Thorup, "All Structured Programs have Small Tree-Width and Good Register Allocation", Appendix A.
 161 // The use of the multimap makes the complexity of this O(|I|log|I|), could be reduced to O(|I|).
 162 template <class l_t, class G_t>
 163 void thorup_elimination_ordering(l_t &l, const G_t &G)
 164 {
 165   // Remove edges to immediately following instruction. By "each statement can have at most obne jump" in the last paragraph of Appendix A it is clear that Thorup does not consider the implicit next-instruction-edges as jumps.
 166   boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> J;
 167   boost::copy_graph(G, J, boost::vertex_copy(forget_properties()).edge_copy(forget_properties()));
 168   for (unsigned int i = 0; i < boost::num_vertices(J) - 1; i++)
 169     remove_edge(i, i + 1, J);
 170
 171   // Todo: Implement a graph adaptor for boost that allows to treat directed graphs as undirected graphs.
 172   boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> S;
 173   boost::copy_graph(J, S);
 174
 175   std::multimap<unsigned int, unsigned int> MJ, MS;
 176
 177   thorup_E(MJ, J);
 178
 179   thorup_E(MS, S);
 180
 181   thorup_D(l, MJ, MS, num_vertices(J));
 182 }
 183
 184 // Finds a (the newest) bag that contains all vertices in X in the tree decomposition T.
 185 template <class X_t, class T_t>
 186 typename boost::graph_traits<T_t>::vertex_iterator find_bag(const X_t &X, const T_t &T)
 187 {
 188   typedef typename boost::graph_traits<T_t>::vertex_iterator T_vertex_iter_t;
 189   typedef typename X_t::const_iterator vertex_index_iter_t;
 190
 191   T_vertex_iter_t t, t_end, t_found;
 192   vertex_index_iter_t v;
 193
 194   for (boost::tie(t, t_end) = vertices(T), t_found = t_end; t != t_end; ++t)
 195     {
 196       for (v = X.begin(); v != X.end(); ++v)
 197         if (T[*t].bag.find(*v) == T[*t].bag.end())
 198           break;
 199
 200       if (v == X.end())
 201         t_found = t;
 202     }
 203
 204   if (t_found == t_end) // Todo: Better error handling (throw exception?)
 205     {
 206       std::cerr << "find_bag() failed.\n";
 207       std::cerr.flush();
 208     }
 209
 210   return(t_found);
 211 }
 212
 213 // Add edges to make the vertices in X a clique in G.
 214 template <class X_t, class G_t>
 215 void make_clique(const X_t &X , G_t &G)
 216 {
 217   typename X_t::const_iterator n1, n2;
 218   for (n1 = X.begin(); n1 != X.end(); n1++)
 219     for (n2 = n1, ++n2; n2 != X.end(); ++n2)
 220       add_edge(*n1, *n2, G);
 221 }
 222
 223 template <class T_t, class v_t, class G_t>
 224 void add_vertices_to_tree_decomposition(T_t &T, const v_t v, const v_t v_end, G_t &G, std::vector<bool> &active)
 225 {
 226   // Base case: Empty graph. Create an empty bag.
 227   if (v == v_end)
 228     {
 229       boost::add_vertex(T);
 230       return;
 231     }
 232
 233   // Todo: A more elegant solution, e.g. using subgraphs or filtered graphs.
 234
 235   typedef typename boost::graph_traits<G_t>::adjacency_iterator adjacency_iter_t;
 236   typedef typename boost::property_map<G_t, boost::vertex_index_t>::type index_map;
 237   index_map index = boost::get(boost::vertex_index, G);
 238
 239   // Get the neigbours
 240   adjacency_iter_t n, n_end;
 241   decltype(T[0].bag) neighbours;
 242   for (boost::tie(n, n_end) = boost::adjacent_vertices(*v, G); n != n_end; ++n)
 243     if (active[index[*n]])
 244       neighbours.insert(index[*n]);
 245
 246   // Recurse
 247   active[*v] = false;
 248   make_clique(neighbours, G);
 249   v_t v_next = v;
 250   add_vertices_to_tree_decomposition(T, ++v_next, v_end, G, active);
 251
 252   // Add new bag
 253   typename boost::graph_traits<T_t>::vertex_iterator t;
 254   typename boost::graph_traits<T_t>::vertex_descriptor s;
 255   t = find_bag(neighbours, T);
 256   s = boost::add_vertex(T);
 257   boost::add_edge(*t, s, T);
 258   T[s].bag = neighbours;
 259   T[s].bag.insert(*v);
 260 }
 261
 262 // Create a tree decomposition from an elimination ordering.
 263 template <class T_t, class G_t>
 264 void tree_decomposition_from_elimination_ordering(T_t &T, const std::list<unsigned int>& l, const G_t &G)
 265 {
 266   std::list<unsigned int>::const_reverse_iterator v, v_end;
 267   v = l.rbegin(), v_end = l.rend();
 268
 269   // Todo: Implement a graph adaptor for boost that allows to treat directed graphs as undirected graphs.
 270   boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> G_sym;
 271   boost::copy_graph(G, G_sym, boost::vertex_copy(forget_properties()).edge_copy(forget_properties()));
 272
 273   std::vector<bool> active(boost::num_vertices(G), true);
 274
 275   add_vertices_to_tree_decomposition(T, v, v_end, G_sym, active);
 276 }
 277
 278 template <class T_t, class G_t>
 279 void thorup_tree_decomposition(T_t &tree_decomposition, const G_t &cfg)
 280 {
 281   std::list<unsigned int> elimination_ordering;
 282
 283   thorup_elimination_ordering(elimination_ordering, cfg);
 284
 285   tree_decomposition_from_elimination_ordering(tree_decomposition, elimination_ordering, cfg);
 286 }
 287
 288 // Ensure that all joins are at proper join nodes: Each node that has two children has the same bag as its children.
 289 // Complexity: Linear in the number of vertices of T.
 290 template <class T_t>
 291 void nicify_joins(T_t &T, typename boost::graph_traits<T_t>::vertex_descriptor t)
 292 {
 293   typedef typename boost::graph_traits<T_t>::adjacency_iterator adjacency_iter_t;
 294
 295   adjacency_iter_t c, c_end;
 296   typename boost::graph_traits<T_t>::vertex_descriptor c0, c1;
 297
 298   boost::tie(c, c_end) = boost::adjacent_vertices(t, T);
 299
 300   switch (out_degree(t, T))
 301     {
 302     case 0:
 303       return;
 304     case 1:
 305       nicify_joins(T, *c);
 306       return;
 307     case 2:
 308       break;
 309     default:
 310       c0 = *c++;
 311       c1 = *c;
 312       typename boost::graph_traits<T_t>::vertex_descriptor d;
 313       d = boost::add_vertex(T);
 314       add_edge(d, c0, T);
 315       add_edge(d, c1, T);
 316       boost::remove_edge(t, c0, T);
 317       boost::remove_edge(t, c1, T);
 318       T[d].bag = T[t].bag;
 319       boost::add_edge(t, d, T);
 320       nicify_joins(T, t);
 321       return;
 322     }
 323
 324   c0 = *c++;
 325   c1 = *c;
 326   nicify_joins(T, c0);
 327   if (T[t].bag != T[c0].bag)
 328     {
 329       typename boost::graph_traits<T_t>::vertex_descriptor d;
 330       d = boost::add_vertex(T);
 331       boost::add_edge(d, c0, T);
 332       boost::remove_edge(t, c0, T);
 333       T[d].bag = T[t].bag;
 334       boost::add_edge(t, d, T);
 335     }
 336   nicify_joins(T, c1);
 337   if (T[t].bag != T[c1].bag)
 338     {
 339       typename boost::graph_traits<T_t>::vertex_descriptor d = boost::add_vertex(T);
 340       boost::add_edge(d, c1, T);
 341       boost::remove_edge(t, c1, T);
 342       T[d].bag = T[t].bag;
 343       boost::add_edge(t, d, T);
 344     }
 345 }
 346
 347 // Ensure that all nodes' bags are either a subset or a superset of their successors'.
 348 // Complexity: Linear in the number of vertices of T.
 349 template <class T_t>
 350 void nicify_diffs(T_t &T, typename boost::graph_traits<T_t>::vertex_descriptor t)
 351 {
 352   typedef typename boost::graph_traits<T_t>::adjacency_iterator adjacency_iter_t;
 353
 354   adjacency_iter_t c, c_end;
 355   typename boost::graph_traits<T_t>::vertex_descriptor c0, c1;
 356
 357   boost::tie(c, c_end) = adjacent_vertices(t, T);
 358
 359   switch (boost::out_degree(t, T))
 360     {
 361     case 0:
 362       if (T[t].bag.size())
 363         boost::add_edge(t, boost::add_vertex(T), T);
 364       return;
 365     case 1:
 366       break;
 367     case 2:
 368       c0 = *c++;
 369       c1 = *c;
 370       nicify_diffs(T, c0);
 371       nicify_diffs(T, c1);
 372       return;
 373     default:
 374       std::cerr << "nicify_diffs error.\n";
 375       return;
 376     }
 377
 378   c0 = *c;
 379   nicify_diffs(T, c0);
 380
 381   // Redundant bags are isolated, and thus marked for later removal.
 382   if (T[t].bag == T[c0].bag)
 383     {
 384       T[c0].bag.clear();
 385       boost::remove_edge(t, c0, T);
 386       adjacency_iter_t c, c_end;
 387       for(boost::tie(c, c_end) = adjacent_vertices(c0, T); c != c_end; ++c)
 388         boost::add_edge(t, *c, T);
 389       boost::clear_vertex(c0, T);
 390     }
 391
 392   if (std::includes(T[t].bag.begin(), T[t].bag.end(), T[c0].bag.begin(), T[c0].bag.end()) || std::includes(T[c0].bag.begin(), T[c0].bag.end(), T[t].bag.begin(), T[t].bag.end()))
 393     return;
 394
 395   typename boost::graph_traits<T_t>::vertex_descriptor d = boost::add_vertex(T);
 396
 397   boost::add_edge(d, c0, T);
 398   boost::remove_edge(t, c0, T);
 399   std::set_intersection(T[t].bag.begin(), T[t].bag.end(), T[c0].bag.begin(), T[c0].bag.end(), std::inserter(T[d].bag, T[d].bag.begin()));
 400   boost::add_edge(t, d, T);
 401 }
 402
 403 // Ensure that all nodes' bags' sizes differ by at most one to their successors'.
 404 template <class T_t>
 405 void nicify_diffs_more(T_t &T, typename boost::graph_traits<T_t>::vertex_descriptor t)
 406 {
 407   typedef typename boost::graph_traits<T_t>::adjacency_iterator adjacency_iter_t;
 408
 409   adjacency_iter_t c, c_end;
 410   typename boost::graph_traits<T_t>::vertex_descriptor c0, c1;
 411
 412   boost::tie(c, c_end) = adjacent_vertices(t, T);
 413
 414   switch (boost::out_degree(t, T))
 415     {
 416     case 0:
 417       if (T[t].bag.size() > 1)
 418         {
 419           typename boost::graph_traits<T_t>::vertex_descriptor d = boost::add_vertex(T);
 420           T[d].bag = T[t].bag;
 421           T[d].bag.erase(T[d].bag.begin());
 422           T[d].weight = 0;
 423           boost::add_edge(t, d, T);
 424           nicify_diffs_more(T, t);
 425         }
 426       else
 427         T[t].weight = 0;
 428       return;
 429     case 1:
 430       break;
 431     case 2:
 432       c0 = *c++;
 433       c1 = *c;
 434       nicify_diffs_more(T, c0);
 435       nicify_diffs_more(T, c1);
 436       {
 437         const unsigned l = T[c0].weight;
 438         const unsigned r = T[c1].weight;
 439         T[t].weight = (l == r) ? l + 1 : std::max(l , r);
 440       }
 441       return;
 442     default:
 443       std::cerr << "nicify_diffs_more error.\n";
 444       return;
 445     }
 446
 447   c0 = *c;
 448
 449   size_t c0_size, t_size;
 450   t_size = T[t].bag.size();
 451   c0_size = T[c0].bag.size();
 452
 453   if (t_size <= c0_size + 1 && t_size + 1 >= c0_size)
 454     {
 455       nicify_diffs_more(T, c0);
 456       T[t].weight = T[c0].weight;
 457       return;
 458     }
 459
 460   typename boost::graph_traits<T_t>::vertex_descriptor d = add_vertex(T);
 461   boost::add_edge(d, c0, T);
 462   boost::remove_edge(t, c0, T);
 463   T[d].bag = T[t_size > c0_size ? t : c0].bag;
 464   typename decltype(T[d].bag)::iterator i;
 465   for (i = T[d].bag.begin(); T[t_size < c0_size ? t : c0].bag.find(*i) != T[t_size < c0_size ? t : c0].bag.end(); ++i);
 466   T[d].bag.erase(i);
 467   boost::add_edge(t, d, T);
 468
 469   nicify_diffs_more(T, t);
 470 }
 471
 472 #ifdef HAVE_TREEDEC_COMBINATIONS_HPP
 473 #include <treedec/treedec_traits.hpp>
 474 #include <boost/graph/adjacency_list.hpp>
 475 #include <boost/tuple/tuple.hpp>
 476 #include <boost/graph/graph_utility.hpp>
 477 #include <treedec/nice_decomposition.hpp>
 478
 479 using treedec::find_root;
 480 #else
 481 // Find a root of an acyclic graph T
 482 // Complexity: Linear in the number of vertices of T.
 483 template <class T_t>
 484 typename boost::graph_traits<T_t>::vertex_descriptor find_root(T_t &T)
 485 {
 486   typename boost::graph_traits<T_t>::vertex_descriptor t;
 487   typename boost::graph_traits<T_t>::in_edge_iterator e, e_end;
 488
 489   t = *(boost::vertices(T).first);
 490
 491   for (boost::tie(e, e_end) = boost::in_edges(t, T); e != e_end; boost::tie(e, e_end) = boost::in_edges(t, T))
 492     t = boost::source(*e, T);
 493
 494   return(t);
 495 }
 496 #endif
 497
 498 // Remove isolated vertices possibly introduced by nicify_diffs(). Complicated, since boost does not support removing more than one vertex at a time.
 499 template <class T_t>
 500 void remove_isolated_vertices(T_t &T)
 501 {
 502   bool change = true;
 503   while(change)
 504     {
 505       change = false;
 506       if(boost::num_vertices(T) <= 1)
 507         return;
 508
 509       for (unsigned int i = 0; i < boost::num_vertices(T); i++)
 510         if(!boost::out_degree(i, T) && !boost::in_degree(i, T))
 511           {
 512             remove_vertex(i, T);
 513             change = true;
 514             break;
 515           }
 516     }
 517 }
 518
 519 // Transform a tree decomposition into a nice tree decomposition.
 520 template <class T_t>
 521 void nicify(T_t &T)
 522 {
 523   typename boost::graph_traits<T_t>::vertex_descriptor t;
 524
 525   t = find_root(T);
 526
 527   // Ensure we have an empty bag at the root.
 528   if(T[t].bag.size())
 529   {
 530     typename boost::graph_traits<T_t>::vertex_descriptor d = t;
 531     t = add_vertex(T);
 532     boost::add_edge(t, d, T);
 533   }
 534
 535   nicify_joins(T, t);
 536   nicify_diffs(T, t);
 537   nicify_diffs_more(T, t);
 538   remove_isolated_vertices(T);
 539 }
 540
 541 class cfg_titlewriter
 542 {
 543 public:
 544   explicit cfg_titlewriter(const std::string& f, const std::string& p) : function(f), purpose(p)
 545     {
 546     }
 547   void operator()(std::ostream& out) const
 548     {
 549       out << "graph [label=\"Control-flow-graph for " << purpose << " (function " << function << ")\"]\n";
 550     }
 551 private:
 552   std::string function;
 553   std::string purpose;
 554 };
 555
 556 class dec_titlewriter
 557 {
 558 public:
 559   explicit dec_titlewriter(unsigned int w, const std::string& f, const std::string& p) : function(f), purpose(p)
 560     {
 561       width = w;
 562     }
 563   void operator()(std::ostream& out) const
 564     {
 565       out << "graph [label=\"Tree-decomposition of width " << width << " for " << purpose << " (function " << function << ")\"]\n";
 566     }
 567 private:
 568   unsigned int width;
 569   std::string function;
 570   std::string purpose;
 571 };
 572
 573 #ifdef HAVE_TREEDEC_COMBINATIONS_HPP
 574
 575 #include <treedec/graph.hpp>
 576 #include <treedec/preprocessing.hpp>
 577 #include <boost/graph/copy.hpp>
 578
 579 #include <treedec/thorup.hpp>
 580 #include <treedec/combinations.hpp>
 581 #include <treedec/misc.hpp>
 582
 583 template <typename Gd_t, typename Gs_t>
 584 void copy_undir(Gd_t &dst, const Gs_t &src)
 585 {
 586   for(unsigned i = 0; i < boost::num_vertices(src); i++)
 587     boost::add_vertex(dst);
 588
 589   typename boost::graph_traits<Gs_t>::edge_iterator e, e_end;
 590   for(boost::tie(e, e_end) = boost::edges(src); e != e_end; ++e)
 591     {
 592       wassert (boost::source(*e, src) != boost::target(*e, src));
 593       if (!boost::edge(boost::source(*e, src), boost::target(*e, src), dst).second)
 594         boost::add_edge(boost::source(*e, src), boost::target(*e, src), dst);
 595     }
 596 }
 597
 598 #endif
 599
 600 #undef USE_THORUP // Thorup's classic algorithm (default in SDCC pre-3.7.0). Substantially worse width than the others.
 601 #define USE_PP_FI_TM 1 // A good trade-off between width and runtime
 602 #undef USE_EX17 // Slightly better width than PP_FI_TM, but no polynomial runtime bound.
 603 #undef USE_PP_MD // Slightly worse width than PP_FI_TM.
 604 #undef USE_PP_FI // Slightly worse width than PP_FI_TM.
 605
 606 // Get a nice tree decomposition for a cfg.
 607 template <class T_t, class G_t>
 608 void get_nice_tree_decomposition(T_t &tree_dec, const G_t &cfg)
 609 {
 610   thorup_tree_decomposition(tree_dec, cfg);
 611
 612 #ifdef HAVE_TREEDEC_COMBINATIONS_HPP
 613
 614 #ifdef USE_THORUP
 615   treedec::thorup<G_t> a2(cfg);
 616 #else
 617   typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS> cfg2_t;
 618   cfg2_t cfg2;
 619   copy_undir(cfg2, cfg);
 620 #if USE_PP_FI_TM
 621   treedec::comb::PP_FI_TM<cfg2_t> a2(cfg2);
 622 #elif USE_EX17
 623   treedec::comb::ex17<cfg2_t> a2(cfg2);
 624 #elif USE_PP_MD
 625   treedec::comb::PP_MD<cfg2_t> a2(cfg2);
 626 #elif USE_PP_FI
 627   treedec::comb::PP_FI<cfg2_t> a2(cfg2);
 628 #else
 629 #error No algorithm selected
 630 #endif
 631 #endif
 632
 633   T_t tree_dec2;
 634   a2.do_it();
 635   a2.get_tree_decomposition(tree_dec2);
 636   wassert(treedec::is_valid_treedecomposition(cfg, tree_dec2));
 637
 638   if (treedec::get_width(tree_dec2) < treedec::get_width(tree_dec))
 639     std::swap(tree_dec, tree_dec2);
 640 #endif
 641
 642   nicify(tree_dec);
 643
 644 #ifdef HAVE_TREEDEC_COMBINATIONS_HPP
 645   wassert(treedec::is_valid_treedecomposition(cfg, tree_dec));
 646 #endif
 647 }
 648