pgRouting

Changeset 72

Show
Ignore:
Timestamp:
12/10/07 14:11:15 (1 year ago)
Author:
anton
Message:

Shooting* restrictions fixed, crashes fixed

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • trunk/core/src/shooting_star_boost_wrapper.cpp

    r43 r72  
    2121 
    2222#include <boost/config.hpp> 
    23 #include <iostream> 
    24 #include <fstream> 
    2523 
    2624#include <boost/graph/graph_traits.hpp> 
    …… 
    3634using namespace boost; 
    3735 
    38 // Maximal number of nodes in the path (to avoid infinite loops) 
    39 #define MAX_NODES 1000000 
    40  
    4136struct Edge 
    4237{ 
    …… 
    4540  int target; 
    4641  float8 cost; 
    47   float8 distance; 
    48   float8 rank; 
    49   std::map< int, std::pair<float8, std::vector<int> >, std::less<int> > adjacent_edges; 
    50  
    51   std::vector< int > history; 
    52  
     42  float distance; 
     43  float rank; 
     44  std::map< int, vector< std::pair<float, std::vector<int> > >, std::less<int> > adjacent_edges; 
    5345  default_color_type color; 
    54    
    55   std::size_t index; 
    56  
    57   adjacency_list_traits<vecS, vecS, directedS>::edge_descriptor predecessor; 
    5846}; 
    5947         
    …… 
    6351  float8 x; 
    6452  float8 y; 
    65  
    66   default_color_type color; 
    67    
    68   float8 cost; 
    69    
    7053}; 
    7154 
    72  
    73 struct found_goal {}; // exception for termination 
     55// exception for termination 
     56struct found_goal  
     57{ 
     58  public: 
     59    found_goal() {} 
     60    found_goal(const found_goal &fg) {} 
     61    ~found_goal() {} 
     62};  
    7463 
    7564// visitor that terminates when we find the goal 
    …… 
    7867{ 
    7968public: 
    80   shooting_star_goal_visitor(Edge goal) : m_goal(goal) {} 
     69  shooting_star_goal_visitor(Edge goal, int max_id) : m_goal(goal){} 
     70  shooting_star_goal_visitor(const shooting_star_goal_visitor &gv) : m_goal(gv.m_goal){} 
     71  ~shooting_star_goal_visitor(){} 
    8172 
    8273  template <class Graph> 
    83   void examine_edge(Edge e, Graph& g) { 
    84     if(g[e].id == g[m_goal].id) 
     74  void examine_edge(Edge e, Graph& g)  
     75  { 
     76    if( g[e].id == g[m_goal].id) 
     77    { 
    8578      throw found_goal(); 
     79    } 
    8680  } 
    8781  template <class Graph> 
    …… 
    8983private: 
    9084  Edge m_goal; 
     85  int  e_max_id; 
    9186}; 
    9287 
    9388 
    9489template <class Graph, class CostType> 
    95 class distance_heuristic : public astar_heuristic<Graph, CostType> 
     90class distance_heuristic 
    9691{ 
    9792public: 
    …… 
    10095  CostType operator()(Edge e) 
    10196  { 
    102     CostType dx = m_g[target(m_goal, m_g)].x - m_g[target(e, m_g)].x; 
    103     CostType dy = m_g[target(m_goal, m_g)].y - m_g[target(e, m_g)].y; 
     97    CostType dx = m_g[source(m_goal, m_g)].x - m_g[source(e, m_g)].x; 
     98    CostType dxt = m_g[target(m_goal, m_g)].x - m_g[target(e, m_g)].x; 
     99    CostType dy = m_g[source(m_goal, m_g)].y - m_g[source(e, m_g)].y; 
     100    CostType dyt = m_g[target(m_goal, m_g)].y - m_g[target(e, m_g)].y; 
    104101    //You can choose any heuristical function from below 
    105102    //return ::max(dx, dy); 
    106103    //return ::sqrt(dx * dx + dy * dy)/2; 
    107104    //return 0; 
    108     return (::fabs(dx)+::fabs(dy))/2; 
     105    return (min(::fabs(dx),::fabs(dxt))+min(::fabs(dy),::fabs(dyt)))/2; 
    109106  }  
    110107private: 
    …… 
    118115graph_add_edge(G &graph, int id, int source, int target,  
    119116               float8 cost, float8 s_x, float8 s_y, float8 t_x, float8 t_y,  
    120                std::map< int, std::pair<float8, vector<int> >, std::less<int> > adjacent_edges) 
     117               std::map< int, vector< std::pair<float, vector<int> > >, std::less<int> > adjacent_edges) 
    121118{ 
    122119 
    …… 
    124121  bool inserted; 
    125122 
    126   if (cost < 0) // edges are not inserted in the graph if cost is negative 
    127     return; 
     123  if (cost < 0) // edges are inserted as unpassable if cost is negative 
     124    cost = MAX_COST; 
    128125 
    129126  tie(e, inserted) = add_edge(source, target, graph); 
    …… 
    131128  graph[e].cost = cost; 
    132129  graph[e].id = id; 
    133  
    134 //  put(edge_index, graph, graph[e], id); 
    135130   
    136131  graph[e].source = source; 
    …… 
    138133   
    139134  graph[e].adjacent_edges = adjacent_edges; 
     135 
     136  graph[e].rank = 0; 
     137  graph[e].distance = 0; 
     138 
    140139   
    141140  typedef typename graph_traits<G>::vertex_descriptor Vertex; 
    …… 
    161160 
    162161  typedef adjacency_list<vecS, vecS, directedS, Vertex, Edge> graph_t; 
    163    
     162 
    164163  typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; 
    165164  typedef graph_traits < graph_t >::edge_descriptor edge_descriptor; 
    166165 
    167   const unsigned int num_nodes = /*1*/count*2; 
     166  const unsigned int num_nodes = count*2; 
    168167   
    169168  int z; 
    170   int src, trg, offset; 
     169  int src, trg, offset, rule_num; 
    171170   
    172171  graph_t graph(num_nodes); 
    173172 
    174   std::map< int, std::pair<float8, vector<int> >, std::less<int> > adjacent_edges; 
     173  std::map< int, vector< std::pair<float, vector<int> > >, std::less<int> > adjacent_edges; 
    175174 
    176175  std::map< int, int, std::less<int> > vertices; 
    177  
    178   offset = 0; 
    179    
     176   
     177  vector<int> rule; 
     178 
     179  offset = 1; 
     180  rule_num = 0; 
     181 
    180182  for (std::size_t j = 0; j < count; ++j) 
    181183  { 
    182184    //Vertex ids renumbering moved here 
    183      
    184185    src = edges_array[j].source; 
    185186    trg = edges_array[j].target; 
    186  
    187     if(vertices[src]==NULL) 
    188     //if (vertices.find(edges_array[j].source) == vertices.end()) 
     187     
     188    if(vertices[src]==0) 
    189189    { 
    190190      vertices[src]=j+offset; 
    191       edges_array[j].source=j+offset; 
    192        
    193     } 
    194     else 
    195     { 
    196       edges_array[j].source=vertices[src]; 
    197     } 
    198  
    199     if(vertices[trg]==NULL) 
    200     //if (vertices.find(edges_array[j].target) == vertices.end())     
    201     { 
    202       offset++; 
    203    
     191    } 
     192    edges_array[j].source=vertices[src]; 
     193     
     194    if(vertices[trg]==0) 
     195    { 
     196      offset++;       
    204197      vertices[trg]=j+offset; 
    205       edges_array[j].target=j+offset; 
    206     } 
    207     else 
    208     { 
    209       edges_array[j].target=vertices[trg]; 
    210     } 
    211      
    212     adjacent_edges[edges_array[j].id].first = edges_array[j].to_cost; 
    213  
     198    } 
     199    edges_array[j].target=vertices[trg]; 
     200     
    214201    for(z=0; z<MAX_RULE_LENGTH;++z) 
    215202    { 
    216203      if(edges_array[j].rule[z] > 0) 
    217204      { 
    218         adjacent_edges[edges_array[j].id].second.push_back(edges_array[j].rule[z]); 
     205        rule.push_back(edges_array[j].rule[z]); 
    219206      } 
     207    } 
     208 
     209    if(edges_array[j].to_cost > 0) 
     210    { 
     211      adjacent_edges[edges_array[j].id].push_back(std::pair<float8, vector<int> > (edges_array[j].to_cost, rule) ); 
     212      rule.clear(); 
    220213    } 
    221214 
    …… 
    227220                                               edges_array[j].s_x, edges_array[j].s_y,  
    228221                                               edges_array[j].t_x, edges_array[j].t_y, adjacent_edges); 
    229  
     222     
    230223      if (!directed || (directed && has_reverse_cost)) 
    231224      { 
    …… 
    241234        } 
    242235 
     236 
     237      if(adjacent_edges[edges_array[j].id].size() > 0) 
     238      { 
     239        adjacent_edges[edges_array[j].id+e_max_id].assign( adjacent_edges[edges_array[j].id].begin(), adjacent_edges[edges_array[j].id].end() ); 
     240        adjacent_edges.erase(edges_array[j].id); 
     241      } 
     242 
     243 
    243244        graph_add_edge<graph_t, edge_descriptor>(graph, 
    244245                                               edges_array[j].id+e_max_id, edges_array[j].target,  
    …… 
    249250 
    250251    adjacent_edges.clear(); 
    251      
    252     } 
    253   } 
    254      
    255   std::map< int, edge_descriptor, std::less<int> > predecessors; 
     252    rule_num = 0; 
     253    } 
     254    else 
     255    { 
     256      rule_num++; 
     257    } 
     258  } 
     259   
    256260   
    257261  edge_descriptor source_edge; 
    …… 
    261265   
    262266  graph_traits<graph_t>::edge_iterator ei, ei_end; 
    263   int index;     
    264  
    265   index = 1; 
    266    
    267   for(tie(ei, ei_end) = edges(graph); ei != ei_end; ++ei, ++index) 
    268     graph[*ei].index = index;     
    269      
     267 
    270268  for(tie(ei, ei_end) = edges(graph); ei != ei_end; ++ei)  
    271269  { 
    …… 
    276274      break; 
    277275    } 
     276 
    278277  } 
    279278 
    …… 
    283282    return -1; 
    284283  } 
     284 
    285285 
    286286  for(tie(ei, ei_end) = edges(graph); ei != ei_end; ++ei)  
    …… 
    294294  } 
    295295 
     296 
    296297  if (!target_found) 
    297298  { 
    …… 
    300301  } 
    301302 
    302   std::vector<float8> distances(num_edges(graph)); 
    303    
    304   std::vector<default_color_type> edge_colors(num_edges(graph), color_traits<default_color_type>::white()); 
    305  
    306   property_map<graph_t, std::vector< int > Edge::*>::type history = get(&Edge::history, graph); 
    307  
    308   property_map<graph_t, std::size_t Edge::*>::type edge_index = get(&Edge::index, graph); 
    309  
    310   property_map<graph_t, float8 Edge::*>::type rank = get(&Edge::rank, graph); 
    311   property_map<graph_t, float8 Edge::*>::type distance = get(&Edge::distance, graph); 
     303  property_map<graph_t, int Edge::*>::type edge_index = get(&Edge::id, graph); 
     304 
     305  std::map< int, edge_descriptor, std::less<int> > predecessors; 
     306   
     307  property_map<graph_t, float Edge::*>::type rank = get(&Edge::rank, graph); 
     308  property_map<graph_t, float Edge::*>::type distance = get(&Edge::distance, graph); 
    312309 
    313310  try  
    …… 
    318315       weight_map(get(&Edge::cost, graph)). 
    319316       weight_map2(get(&Edge::adjacent_edges, graph)). 
    320        vertex_color_map(get(&Vertex::color, graph)). 
    321317       edge_color_map(get(&Edge::color, graph)). 
    322        visitor(shooting_star_goal_visitor<edge_descriptor>(target_edge)), 
     318       visitor(shooting_star_goal_visitor<edge_descriptor>(target_edge, e_max_id)), 
    323319       edge_index, 
    324320       distance, rank, 
    325        history,  
    326321       predecessors, e_max_id 
    327322       ); 
    328323 
    329324  }  
    330   catch(found_goal fg) { 
     325  catch(found_goal &fg)  
     326  { 
    331327   
    332328    vector<edge_descriptor> path_vect; 
    …… 
    337333    while (target_edge != source_edge)  
    338334      { 
     335         
    339336        if ((target_edge == predecessors[graph[target_edge].id]) && (predecessors[graph[target_edge].id] != source_edge)) 
    340337        { 
    …… 
    346343        target_edge = predecessors[graph[target_edge].id]; 
    347344 
    348         if(target_edge == predecessors[graph[target_edge].id] ) 
    349           continue; 
    350  
    351345        path_vect.push_back(target_edge); 
    352346 

  • trunk/core/src/shooting_star.h

    r43 r72  
    2222#define _SHOOTING_STAR_H 
    2323#define MAX_RULE_LENGTH 5 
     24 
     25#define MAX_NODES 1000000 
     26#define MAX_COST  100000 
    2427 
    2528#include "postgres.h" 

  • trunk/core/src/shooting_star_relax.hpp

    r43 r72  
    1818#include <boost/property_map.hpp> 
    1919 
    20 #include <iostream> 
    21 #include <fstream> 
    2220#include <postgres.h> 
     21 
     22#define U_TURN_COST 100000 
    2323 
    2424bool is_equal ( int a[], int b[], int size ) 
    …… 
    5656    template <class Edge, class Graph, class WeightMap, class EdgeMap, 
    5757            class PredecessorMap, class DistanceMap, class CostMap, 
    58             class HistoryMap, class BinaryFunction, class BinaryPredicate> 
     58            class BinaryFunction, class BinaryPredicate> 
    5959    bool relax(Edge e,  
    6060               Edge pe,  
    6161               const Graph& g, const WeightMap& w, const EdgeMap& em, 
    6262               PredecessorMap& p, DistanceMap& d, CostMap& c, 
    63                HistoryMap& his, 
    6463               const BinaryFunction& combine, const BinaryPredicate& compare, 
    6564               int e_max_id) 
    …… 
    8180       
    8281      W w_e = get(w, e); 
    83        
    84       //myfile<<"w(e) = "<<w_e<<"\n"<<std::flush; 
    85  
    86       //myfile<<"cost("<<g[e].id<<") = "<<get(c, e)<<"\n"<<std::flush; 
    87  
    88       //myfile<<"d("<<g[e].id<<") = "<<get(d, e)<<"\n"<<std::flush; 
    89  
    90       //myfile<<g[u].id<<" - "<<g[v].id<<" : d_e="<<d_e<<"\n"<<std::flush; 
    91  
    9282 
    9383      //edge where we came from 
    9484      bool edge_exists; 
    95       //Edge pe; 
    96        
    97       //pe = get(p, g[e].id); 
    9885       
    9986      W w_pe_e; 
    10087 
    101       //E w_pe = get(em, pe); 
    10288      E w_pe = get(em, e); 
    10389       
    104       bool contains = false; 
     90      int contains = -1; 
    10591         
    106  
    107       //myfile<<"w(pe, e) = "<<w_pe_e<<"\n"<<std::flush; 
    108  
    109       //myfile<<"id = "<<g[e].id<<", size = "<<w_pe[g[e].id].second.size()<<"\n"<<std::flush; 
    110  
    11192      Edge ce = pe; 
    11293      int e_id; 
    …… 
    11596      typedef typename std::vector<Edge>::iterator It; 
    11697 
    117       //for(int i=w_pe[g[e].id].second.size()-1; i>=0; --i) 
     98      for(int i=0; i< w_pe[g[e].id].size(); ++i) 
    11899       
    119       if(w_pe[g[e].id].second.size() < 1 || w_pe[g[e].id].second.back() > 0) 
    120       for(int i=0; i<w_pe[g[e].id].second.size(); ++i) 
     100      if(w_pe[g[e].id].at(i).second.size() < 1 || w_pe[g[e].id].at(i).second.back() > 0) 
     101      { 
     102       
     103      for(int j=0; j<w_pe[g[e].id].at(i).second.size(); ++j) 
    121104      { 
    122105        e_id = g[ce].id; 
    123         //myfile<<"e_id="<<e_id<<", second["<<g[e].id<<"]="<<w_pe[g[e].id].second.at(i)<<"\n"<<std::flush; 
    124106         
    125         if(w_pe[g[e].id].second.at(i) == -1) 
     107        if(w_pe[g[e].id].at(i).second.at(j) == -1) 
    126108          continue; 
    127            
    128         if(w_pe[g[e].id].second.at(i) == e_id || w_pe[g[e].id].second.at(i)+e_max_id == e_id) 
     109         
     110        if(w_pe[g[e].id].at(i).second.at(j) == e_id || w_pe[g[e].id].at(i).second.at(j)+e_max_id == e_id|| 
     111           w_pe[g[e].id].at(i).second.at(j) == e_id+e_max_id || w_pe[g[e].id].at(i).second.at(j)+e_max_id == e_id+e_max_id) 
    129112        { 
    130          contains = true; 
     113         contains = i; 
    131114         edge_h.push_back(ce); 
    132115        } 
    133         else 
     116        else if(i == contains) 
    134117        { 
    135          contains = false; 
     118         contains = -1; 
    136119        } 
    137120         
    …… 
    139122      } 
    140123       
     124      } 
     125       
    141126      //calculate w_pe_e 
    142       if(contains) 
     127      if(contains >= 0) 
    143128      { 
    144  
    145         w_pe_e = w_pe[g[e].id].first; 
    146  
    147  
     129        w_pe_e = w_pe[g[e].id].at(contains).first; 
     130      } 
     131      else if(abs(g[e].id-g[pe].id) == e_max_id) 
     132      { 
     133        w_pe_e = U_TURN_COST; 
    148134      } 
    149135      else 
    …… 
    151137        w_pe_e = 0; 
    152138      } 
    153          
     139 
    154140      //Ugly combination with w_e_pe. 
    155141 

  • trunk/core/src/shooting_star_search.hpp

    r43 r72  
    2828#include "edge_visitors.hpp" 
    2929 
    30 #include <iostream> 
    31 #include <fstream> 
    32  
    33   template <class Edge> 
    34   struct EdgeRankCompare { 
    35     bool operator()(const Edge& LHS, const Edge& RHS) { 
    36       return (LHS.rank < RHS.rank); 
    37     } 
     30template <class Edge> 
     31struct EdgeRankCompare  
     32{ 
     33  bool operator()(const Edge& LHS, const Edge& RHS)  
     34  { 
     35    return (LHS.rank < RHS.rank); 
     36  } 
    3837                 
    39   }; 
    40  
    41   template <class Edge, class Container, class Cmp> 
    42       class edge_queue : public std::priority_queue<Edge, Container, Cmp> 
    43   { 
    44   protected: 
    45     using std::priority_queue< Edge, Container, Cmp >::c; 
    46     using std::priority_queue< Edge, Container, Cmp >::comp; 
    47      
    48   public: 
    49       void sort() 
    50       { 
    51         sort_heap(c.begin(), c.end(), comp); 
    52       }    
    53   }; 
    54  
    55 namespace boost { 
    56  
     38}; 
     39 
     40template <class Edge, class Container, class Cmp> 
     41class edge_queue : public std::priority_queue<Edge, Container, Cmp> 
     42{ 
     43protected: 
     44  using std::priority_queue< Edge, Container, Cmp >::c; 
     45  using std::priority_queue< Edge, Container, Cmp >::comp; 
     46     
     47public: 
     48  void sort() 
     49  { 
     50    sort_heap(c.begin(), c.end(), comp); 
     51  }    
     52}; 
     53 
     54namespace boost  
     55{ 
    5756   
    5857  template <class Heuristic, class Graph> 
    59   struct AStarHeuristicConcept { 
     58  struct AStarHeuristicConcept  
     59  { 
    6060    void constraints() 
    6161    { 
    …… 
    7070 
    7171  template <class Graph, class CostType> 
    72       class astar_heuristic : public std::unary_function< 
     72  class astar_heuristic : public std::unary_function< 
    7373    typename graph_traits<Graph>::vertex_descriptor, CostType> 
    7474  { 
    …… 
    110110 
    111111  template <class IncidenceGraph, class Buffer, class BFSVisitor, 
    112             class ColorMap, class EdgeColorMap, class HistoryMap> 
     112            class ColorMap, class EdgeColorMap/*, class HistoryMap*/> 
    113113  void shooting_star_edges_visit (const IncidenceGraph& g, 
    114114                            typename graph_traits<IncidenceGraph>::edge_descriptor s, 
    115115                            Buffer& Q, BFSVisitor vis, ColorMap color, EdgeColorMap edge_color,  
    116                             HistoryMap history, int e_max_id) 
     116                            int e_max_id) 
    117117  { 
    118118    function_requires< IncidenceGraphConcept<IncidenceGraph> >(); 
    …… 
    121121    typedef typename GTraits::edge_descriptor Edge; 
    122122    function_requires< ShootingStarVisitorConcept<BFSVisitor, IncidenceGraph> >(); 
    123     function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >(); 
    124123    function_requires< ReadWritePropertyMapConcept<EdgeColorMap, Edge> >(); 
    125124     
    …… 
    131130 
    132131    typename GTraits::out_edge_iterator ei, ei_end; 
    133                                                                      
    134     put(edge_color, s, EdgeColor::gray());         vis.discover_edge(s, g); 
     132 
     133    put(edge_color, s, EdgeColor::gray()); 
     134    vis.discover_edge(s, g); 
     135     
    135136    Q.push(s); 
    136137     
    137     while (! Q.empty()) { 
    138       Edge e = Q.top();  Q.pop();            vis.examine_edge(e, g); 
    139        
    140       for (tie(ei, ei_end) = out_edges(target(e, g), g); ei != ei_end; ++ei) { 
    141        
    142         EdgeColorValue e_color = get(edge_color, *ei); 
    143  
    144         if (e_color == EdgeColor::white()) {         vis.tree_edge(*ei, e, g, e_max_id); 
    145           put(edge_color, *ei, EdgeColor::gray());   vis.discover_edge(*ei, g); 
     138    while (! Q.empty())  
     139    { 
     140      Edge e = Q.top();  Q.pop();             
     141       
     142      vis.examine_edge(e, g); 
     143       
     144      for (tie(ei, ei_end) = out_edges(target(e, g), g); ei != ei_end; ++ei)  
     145      { 
     146        EdgeColorValue e_color = get(edge_color, *ei); 
     147 
     148        if (e_color == EdgeColor::white())  
     149        {          
     150          vis.tree_edge(*ei, e, g, e_max_id); 
     151          put(edge_color, *ei, EdgeColor::gray());    
     152          vis.discover_edge(*ei, g); 
    146153          Q.push(*ei); 
    147            
    148         } else {                                     vis.non_tree_edge(*ei, g); 
    149           if (e_color == EdgeColor::gray()){         vis.gray_target(*ei, e, g, e_max_id); 
     154        }  
     155        else  
     156        {                                      
     157          vis.non_tree_edge(*ei, g); 
     158          if (e_color == EdgeColor::gray()) 
     159          {          
     160            vis.gray_target(*ei, e, g, e_max_id); 
    150161          } 
    151           else{                                      vis.black_target(*ei, e, g, e_max_id); 
     162          else 
     163          {                                       
     164            vis.black_target(*ei, e, g, e_max_id); 
    152165          } 
    153166        } 
    …… 
    155168      } // end for 
    156169 
    157       put(edge_color, e, EdgeColor::black());        vis.finish_edge(e, g); 
     170      put(edge_color, e, EdgeColor::black());         
     171      vis.finish_edge(e, g); 
    158172       
    159173    } // end while 
    160      
    161174  } 
    162175                                                                                                                                                                                               
    163176   
    164177  template <class Visitors = null_visitor> 
    165   class shooting_star_visitor : public bfs_visitor<Visitors> { 
    166   public: 
    167     shooting_star_visitor() {} 
    168     shooting_star_visitor(Visitors vis) 
    169       : bfs_visitor<Visitors>(vis) {} 
    170    
    171     template <class Edge, class Graph> 
    172     void edge_relaxed(Edge e, Graph& g) { 
    173       invoke_visitors(this->m_vis, e, g, on_edge_relaxed()); 
    174     } 
    175     template <class Edge, class Graph> 
    176     void edge_not_relaxed(Edge e, Graph& g) { 
    177       invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());       
    178     } 
    179     template <class Edge, class Graph> 
    180     void initialize_edge(Edge e, Graph& g) { 
    181       invoke_visitors(this->m_vis, e, g, on_initialize_edge());       
    182     } 
    183      
    184   private: 
    185     template <class Edge, class Graph> 
    186     void tree_edge(Edge e, Edge pe, Graph& g) {} 
    187     template <class Edge, class Graph> 
    188     void non_tree_edge(Edge e, Graph& g) {} 
     178  class shooting_star_visitor : public bfs_visitor<Visitors>  
     179  { 
     180    public: 
     181      shooting_star_visitor() {} 
     182      shooting_star_visitor(Visitors vis) 
     183        : bfs_visitor<Visitors>(vis) {} 
     184   
     185      template <class Edge, class Graph> 
     186      void edge_relaxed(Edge e, Graph& g)  
     187      { 
     188        invoke_visitors(this->m_vis, e, g, on_edge_relaxed()); 
     189      } 
     190      template <class Edge, class Graph> 
     191      void edge_not_relaxed(Edge e, Graph& g)  
     192      { 
     193        invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());       
     194      } 
     195      template <class Edge, class Graph> 
     196      void initialize_edge(Edge e, Graph& g)  
     197      { 
     198        invoke_visitors(this->m_vis, e, g, on_initialize_edge());       
     199      } 
     200     
     201    private: 
     202      template <class Edge, class Graph> 
     203      void tree_edge(Edge e, Edge pe, Graph& g) {} 
     204      template <class Edge, class Graph> 
     205      void non_tree_edge(Edge e, Graph& g) {} 
    189206  }; 
     207 
    190208  template <class Visitors> 
    191209  shooting_star_visitor<Visitors> 
    192   make_shooting_star_visitor(Visitors vis) { 
     210  make_shooting_star_visitor(Visitors vis)  
     211  { 
    193212    return shooting_star_visitor<Visitors>(vis); 
    194213  } 
     214   
    195215  typedef shooting_star_visitor<> default_shooting_star_visitor; 
    196216   
    …… 
    200220    template <class AStarHeuristic, class UniformCostVisitor, 
    201221              class UpdatableQueue, class PredecessorMap, 
    202               class CostMap, class DistanceMap, class WeightMap, 
     222              class CostMap,  
     223              class DistanceMap, class WeightMap, 
    203224              class EdgeMap, 
    204               class ColorMap, class EdgeColorMap, class HistoryMap,  
     225              class ColorMap, class EdgeColorMap, 
    205226              class BinaryFunction, 
    206227              class BinaryPredicate> 
    …… 
    220241                        UpdatableQueue& Q, PredecessorMap& p, 
    221242                        CostMap c, DistanceMap d, WeightMap w, EdgeMap em, 
    222                         ColorMap col, EdgeColorMap ecol, HistoryMap his,  
     243                        ColorMap col, EdgeColorMap ecol, //HistoryMap his,  
    223244                        BinaryFunction combine, 
    224245                        BinaryPredicate compare, C zero) 
    225246        : m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c), 
    226247          m_distance(d), m_weight(w), m_edge(em), m_color(col),  
    227           m_ecolor(ecol), m_history(his), 
     248          m_ecolor(ecol), //m_history(his), 
    228249          m_combine(combine), m_compare(compare), m_zero(zero) {} 
    229        
     250 
     251      shooting_star_bfs_visitor(const shooting_star_bfs_visitor &v) 
     252        : m_h(v.m_h), m_vis(v.m_vis), m_Q(v.m_Q), m_predecessor(v.m_predecessor), m_cost(v.m_cost), 
     253          m_distance(v.m_distance), m_weight(v.m_weight), m_edge(v.m_edge), m_color(v.m_color),  
     254          m_ecolor(v.m_ecolor), //m_history(his), 
     255          m_combine(v.m_combine), m_compare(v.m_compare), m_zero(v.m_zero) {} 
     256           
     257      ~shooting_star_bfs_visitor() {} 
    230258       
    231259      template <class Vertex, class Graph> 
    232       void initialize_vertex(Vertex u, Graph& g) { 
     260      void initialize_vertex(Vertex u, Graph& g)  
     261      { 
    233262        m_vis.initialize_vertex(u, g); 
    234263      } 
    235264      template <class Edge, class Graph> 
    236       void initialize_edge(Edge e, Graph& g) { 
     265      void initialize_edge(Edge e, Graph& g)  
     266      { 
    237267        m_vis.initialize_edge(e, g); 
    238268      } 
    239269      template <class Vertex, class Graph> 
    240       void discover_vertex(Vertex u, Graph& g) { 
     270      void discover_vertex(Vertex u, Graph& g)  
     271      { 
    241272        m_vis.discover_vertex(u, g); 
    242273      } 
    243274      template <class Edge, class Graph> 
    244       void discover_edge(Edge e, Graph& g) { 
     275      void discover_edge(Edge e, Graph& g)  
     276      { 
    245277        m_vis.discover_vertex(e, g); 
    246278      } 
    247279      template <class Vertex, class Graph> 
    248       void examine_vertex(Vertex u, Graph& g) { 
     280      void examine_vertex(Vertex u, Graph& g)  
     281      { 
    249282        m_vis.examine_vertex(u, g); 
    250283      } 
    251284      template <class Vertex, class Graph> 
    252       void finish_vertex(Vertex u, Graph& g) { 
     285      void finish_vertex(Vertex u, Graph& g)  
     286      { 
    253287        m_vis.finish_vertex(u, g); 
    254288      } 
    255289      template <class Edge, class Graph> 
    256       void examine_edge(Edge e, Graph& g) {  
     290      void examine_edge(Edge e, Graph& g)  
     291      {  
    257292        if (m_compare(get(m_weight, e), m_zero)) 
    258293          throw negative_edge(); 
    …… 
    263298       
    264299      template <class Edge, class Graph> 
    265       void finish_edge(Edge e, Graph& g) { 
     300      void finish_edge(Edge e, Graph& g)  
     301      { 
    266302        m_vis.finish_edge(e, g); 
    267303      } 
    …… 
    269305       
    270306      template <class Edge, class Graph> 
    271       void tree_edge(Edge e, Edge pe, Graph& g, int e_max_id) { 
    272  
     307      void tree_edge(Edge e, Edge pe, Graph& g, int e_max_id)  
     308      { 
    273309        m_decreased = relax(e, pe, g, m_weight, m_edge, m_predecessor, m_distance, 
    274                             m_cost, m_history, m_combine, m_compare, e_max_id); 
    275      
    276         if(m_decreased) { 
     310                            m_cost, m_combine, m_compare, e_max_id); 
     311     
     312        if(m_decreased)  
     313        { 
    277314          m_vis.edge_relaxed(e, g); 
    278315           
    …… 
    281318                        m_h(e))); 
    282319 
    283         } else 
     320        }  
     321        else 
    284322          m_vis.edge_not_relaxed(e, g); 
    285323      } 
    …… 
    287325       
    288326      template <class Edge, class Graph> 
    289       void gray_target(Edge e, Edge pe, Graph& g, int e_max_id) { 
    290          
     327      void gray_target(Edge e, Edge pe, Graph& g, int e_max_id)  
     328      { 
    291329        m_decreased = relax(e, pe, g, m_weight, m_edge, m_predecessor, m_distance, 
    292                             m_cost, m_history, m_combine, m_compare, e_max_id); 
    293  
    294         if(m_decreased) { 
     330                            m_cost, m_combine, m_compare, e_max_id); 
     331 
     332        if(m_decreased)  
     333        { 
    295334          put(m_cost, e, 
    296335              m_combine(get(m_distance, e), 
    …… 
    300339                   
    301340          m_vis.edge_relaxed(e, g); 
    302         } else 
     341        }  
     342        else 
    303343          m_vis.edge_not_relaxed(e, g); 
    304344      } 
    …… 
    306346             
    307347      template <class Edge, class Graph> 
    308       void black_target(Edge e, Edge pe, Graph& g, int e_max_id) { 
     348      void black_target(Edge e, Edge pe, Graph& g, int e_max_id)  
     349      { 
    309350 
    310351        m_decreased = relax(e, pe, g, m_weight, m_edge, m_predecessor, m_distance, 
    311                             m_cost, m_history, m_combine, m_compare, e_max_id); 
    312  
    313         if(m_decreased) { 
     352                            m_cost, m_combine, m_compare, e_max_id); 
     353 
     354        if(m_decreased)  
     355        { 
    314356          m_vis.edge_relaxed(e, g); 
    315           put(m_cost, e, 
    316               m_combine(get(m_distance, e), 
    317                         m_h(e))); 
     357          put(m_cost, e, m_combine(get(m_distance, e), m_h(e))); 
    318358           
    319359          m_Q.push(e); 
    320360          put(m_ecolor, e, EdgeColor::gray()); 
    321361          m_vis.black_target(e, g); 
    322         } else 
     362        }  
     363        else 
    323364          m_vis.edge_not_relaxed(e, g); 
    324365      }   
    …… 
    334375      ColorMap m_color; 
    335376      EdgeColorMap m_ecolor; 
    336       HistoryMap m_history; 
    337377      BinaryFunction m_combine; 
    338378      BinaryPredicate m_compare; 
    339379      bool m_decreased; 
    340       C m_zero; 
    341        
     380      C m_zero;       
    342381    }; 
    343382     
    …… 
    346385  template <typename VertexAndEdgeListGraph, typename AStarHeuristic, 
    347386            typename ShootingStarVisitor, typename PredecessorMap, 
    348             typename CostMap, typename DistanceMap, 
     387            typename CostMap,  
     388            typename DistanceMap, 
    349389            typename WeightMap,  
    350390            typename EdgeMap, 
    351391            typename ColorMap, typename EdgeColorMap, 
    352             typename HistoryMap, 
    353392            typename IndexMap, 
    354393            typename CompareFunction, typename CombineFunction, 
    …… 
    361400     PredecessorMap &predecessor, CostMap cost, 
    362401     DistanceMap distance, WeightMap weight, EdgeMap edge_map, 
    363      ColorMap color, EdgeColorMap edge_color, HistoryMap history, 
     402     ColorMap color, EdgeColorMap edge_color, 
    364403     IndexMap index_map, CompareFunction compare, CombineFunction combine, 
    365404     CostInf inf, CostZero zero, int e_max_id) 
    …… 
    377416    detail::shooting_star_bfs_visitor<AStarHeuristic, ShootingStarVisitor, 
    378417        MutableQueue, PredecessorMap, CostMap, DistanceMap, 
    379         WeightMap, EdgeMap, ColorMap, EdgeColorMap, HistoryMap, CombineFunction, CompareFunction> 
     418        WeightMap, EdgeMap, ColorMap, EdgeColorMap, /*HistoryMap,*/ CombineFunction, CompareFunction> 
    380419      bfs_vis(h, vis, Q, predecessor, cost, distance, weight, 
    381               edge_map, color, edge_color, history, combine, compare, zero); 
    382    
    383     shooting_star_edges_visit(g, s, Q, bfs_vis, color, edge_color, history, e_max_id); 
     420              edge_map, color, edge_color, combine, compare, zero); 
     421   
     422    shooting_star_edges_visit(g, s, Q, bfs_vis, color, edge_color, e_max_id); 
    384423  } 
    385424   
    …… 
    391430            typename IndexMap, 
    392431            typename ColorMap, typename EdgeColorMap, 
    393             typename HistoryMap, 
     432            //typename HistoryMap, 
    394433            typename CompareFunction, typename CombineFunction, 
    395434            typename CostInf, typename CostZero> 
    …… 
    402441     DistanceMap distance, WeightMap weight, 
    403442     EdgeMap edge_map, IndexMap index_map, ColorMap color, EdgeColorMap edge_color, 
    404      HistoryMap history, CompareFunction compare, CombineFunction combine, 
     443     CompareFunction compare, CombineFunction combine, 
    405444     CostInf inf, CostZero zero, int e_max_id) 
    406445  { 
    …… 
    415454    typename graph_traits<VertexAndEdgeListGraph>::edge_iterator ei, ei_end; 
    416455 
    417     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { 
     456    for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)  
     457    { 
    418458      vis.initialize_vertex(*ui, g); 
    419459    } 
    420460 
    421     for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { 
     461    for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)  
     462    { 
    422463      put(distance, *ei, inf); 
    423464      put(edge_color, *ei, EdgeColor::white()); 
    …… 
    432473    shooting_star_search_no_init 
    433474      (g, s, h, vis, predecessor, cost, distance, weight, edge_map, 
    434        color, edge_color, history, index_map, compare, combine, inf, zero, e_max_id); 
     475       color, edge_color, index_map, compare, combine, inf, zero, e_max_id); 
    435476     
    436477  } 
    437478   
    438   namespace detail { 
     479  namespace detail  
     480  { 
    439481    template <class VertexAndEdgeListGraph, class AStarHeuristic, 
    440482              class CostMap, class DistanceMap, class WeightMap, class EdgeMap, 
    …… 
    442484              class PredecessorMap, 
    443485              class ColorMap, class EdgeColorMap,  
    444               class HistoryMap, class Params> 
     486              class Params> 
    445487    inline void 
    446488    shooting_star_dispatch2 
    …… 
    450492       WeightMap weight, EdgeMap edge_map, IndexMap index_map,  
    451493       PredecessorMap& predecessor, ColorMap color, 
    452        EdgeColorMap edge_color, HistoryMap history, const Params& params, 
     494       EdgeColorMap edge_color, const Params& params, 
    453495       int e_max_id) 
    454496    { 
    …… 
    460502                      make_shooting_star_visitor(null_visitor())), 
    461503         predecessor, 
    462          cost, distance, weight, edge_map, index_map, color, edge_color, history, 
     504         cost, distance, weight, edge_map, index_map, color, edge_color, //history, 
    463505         choose_param(get_param(params, distance_compare_t()), 
    464506                      std::less<C>()), 
    …… 
    478520              class PredecessorMap, 
    479521              class ColorMap, class EdgeColorMap, 
    480               class HistoryMap, class Params> 
     522              class Params> 
    481523    inline void 
    482524    shooting_star_dispatch1 
    …… 
    485527       AStarHeuristic h, CostMap cost, DistanceMap distance, 
    486528       WeightMap weight, EdgeMap edge_map, IndexMap index_map, PredecessorMap& predecessor,  
    487        ColorMap color, EdgeColorMap edge_color, HistoryMap history, const Params& params, 
     529       ColorMap color, EdgeColorMap edge_color, const Params& params, 
    488530       int e_max_id) 
    489531    { 
    …… 
    496538 
    497539      std::vector<default_color_type> color_map(num_vertices(g)); 
    498       std::vector<default_color_type> edge_color_map(num_edges(g)); 
    499540      default_color_type c = white_color; 
    500541       
    …… 
    512553                      (color_map.begin(), index_map, c)), 
    513554         edge_color,  
    514          history, 
    515555         params, 
    516556         e_max_id); 
    …… 
    525565            typename DistanceMap, 
    526566            typename CostMap, 
    527             typename