Re: [Boost-bugs] [Boost C++ Libraries] #11960: boost::transitive_closure dies on small graph with only 100, 000 vertices

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #11960: boost::transitive_closure dies on small graph with only 100, 000 vertices
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2016-02-06 03:25:27

#11960: boost::transitive_closure dies on small graph with only 100,000 vertices
-------------------------------+---------------------
  Reporter:  jpritikin@…       |      Owner:
      Type:  Bugs              |     Status:  new
 Milestone:  To Be Determined  |  Component:  None
   Version:  Boost 1.58.0      |   Severity:  Problem
Resolution:                    |   Keywords:
-------------------------------+---------------------

Comment (by Joshua Pritikin <jpritikin@…>):

 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?

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/11960#comment:1>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.