Пятнашки boost library

Предисловие

Реализация алгоритма на основе библиотеки boost полностью рабочая, по заявлению разработчиков http://www.boost.org/libs/graph/doc/astar_search.html алгоритм поддерживает функционал Implicit Graph. Однако в реализации библиотеки мы можем увидеть обратное, граф образуеться из MutableTree, который имеет фиксированный размер. Что противоречит документации. Думаю в ближайшее время пач будет выпущен и данная реализация алгоритма автоматически начет работать.

Исходный код

#include <boost/graph/astar_search.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <boost/random.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/tokenizer.hpp>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <vector>
#include <list>
#include <iostream>
#include <fstream>
#include <math.h> // for sqrt

class AllError:public std::exception
{
 std::string str;
public:
 AllError(const char*p):str(p)
 {
 }
 const char* what()const throw()
 {
  return str.c_str();
 }
};

typedef int TokenMovePosition;
typedef std::vector<TokenMovePosition> TokenFree;

class TokenPosition16:public std::vector<int>
{
public:
 TokenPosition16()
 {
 }
 const_iterator Find(int k) const
 {
  const_iterator i=begin();
  for(;i!=end();i++)
  {
   if(*i==k)
    return i;
  }
  return i;
 };
 void Reset()
 {
  assign(16,0);
  for(int i=0;i<size();i++)
  {
   at(i)=i+1;
  }
 }
 int Calc(const TokenPosition16 &goal)
 {
  //int err=0;
  //for(int i=0;i<16;i++)
  //{
  // err+=at(i)!=goal.at(i);
  //}
  // manhattan distance
  int err=0;
  for(int i=0;i<16;i++)
  {
   int goalpos=std::distance(goal.begin(),goal.Find(at(i)));
   int cols=std::abs(goalpos%4-i%4);
   int rows=std::abs(goalpos/4-i/4);
   err+=cols+rows;
  }
  return err;
 }
 void Random()
 {
  clear();
  int tokens[]={2,11,14,5, 9,7,16,4, 13,12,1,3, 8,10,15,6};
  assign(&tokens[0],&tokens[sizeof(tokens)/sizeof(int)]);
 };
 TokenPosition16 Convert(TokenMovePosition to) const
 {
  TokenPosition16 t;
  t.assign(begin(),end());
  iterator i=std::find(t.begin(),t.end(),16);
  if(i==t.end())
   throw AllError("16 not found");
  int bak=t.at(to);
  t.at(to)=*i;
  *i=bak;
  return t;
 }
 TokenFree GetTokenFree() const
 {
  const_iterator i=std::find(begin(),end(),16);
  if(i==end())
   throw AllError("16 not found");
  TokenFree tf;
  tf.reserve(4);
  size_t pos=std::distance(begin(),i);
  // move up
  if(pos>3)
   tf.push_back(pos-4);
  // move down
  if(pos<13)
   tf.push_back(pos+4);
  // move left
  if(pos%4!=0)
   tf.push_back(pos-1);
  // move right
  if((pos+1)%4!=0)
   tf.push_back(pos+1);
  return tf;
 }
 bool operator < (const TokenPosition16&t) const
 {
  const int icount=16;
  if(t.size()!=icount || size()!=icount)
   throw AllError("Worong tokens");
  int i=0;
  int ret=0;
  while(i<icount && !(ret=at(i)-t.at(i)))
  {
   i++;
  };
  return ret<0;
 }
};

typedef TokenPosition16 TokenPosition;

std::ostream& operator << (std::ostream &o,const TokenPosition& t)
{
 for(int i=0;i<t.size();i++)
 {
  if(i%4==0)
   o<<std::endl;
  o.width(3);
  if(t[i]==16)
   o<<" ";
  else
   o<<t[i];
 }
 return o;
}

enum vertex_token_t { vertex_token };

namespace boost
{
 BOOST_INSTALL_PROPERTY(vertex, token);
}

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
  boost::property<boost::vertex_color_t, boost::default_color_type,
  boost::property<vertex_token_t, TokenPosition ,
  boost::property<boost::vertex_rank_t, unsigned int,
  boost::property<boost::vertex_distance_t, unsigned int,
  boost::property<boost::vertex_predecessor_t, unsigned int> > > > >,
  boost::property<boost::edge_weight_t, int> > mygraph_t;
typedef boost::property_map<mygraph_t, boost::edge_weight_t>::type WeightMap;
typedef boost::property_map<mygraph_t, boost::vertex_index_t>::type IndexMap;
typedef boost::property_map<mygraph_t, vertex_token_t>::type TokenMap;

struct TokenHolder
{
 TokenPosition tp;
 mygraph_t::vertex_descriptor vertex;
 TokenHolder(const TokenPosition&tp,mygraph_t::vertex_descriptor v):tp(tp),vertex(v){}
 TokenHolder(const TokenPosition&tp):tp(tp){}
 bool operator < (const TokenHolder& t) const
 {
  return tp<t.tp;
 }
};

typedef std::set<TokenHolder> TokenSet;
template<class Graph,class TokenPosition>

typename Graph::vertex_descriptor add_vertex(const TokenPosition&tp,TokenSet& ts,Graph&g)
{
 TokenSet::const_iterator i=ts.find(TokenHolder(tp));
 if(i!=ts.end())
  return i->vertex;
 typename boost::property_map<Graph, vertex_token_t>::type tokenmap=boost::get(vertex_token, g);
 Graph::vertex_descriptor v=boost::add_vertex(typename Graph::vertex_property_type(boost::white_color),g);
 tokenmap[v]=tp;
 ts.insert(TokenHolder(tokenmap[v],v));
 return v;
}

template <class Graph, class CostType> class fifth_heuristic : public boost::astar_heuristic<Graph, CostType>
{
public:
 typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;

 fifth_heuristic(const TokenPosition&t,TokenSet&ts):m_goal(t),m_ts(ts) {}

 CostType operator()(Vertex u)
 {
  ;
  return 1;
 }
private:
 TokenPosition m_goal;
 TokenSet& m_ts;
};

struct found_goal {};

class astar_goal_visitor : public boost::default_astar_visitor
{
public:
 TokenPosition m_goal;
 TokenSet* m_ts;
 template <class Vertex,class Graph>
 void examine_vertex(Vertex u, Graph& g)
 {
  boost::property_map<Graph, vertex_token_t>::type tokenmap=boost::get(vertex_token, g);
  if(tokenmap[u].Calc(m_goal)==0)
   throw found_goal();
  TokenFree tf=tokenmap[u].GetTokenFree();
  for(TokenFree::iterator i=tf.begin();i!=tf.end();i++)
  {
   typename Graph::vertex_descriptor te=add_vertex(tokenmap[u].Convert(*i),*m_ts,g);
   typename Graph::edge_descriptor e=boost::add_edge(u,te,typename Graph::edge_property_type(1),g).first;
   std::cout<<tokenmap[te]<<std::endl;
  };
 }
};

template<class T> class astar_implicit_graph:public T
{
public:
 void examine_vertex(typename mygraph_t::vertex_descriptor u, const mygraph_t& g)
 {
  T::examine_vertex(u,const_cast<mygraph_t&>(g));
 }
};

int main(int argc, char **argv)
{
 mygraph_t g;
 WeightMap weightmap = boost::get(boost::edge_weight, g);
 IndexMap indexmap = boost::get(boost::vertex_index, g);
 TokenMap tokenmap = boost::get(vertex_token,g);
 TokenSet tokenset;
 TokenPosition initial;
 initial.Random();
 mygraph_t::vertex_descriptor ts=add_vertex(initial,tokenset,g);
 std::cout<<tokenmap[ts]<<std::endl;
 try
 {
  TokenPosition goal;
  goal.Reset();
  astar_implicit_graph<astar_goal_visitor> vis;
  vis.m_ts=&tokenset;
  vis.m_goal=goal;
  boost::astar_search(g, ts,
   fifth_heuristic<mygraph_t,int>(goal,tokenset),
   boost::visitor(vis).
   color_map(boost::get(boost::vertex_color,g)).
   rank_map(boost::get(boost::vertex_rank,g)).
   distance_map(boost::get(boost::vertex_distance,g)).
   predecessor_map(boost::get(boost::vertex_predecessor,g)));
 }catch(found_goal fg)
 {
  return 0;
 }
 return 0;
}