Hi all
I am using astar_search from the BGL and have sometimes hangs due to an
infinite loop (no, I do not use negative costs or negative heuristic values).
Now here is the strange problem: when compiling the attached (see below) test
program with compiler optimization enabled it runs into an infinite loop.
Without optimization a solution is found.
I need help, because I do not know what I should do next. Is this a compiler
bug? Is there something boost can do (workaround)? Is there a known issue
(could not find anything) with the relax function?
--
Detlef
Here are the facts:
I condensed one of the malicious (undirected) graphs to
<SNIP>
V ar[181];
for( unsigned int i = 0; i < 181; ++i ) {
ar[i] = add_vertex( VProp(i, 1.0), g );
}
add_edge( ar[1], ar[18 ], EProp( 2.20 ), g );
add_edge( ar[0], ar[30 ], EProp( 1.58 ), g );
add_edge( ar[0], ar[66 ], EProp( 0.93 ), g );
add_edge( ar[66], ar[100 ], EProp( 2.72 ), g );
add_edge( ar[66], ar[101 ], EProp( 2.87 ), g );
add_edge( ar[30], ar[142 ], EProp( 4.88 ), g );
add_edge( ar[18], ar[142 ], EProp( 3.29 ), g );
</SNAP>.
There are no other edges. A complete listing of the program is attached.
My compiler version:
# g++ -v
Using built-in specs.
Target: i586-suse-linux
Configured with: ../configure --enable-threads=posix --prefix=/usr
--with-local-prefix=/usr/local --infodir=/usr/share/info
--mandir=/usr/share/man --libdir=/usr/lib --libexecdir=/usr/lib
--enable-languages=c,c++,objc,f95,java,ada --disable-checking
--with-gxx-include-dir=/usr/include/c++/4.0.2 --enable-java-awt=gtk
--disable-libjava-multilib --with-slibdir=/lib --with-system-zlib
--enable-shared --enable-__cxa_atexit --without-system-libunwind
--host=i586-suse-linux
Thread model: posix
gcc version 4.0.2 20050901 (prerelease) (SUSE Linux)
# g++ -O2 searchtest4.cpp && a.out 2>/dev/null
discover: 0
examine: 0
edge_relaxed: 0 -- 30
discover: 30
edge_relaxed: 0 -- 66
discover: 66
examine: 66
edge_not_relaxed: 66 -- 0
edge_relaxed: 66 -- 100
discover: 100
edge_relaxed: 66 -- 101
discover: 101
examine: 30
edge_not_relaxed: 30 -- 0
edge_relaxed: 30 -- 142
discover: 142
CYCLE: examine: 100
CYCLE: edge_relaxed: 100 -- 66
CYCLE: black_target: 100 -- 66
CYCLE: examine: 66
CYCLE: edge_not_relaxed: 66 -- 0
CYCLE: edge_relaxed: 66 -- 100
CYCLE: black_target: 66 -- 100
CYCLE: edge_relaxed: 66 -- 101
From now on the lines marked CYCLE are repeated.
--> infinite loop
# g++ -O0 searchtest4.cpp && a.out 2>/dev/null
discover: 0
examine: 0
edge_relaxed: 0 -- 30
discover: 30
edge_relaxed: 0 -- 66
discover: 66
examine: 66
edge_not_relaxed: 66 -- 0
edge_relaxed: 66 -- 100
discover: 100
edge_relaxed: 66 -- 101
discover: 101
examine: 30
edge_not_relaxed: 30 -- 0
edge_relaxed: 30 -- 142
discover: 142
examine: 100
edge_not_relaxed: 100 -- 66 // from here on the two outputs differ
examine: 101
edge_not_relaxed: 101 -- 66
examine: 142
edge_not_relaxed: 142 -- 30
edge_relaxed: 142 -- 18
discover: 18
examine: 18
edge_relaxed: 18 -- 1
discover: 1
edge_not_relaxed: 18 -- 142
examine: 1
found
1->18->142->30->0
--> success
Here is the listing "searchtest4.cpp": ----------------------------------
#include
#include
#include
#include <iostream>
using namespace std;
using namespace boost;
struct VProp {
VProp() : m_distance(1.0) {}
VProp( size_t invar_id, double heuristic )
: m_vertex_invariable_id( invar_id ),
m_heuristic( heuristic ),
m_distance( .0 ) {}
size_t m_vertex_invariable_id; // my id that is not changed by rebuilding
the index map
double m_heuristic; // a really simple heuristic
double m_distance; // altered by the algo: this id is the
distance
boost::default_color_type m_color;
};
struct EProp {
EProp() : m_weight( .0 ) {}
EProp( double weight ) : m_weight( weight ) {}
double m_weight;
};
typedef boost::adjacency_list< boost::vecS, boost::vecS,
boost::undirectedS, VProp, EProp > G;
typedef G::vertex_descriptor V;
typedef G::edge_descriptor E;
struct found_goal {};
template< class Vertex, class Edge >
class GoalVisitor : public boost::default_astar_visitor {
public:
GoalVisitor(Vertex goal) : m_goal(goal) {}
template <class Graph>
void examine_vertex(Vertex u, Graph& g) {
cout << "examine: " << u
<< endl;
if(u == m_goal) throw found_goal();
}
template <class Graph>
void discover_vertex(Vertex u, Graph& g) {
cout << "discover: " << u
<< endl;
}
template <class Graph>
void black_target(Edge u, Graph& g) {
cout << "black_target: " << boost::source( u, g )
<< " -- "
<< boost::target( u, g )
<< endl;
}
template <class Graph>
void edge_relaxed(Edge u, Graph& g) {
cout << "edge_relaxed: " << boost::source( u, g )
<< " -- "
<< boost::target( u, g )
<< endl;
}
template <class Graph>
void edge_not_relaxed(Edge u, Graph& g) {
cout << "edge_not_relaxed: " << boost::source( u, g )
<< " -- "
<< boost::target( u, g )
<< endl;
}
private:
Vertex m_goal;
};
template< class Graph, class CostType >
class DistanceHeuristic : public boost::astar_heuristic {
public:
DistanceHeuristic( Graph & graph ) : m_graph(graph) {}
template< class Vertex >
CostType operator()( Vertex u) {
return m_graph[u].m_heuristic;
}
private:
Graph & m_graph;
};
class EdgeWeightWriter {
public:
EdgeWeightWriter( G & graph ): m_graph( graph ) {}
template< class OStream >
void operator()( OStream& out, V v ) {
// out << " [label= \"" << v <<"\"]";
}
template< class OStream >
void operator()( OStream& out, E v ) {
out.precision( 30 );
out << " [label= \"" << m_graph[v].m_weight <<"\"]";
}
private:
G & m_graph;
};
int main() {
G g;
V ar[181];
for( unsigned int i = 0; i < 181; ++i ) {
ar[i] = add_vertex( VProp(i, 1.0), g );
}
// add_edge( ar[1], ar[18 ], EProp( 2.20307469298885294506362697575 ), g );
// add_edge( ar[0], ar[30 ], EProp( 1.58945958901181461087048774061 ), g );
// add_edge( ar[0], ar[66 ], EProp( 0.937232823257896585644743936427 ),
g );
// add_edge( ar[66], ar[100 ], EProp( 2.72761497732282665040770552878 ),
g );
// add_edge( ar[66], ar[101 ], EProp( 2.87914914272965027919326530537 ),
g );
// add_edge( ar[30], ar[142 ], EProp( 4.8843528076143511995610424492 ),
g );
// add_edge( ar[18], ar[142 ], EProp( 3.29201592753501959265349796624 ),
g );
add_edge( ar[1], ar[18 ], EProp( 2.20 ), g );
add_edge( ar[0], ar[30 ], EProp( 1.58 ), g );
add_edge( ar[0], ar[66 ], EProp( 0.93 ), g );
add_edge( ar[66], ar[100 ], EProp( 2.72 ), g );
add_edge( ar[66], ar[101 ], EProp( 2.87 ), g );
add_edge( ar[30], ar[142 ], EProp( 4.88 ), g );
add_edge( ar[18], ar[142 ], EProp( 3.29 ), g );
map< V, V > predecessor;
associative_property_map< map< V, V > > predecessorMap( predecessor );
/**
* solution to this: 1->18->142->30->0
*/
try {
astar_search(g, ar[0], DistanceHeuristic( g ),
predecessor_map( predecessorMap ).
weight_map( get(&EProp::m_weight, g) ).
color_map( get(&VProp::m_color, g) ).
distance_map( get(&VProp::m_distance, g) ).
visitor(GoalVisitor( ar[1] ) ) );
} catch ( found_goal ) {
cout << "found" << endl;
for(V v = ar[1];; v = predecessor[v]) {
cout << v;
if(predecessor[v] == v) break;
cout << "->";
}
cout << endl;
}
boost::write_graphviz( std::cerr, g,
EdgeWeightWriter( g ), EdgeWeightWriter( g ),
default_writer() );
}
