Boost logo

Boost Users :

Subject: [Boost-users] astar_search_no_init
From: anilpanicker (anilpanicker_at_[hidden])
Date: 2011-07-20 08:00:43

I'm trying to compile the puzzle 8 given in this link

using astar_search_no_init()

but I get this error "error C2106: '=' : left operand must be l-value"
I'm using VS2010. Can someone please help me

Here is my entire code

using namespace std;
using namespace boost;

class puzzle_state_t: public vector<int>
        int m_row,m_col; // row and columns
        puzzle_state_t(int r,int c): vector<int>(r*c),m_row(r),m_col(c){}
        //another ctor with some iterator
        template<typename IteratorType>
        puzzle_state_t(int r,int c,IteratorType beg,IteratorType en):
        //find the cell in the vector
        // rows are numbered 0,1,2
        // cols are numbered 0,1,2
        inline int cell(int r, int c) const
                return r*m_col+c; //gives the index of vector
        //get value of a cell
        inline int get(int r, int c) const
                int index= cell(r,c);
                return operator[] (index);// returns value
        //move between two cells
        inline void move(int i,int j)
                int tmp=operator[] (j);
        //find coordinates of an offset
        inline void coords(int i, int &r, int &c) const

        friend ostream& operator <<(ostream &out, const puzzle_state_t &p)
                for(int i = 0; i < p.m_row; ++i)
                        for(int j = 0; j < p.m_col; ++j)

                                if(p.get(i, j) > 0)
                                cout << p.get(i, j)<<"\t" ;
                                cout << "-"<<"\t";
                                cout << endl;
        return out;


//1. find out the cell with zero
void generate_children(const puzzle_state_t &p, list<puzzle_state_t>
&children )
        puzzle_state_t::const_iterator const_it= find(p.begin(),p.end(),0);
        int soffset= const_it-p.begin(); //index of array
        int sr,sc;
        p.coords(soffset,sr,sc);// got the cell
        {//mode tile to left
                children.back().move(soffset,p.cell(sr,sc-1) );
        {//move to right
        {//move tile to above
                children.back().move(soffset,p.cell(sr-1,sc) );
                children.back().move(soffset,p.cell(sr+1,sc) );

//Graph and related types

//a new property tag
struct vertex_puzzle_state_t
        typedef vertex_property_tag kind;

//define VertexProperties
typedef property&lt;vertex_color_t, default_color_type,
property&lt;vertex_rank_t, unsigned int,
property&lt;vertex_distance_t, unsigned int,
property&lt;vertex_predecessor_t, unsigned int,
property&lt;vertex_puzzle_state_t, puzzle_state_t,
property&lt;vertex_index_t,unsigned int&gt; > > > > > VertexProperties;
//define EdgeProperties
typedef property&lt;edge_weight_t, unsigned int&gt; EdgeProperties;
//Define Graph_type
typedef graph_traits<graph_t>::vertex_descriptor vertex_t;
typedef graph_traits<graph_t>::edge_descriptor edge_t;
typedef graph_traits<graph_t>::vertex_iterator vit;
typedef graph_traits<graph_t>::edge_iterator eit;
//property maps
//Named Parameter version
//IN:weight_map- length of each edge
//IN: vertex_index_map-
typedef property_map&lt;graph_t,edge_weight_t&gt;::type WeightMap;
typedef property_map&lt;graph_t,vertex_index_t&gt;:: type IndexMap;
//OUT: predecessor_map
//Out: distance_map
//OUT: rank_map
//OUT: color_map
typedef property_map&lt;graph_t,vertex_predecessor_t&gt;::type PredMap;
typedef property_map&lt;graph_t,vertex_distance_t&gt;::type DistanceMap;
typedef property_map&lt;graph_t,vertex_rank_t&gt;::type RankMap;
typedef property_map&lt;graph_t,vertex_color_t&gt;::type ColorMap;
// custom mpa
typedef property_map&lt;graph_t,vertex_puzzle_state_t&gt;::type StateMap;

struct found_goal{};

template<typename Vertex>
class puzzle_visitor : public boost::default_astar_visitor
        list<vertex_t> &m_verticesList;
        puzzle_state_t &m_goal_state;
        puzzle_visitor(list<vertex_t> & vlist,puzzle_state_t &goal):
    template <class Graph>
        void examine_vertex(Vertex u, Graph& g)
        {// add states and break if it reached goal state
                StateMap smap= get(vertex_puzzle_state_t,g);
                 WeightMap wmap= get(edge_weight_t,g);
                 ColorMap cmap= get(vertex_color_t,g);
                        throw found_goal();
                //add successors of state
                list<puzzle_state_t> new_vertices;
                generate_children(smap[u],new_vertices );
                list<puzzle_state_t>::iterator it;
                for(it=new_vertices.begin(); it != new_vertices.end(); ++it)
                        //make sure this is a new state
                        vit vi,vend;
                        for(tie(vi,vend)=vertices(g); vi != vend; ++vi)
                                if(*vi== *it )
                        if(vi != vend)//not new
                                pair&lt;edge_t,bool&gt; eAdded=add_edge(u,*vi,g);
                                Vertex v= add_vertex(g);
                                pair&lt;edge_t,bool&gt; eAdded=add_edge(u,v,g);


// the distance huristics
// sum of (row_goal-row_current) + (col_goal-col_current) for all tiles
class manhattan_dist: public astar_heuristic&lt;graph_t,unsigned int&gt;
         puzzle_state_t &m_goal_state;
         StateMap m_smap;
         inline unsigned int myabs(int i)
                 return static_cast<unsigned int> (i<0 ? -i:i);
        manhattan_dist(puzzle_state_t &goal, StateMap &smap):
          unsigned int operator() (vertex_t u)
                  unsigned int md=0;
                  puzzle_state_t::const_iterator it_i,it_j;
                  int ir,ic,jr,jc;
                  for(it_i=m_smap[u].begin(); it_i != m_smap[u].end(); ++it_i)
                          m_smap[u].coords(it_i - m_smap[u].begin(), ir, ic);
                                m_goal_state.coords(it_j - m_goal_state.begin(), jr, jc);
                                md += myabs(jr - ir) + myabs(jc - ic);
                  return md;

int main()
        //set up start_state and goal_puzzle state
        graph_t g;
        list<vertex_t> examine_seq;
        IndexMap indexMap= get(vertex_index,g);
        WeightMap wmap= get(edge_weight_t (),g);
        DistanceMap dmap= get(vertex_distance,g);
        ColorMap cmap= get(vertex_color,g);
        PredMap predessors= get(vertex_predecessor,g);
        RankMap rmap= get(vertex_rank,g);
        //custom map
        StateMap smap= get(vertex_puzzle_state_t (),g);
        //add first vertex
        vertex_t start = add_vertex(g);
        int sstart []= {1,3,4,8,0,2,7,6,5};
        int sgoal []= {1,2,3,8,0,4,7,6,5};
        //smap[start]= puzzle_state_t(3,3,&sstart[0],&sstart[9] );
        puzzle_state_t p(3,3);
        puzzle_state_t goal(3,3);
        for(int i=0; i<9; ++i)
        smap[start]= p;
        cout<<"Start state"<&lt;endl&lt;&lt;endl;
        cout&lt;&lt; smap[start]&lt;&lt;endl;
        cout&lt;&lt;&quot;Goal state&quot;&lt;&lt;endl&lt;&lt;endl;

        puzzle_visitor&lt;vertex_t&gt; vis(examine_seq,goal);
        manhattan_dist m_dist_heuristic(goal,smap);

                                                 start, //source
                                                 m_dist_heuristic,// heuristic
                                                 visitor(vis).// vis
                                                 vertex_index_map(indexMap).// IN: index_map
                                                 weight_map(wmap).//IN: weight_map

        return 0;

View this message in context:
Sent from the Boost - Users mailing list archive at

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at