Opened 7 years ago

Last modified 7 years ago

#11960 new Bugs

boost::transitive_closure dies on small graph with only 100,000 vertices

Reported by: jpritikin@… Owned by: Jeremiah Willcock
Milestone: To Be Determined Component: graph
Version: Boost 1.58.0 Severity: Problem
Keywords: Cc:

Description

Here's a trivial program that dies with a SIGKILL inside of boost::transitive_closure. I suspect it tries to allocate an absurd amount of memory.

Attachments (1)

death.cpp​ (1.2 KB ) - added by Joshua Pritikin <jpritikin@…> 7 years ago.
cpp source code to reproduce bug

Download all attachments as: .zip

Change History (3)

by Joshua Pritikin <jpritikin@…>, 7 years ago

Attachment: death.cpp​ added

cpp source code to reproduce bug

comment:1 by Joshua Pritikin <jpritikin@…>, 7 years ago

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?

comment:2 by Steven Watanabe, 7 years ago

Component: None → graph
Owner: set to Jeremiah Willcock
Note: See TracTickets for help on using tickets.