[Boost-users] astar_search_no_init

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 

http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf

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

#include<boost/graph/adjacency_list.hpp>
#include<boost/graph/astar_search.hpp>
#include<iostream>
#include<vector>
#include<list>
using namespace std;
using namespace boost;

class puzzle_state_t: public vector<int>
{
public:
        int m_row,m_col; // row and columns
        puzzle_state_t(){}
        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):
vector<int>(beg,en)m_row(r),m_col(c){}
        //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);
                operator[](j)=operator[](i);
                operator[](i)=tmp;
        }
        //find coordinates of an offset
        inline void coords(int i, int &r, int &c) const
        {
                r=i/m_col;
                c=i%m_col;
        }

        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" ;
                                else
                                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
        if(sc>0)
        {//mode tile to left
                children.push_back(p);
                children.back().move(soffset,p.cell(sr,sc-1) );
        }
        if(sc&lt;p.m_col-1)
        {//move to right
                children.push_back(p);
                children.back().move(soffset,p.cell(sr,sc+1));
        }
        if(sr&gt;0)
        {//move tile to above
                children.push_back(p);
                children.back().move(soffset,p.cell(sr-1,sc) );
        }
        if(sr&lt;p.m_row-1)
        {
                children.push_back(p);
                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
adjacency_list&lt;listS,vecS,undirectedS,VertexProperties,EdgeProperties,no_property,listS&gt;
graph_t;
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
{
private:
        list<vertex_t> &m_verticesList;
        puzzle_state_t &m_goal_state;
public:
        puzzle_visitor(list<vertex_t> & vlist,puzzle_state_t &goal):
m_verticesList(vlist),m_goal_state(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);
                if(smap[u]==m_goal)
                        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 )
                                        break;
                        }
                        if(vi != vend)//not new
                        {
                                pair&lt;edge_t,bool&gt; eAdded=add_edge(u,*vi,g);
                                if(eAdded)
                                        put(wmap,eAdded.first);
                        }else
                        {//new
                                Vertex v= add_vertex(g);
                                put(cmap,v,white_color);
                                pair&lt;edge_t,bool&gt; eAdded=add_edge(u,v,g);
                                if(eAdded)
                                        put(wmap,eAdded.first)

                        }
                
                }
        }
};

// 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);
         }
public:
        manhattan_dist(puzzle_state_t &goal, StateMap &smap):
          m_goal_state(goal),m_smap(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)
                  {
                          it_j=find(m_goal_state.begin(),m_goal_state.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;
        //maps
        //IN
        IndexMap indexMap= get(vertex_index,g);
        WeightMap wmap= get(edge_weight_t (),g);
        //OUT
        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);
        put(cmap,start,white_color);
        put(dmap,start,0);
        //
        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)
        {
                p[i]=sstart[i];
                goal[i]=sgoal[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;
        cout&lt;&lt;goal&lt;&lt;endl;

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

        
        
        astar_search_no_init(g,
                                                 start, //source
                                                 m_dist_heuristic,// heuristic
                                                 visitor(vis).// vis
                                                 vertex_index_map(indexMap).// IN: index_map
                                                 weight_map(wmap).//IN: weight_map
                                                 predecessor_map(predessors).//OUT
                                                 distance_map(dmap).//OUT
                                                 color_map(cmap).//OUT
                                                 rank_map(rmap)//OUT
                                                 );
                                                 
    

        return 0;
}

--
View this message in context: http://boost.2283326.n4.nabble.com/astar-search-no-init-tp3680535p3680535.html
Sent from the Boost - Users mailing list archive at Nabble.com.