Re: [boost] Errors in Boost.Graph's topological_sort

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2003-01-29 10:13:14

Hi Christoph,

The problem with your example is that you forgot to initialize the
vertex_index property for each vertex. Perhaps you thought that the
adjacency_list would do this for you. However, this is not the case when
using VertexList=listS. I know this is confusing, but it is stated in the
docs that there is a builtin vertex_index property when VertexList=vecS,
whereas you were using listS.

So you need to add a couple calls to "put" to fix the situation.

  u = boost::add_vertex( g );
  put(boost::vertex_index, g, u, 0);
  v = boost::add_vertex( g );
  put(boost::vertex_index, g, v, 1);

Regards,
Jeremy

P.S. You know, it isn't polite to be accusatory before you really know
what the problem is.

On Wed, 19 Dec 2002, Christoph [ISO-8859-1] Kögl wrote:
christ> Hi there,
christ>
christ> I am using 1.29.0 on a Linux PC running Mandrake 8.1, and I am using
christ> gcc-2.96 (GNU CPP version 2.96 20000731 (Mandrake Linux 8.1
christ> 2.96-0.62mdk).
christ>
christ> See the following code. Topological sort has all sorts of problems with
christ> directed graphs (using adjacency lists) having two vertices and a single
christ> edge connecting them:
christ>
christ> #include <boost/graph/adjacency_list.hpp>
christ> #include <boost/graph/properties.hpp>
christ> #include <boost/graph/topological_sort.hpp>
christ> #include <list>
christ> #include <iterator>
christ> #include <iostream>
christ>
christ> typedef
christ> boost::adjacency_list<
christ>   boost::listS
christ> , boost::listS
christ> , boost::directedS
christ> , boost::property<
christ>     boost::vertex_index_t
christ>   , int
christ>   >
christ> >
christ> Graph;
christ>
christ> void testing( bool flip )
christ> {
christ>   Graph g;
christ>   Graph::vertex_descriptor u, v;
christ>   u = boost::add_vertex( g );
christ>   v = boost::add_vertex( g );
christ>   if( flip )
christ>   {
christ>     boost::add_edge( v, u, g );
christ>   }
christ>   else
christ>   {
christ>     boost::add_edge( u, v, g );
christ>   }
christ>   std::list< Graph::vertex_descriptor > seq;
christ>   try
christ>   {
christ>     boost::topological_sort( g, std::front_inserter( seq ) );
christ>   }
christ>   catch( const boost::not_a_dag & )
christ>   {
christ>     std::cout << "G(" << (flip ? "v, u" : "u, v") << ") not a DAG\n";
christ>   }
christ> }
christ>
christ> int main( )
christ> {
christ>   testing( false );
christ>   testing( true );
christ>   return 0;
christ> }
christ>
christ> Running this program results in the following output (slightly edited):
christ> > G(u, v) not a DAG
christ> > Speicherzugriffsfehler (German for SIGSEV)
christ> Hence u->v is not a DAG, the top. sorting routine detects a back edge.
christ> BYP?
christ> And the second call get stuck consistently at this point:
christ> template <class PropertyMap, class Reference, class K, class V>
christ>   inline void put(const put_get_helper<Reference, PropertyMap>& pa, K k,
christ> const V& v)
christ> {
christ>   static_cast<const PropertyMap&>(pa)[k] = v; // Crash occurs here.
christ> }
christ>
christ> Inverting the above function invocation sequence results in the
christ> following
christ> output:
christ> > G(u, v) not a DAG
christ> Same wrong answer, but no crash this time in testing( false ).
christ>
christ> Running only the testing( false ) call results in the same output.
christ>
christ> Boost.Graph's interfaces really appeal to me, they are very cleverly
christ> designed, but I am
christ> unable to use the current implementation in any serious project, since
christ> the above seems to
christ> point to nasty little QOI problems ... It's back to LEDA again, I
christ> suppose ...
christ>
christ> Cheers
christ>
christ> Christoph
christ>
christ> _______________________________________________
christ> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
christ>

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------