[Boost-users] [boost][graph] astar_search bug

Subject: [Boost-users] [boost][graph] astar_search bug
From: Andy Tompkins (atompkins_at_[hidden])
Date: 2010-02-10 16:48:23

Hi,

I have been upgrading some projects to use boost version 1.42.0 with
Visual Studio 2008 and found (I believe) a bug with astar_search.

I have attached a minimal program that will reproduce the problem, and a
patch file to correct it. I created a ticket (Ticket #3917) that has
these files attached and attached them to this.

Regards,
Andy Tompkins


// copied and modified from boost/libs/graph/example/knights-tour.cpp

//=======================================================================
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, 
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#include <boost/config.hpp>
#include <stdlib.h>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <boost/operators.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/shared_container_iterator.hpp>

using namespace std;
using namespace boost;

struct vertex_t
{
        vertex_t() : i(0) {}
        explicit vertex_t(int i) : i(i) {}
        vertex_t(vertex_t const& rhs) : i(rhs.i) {}

        bool operator==(vertex_t const& rhs) const {
                return i == rhs.i;
        }
        bool operator!=(vertex_t const& rhs) const {
                return !operator==(rhs);
        }

        int i;
};

struct edge_t
{
        edge_t() {}
        edge_t(vertex_t const& u, vertex_t const& v) : u(u), v(v) {}
        edge_t(edge_t const& rhs) : u(rhs.u), v(rhs.v) {}

        bool operator==(edge_t const& rhs) const {
                return u == rhs.u && v == rhs.v;
        }
        bool operator!=(edge_t const& rhs) const {
                return !operator==(rhs);
        }

        vertex_t u;
        vertex_t v;
};

struct graph_t
{
        typedef std::vector<vertex_t>::iterator vertex_iterator;
        typedef std::vector<vertex_t>::size_type vertices_size_type;
        typedef vertex_t vertex_descriptor;
        typedef edge_t edge_descriptor;
        typedef directed_tag directed_category;
        typedef disallow_parallel_edge_tag edge_parallel_category;

        struct category_t : public incidence_graph_tag, public vertex_list_graph_tag {};
        typedef category_t traversal_category;

        typedef shared_container_iterator<vector<edge_t> > out_edge_iterator;
        typedef size_t degree_size_type;

        typedef void adjacency_iterator;
        typedef void in_edge_iterator;
        typedef void edge_iterator;
        typedef void edges_size_type;

        explicit graph_t(int size)
        {
        for (int i=0; i<size; i++) {
                        m_vertices.push_back(vertex_t(i));
                }
        }

public:
        std::vector<vertex_t> m_vertices;
};

vertex_t source(edge_t const& e, graph_t const&)
{
        return e.u;
}

vertex_t target(edge_t const& e, graph_t const&)
{
        return e.v;
}

std::pair<graph_t::out_edge_iterator, graph_t::out_edge_iterator>
out_edges(vertex_t const& v, graph_t const& g)
{
        boost::shared_ptr<vector<edge_t> > c(new vector<edge_t> );
        if (v.i > 0) {
                c->push_back(edge_t(vertex_t(v.i-1), v));
        }
        if (static_cast<size_t>(v.i) < g.m_vertices.size()-1) {
                c->push_back(edge_t(v, vertex_t(v.i+1)));
        }
        
        return make_shared_container_range(c);
}

size_t out_degree(vertex_t const& v, graph_t const& g)
{
        std::pair<graph_t::out_edge_iterator, graph_t::out_edge_iterator> eis = out_edges(v, g);
        return std::distance(eis.first, eis.second);

}

std::pair<graph_t::vertex_iterator, graph_t::vertex_iterator>
vertices(graph_t& g) {
        return make_pair(g.m_vertices.begin(), g.m_vertices.end());
}

graph_t::vertices_size_type num_vertices(graph_t const& g) {
        return g.m_vertices.size();
}

struct vertex_index_map_t
{
        typedef int value_type;
        typedef int reference;
        typedef vertex_t key_type;
        typedef readable_property_map_tag category;
};
int get(vertex_index_map_t, vertex_t const& v) {
        return v.i;
}

struct edge_weight_map_t
{
        typedef double value_type;
        typedef double reference;
        typedef edge_t key_type;
        typedef readable_property_map_tag category;
};
double get(edge_weight_map_t, edge_t const& e) {
        return abs(e.u.i - e.u.i);
}
///////////////////////////////////////////////////////////////////////////////

struct h : public astar_heuristic<graph_t, double>
{
    double operator()(vertex_t const& v) const
        {
                return 0.0;
        }
};

int main(int argc, char *argv[])
{
        graph_t g(10);

        astar_search
                ( g
                , vertex_t(0)
                , h()
                , weight_map(edge_weight_map_t())
                  .vertex_index_map(vertex_index_map_t())
                );

        return 0;
}