[boost] Errors in Boost.Graph's topological_sort

From: Christoph Kögl (christoph_at_[hidden])
Date: 2002-12-18 18:22:54

Hi there,

I am using 1.29.0 on a Linux PC running Mandrake 8.1, and I am using
gcc-2.96 (GNU CPP version 2.96 20000731 (Mandrake Linux 8.1
2.96-0.62mdk).

See the following code. Topological sort has all sorts of problems with
directed graphs (using adjacency lists) having two vertices and a single
edge connecting them:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/topological_sort.hpp>
#include <list>
#include <iterator>
#include <iostream>

typedef
boost::adjacency_list<
  boost::listS
, boost::listS
, boost::directedS
, boost::property<
    boost::vertex_index_t
  , int
  >
>
Graph;

void testing( bool flip )
{
  Graph g;
  Graph::vertex_descriptor u, v;
  u = boost::add_vertex( g );
  v = boost::add_vertex( g );
  if( flip )
  {
    boost::add_edge( v, u, g );
  }
  else
  {
    boost::add_edge( u, v, g );
  }
  std::list< Graph::vertex_descriptor > seq;
  try
  {
    boost::topological_sort( g, std::front_inserter( seq ) );
  }
  catch( const boost::not_a_dag & )
  {
    std::cout << "G(" << (flip ? "v, u" : "u, v") << ") not a DAG\n";
  }
}

int main( )
{
  testing( false );
  testing( true );
  return 0;
}

Running this program results in the following output (slightly edited):
> G(u, v) not a DAG
> Speicherzugriffsfehler (German for SIGSEV)
Hence u->v is not a DAG, the top. sorting routine detects a back edge.
BYP?
And the second call get stuck consistently at this point:
template <class PropertyMap, class Reference, class K, class V>
  inline void put(const put_get_helper<Reference, PropertyMap>& pa, K k,
const V& v)
{
  static_cast<const PropertyMap&>(pa)[k] = v; // Crash occurs here.
}

Inverting the above function invocation sequence results in the
following
output:
> G(u, v) not a DAG
Same wrong answer, but no crash this time in testing( false ).

Running only the testing( false ) call results in the same output.

Boost.Graph's interfaces really appeal to me, they are very cleverly
designed, but I am
unable to use the current implementation in any serious project, since
the above seems to
point to nasty little QOI problems ... It's back to LEDA again, I
suppose ...

Cheers

Christoph