Boost C++ Libraries: Ticket #11960: boost::transitive_closure dies on small graph with only 100,000 vertices

attachment set

Sat, 06 Feb 2016 03:03:29 GMT

attachment → death.cpp

cpp source code to reproduce bug

Sat, 06 Feb 2016 03:25:27 GMT

I traced it to transitive_closure.hpp:178,

        std::vector<std::vector<cg_vertex> > successors(CG_vec.size(),
                                                       std::vector<cg_vertex>
                                                       (chains.size(), inf));

Both vec.size() and chains.size() are 100,000 and sizeof(inf) is 8 so that's .. 76 terabytes? There must be a more space efficient way to implement this algorithm?

component changed; owner set

Steven Watanabe — Sat, 13 Feb 2016 21:17:56 GMT

owner set to Jeremiah Willcock
component None → graph