treedec::comb::PP_FI fails on adjacency_list<vecS>

[tunyash]

We'd tried to run the algorithm on a simple 4 by 4 grid (the call to the algorithm) (graph generation) and got the following runtime error:

/home/tunyash/treewidth/disj_paths_bd_tw/src/../tdlib/src/impl/greedy_heuristic.hpp:558: void treedec::obsolete::fillIn<G_t, CFGT_t>::fill_update_cb::operator()(treedec::obsolete::fillIn<G_t, CFGT_t>::fill_update_cb::vertex_descriptor, treedec::obsolete::fillIn<G_t, CFGT_t>::fill_update_cb::vertex_descriptor) [with G_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>; CFGT_t = treedec::algo::default_config; treedec::obsolete::fillIn<G_t, CFGT_t>::fill_update_cb::vertex_descriptor = long unsigned int]: Assertions < t' failed.`

I am not quite sure what to make of it or how to fix it. Will be thankful for any assistance.

[felix-salfelder]

On Sun, Jun 13, 2021 at 06:37:32AM -0700, Artur wrote:

I'd tried to run the algorithm on a simple 4 by 4 grid [..]

Hi Artur.

I have had a look. I could not execute your code, and so I am only guessing. Please provide a small self-contained example.

/home/tunyash/treewidth/disj_paths_bd_tw/src/../tdlib/src/impl/greedy_heuristic.hpp:558: void treedec::obsolete::fillIn<G_t, CFGT_t>::fill_update_cb::operator()(tre [..] Assertion `s < t' failed.

I am not quite sure what to make of it or how to fix it. Will be thankful for any assistance.

Historically, some of the algorithms required set based adjacency lists (boost::setS), and some of the rewrite seems unfinished. Some pointers

• typedef adjacency_list<vecS, vecS, undirectedS> Graph; // in your code
• "obsolete" shows up in the error message. It seems that historical code is used or there is some ordering requirement. Note how sets maintain an ordering, but there are other ways.
• examples/tdecomp.cc uses a "pending" version, cf. fi_thread.h. I don't remember how much the pending version works, it certainly lacks testing.
• The assertion in question has a "really?" comment. This might hint at an attempt to figure out what's wrong, perhaps in the context of non-ordered graphs. Remove the assertion and see what happens.

[tunyash]

Hi Felix, thanks a lot for the answer!

Here is another assertion that shows up if I remove the first one: tdlib/src/fill.hpp:838: std::pair<typename boost::graph_traits<Graph>::vertex_descriptor, typename boost::graph_traits<Graph>::vertices_size_type> treedec::obsolete::FILL<G_t, CFG>::pick_min(unsigned int, unsigned int, bool) [with G_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>; CFG = treedec::detail::fill_config<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> >; typename boost::graph_traits<Graph>::vertices_size_type = long unsigned int; typename boost::graph_traits<Graph>::vertex_descriptor = long unsigned int]: Assertiontreedec::count_missing_edges(p.first,_g) == p.second' failed.`

Here is the self-contained example.

I am not quite sure what you mean by ordering, can you elaborate?

[felix-salfelder]

On Sun, Jun 13, 2021 at 12:27:32PM -0700, Artur wrote:

Here is another assertion that shows up if I remove the first one: tdlib/src/fill.hpp:838: [..] Assertiontreedec::count_missing_edges(p.first,_g) == p.second' failed.`

The code underneath has some requirements that do not hold.

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> Graph; // 1 typedef treedec::graph_traits::treedec_type Tree;

int main() { [..] treedec::comb::PP_FI algo(g); // 2 [..] }

Thanks, I can run this. I tried both

typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS> Graph; // 1

and

treedec::pending::PP_FI algo(g); // 2

The former seems to work as expected. Perhaps, assert(s<t) must be replaced by something similar to static_assert(some_property_template::is_ordered). Then your example won't compile anymore.

The latter seems to be the correct approach, but unfortunately, it runs into incomplete code. There is work to do -- maybe it is as simple as skipping isolated nodes, but I doubt it.

I am not quite sure what you mean by ordering, can you elaborate?

adjacency_list does not maintain any particular order in the adjacency iterators under modifications. Some algorithms fail to work on unordered input (think of ordered set intersection). Generally you want to avoid setS (aka std::set, aka search tree) because it is slow, but need to maintain the order in other ways, or do things entirely different.

NB: boost::adjacency_list does not (did not?) provide ordered arrays (e.g. boost::flat_set). gala tries to address some of this.

[llarisch]

You might want to have a look into the separator algorithm and the network flow problem alongside - disjoint paths etc