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() ); }