pgRouting

Changeset 81

Show
Ignore:
Timestamp:
12/19/07 13:53:41 (1 year ago)
Author:
anton
Message:

--

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • sandbox/orkney/algorithm.h

    r78 r81  
    4848#define NO_TARGET_FOUND 2 
    4949#define NO_PATH_FOUND   3 
    50 #define OVERFLOW        4 
     50#define RESULT_OVERFLOW 4 
    5151 
    5252 
    …… 
    5454using namespace boost; 
    5555 
     56struct Edge 
     57{ 
     58  int id; 
     59  int source; 
     60  int target; 
     61  double cost; 
     62  double distance; 
     63  double rank; 
     64  std::map< int, vector< std::pair<float, std::vector<int> > >, std::less<int> > adjacent_edges; 
     65  default_color_type color; 
     66}; 
     67         
     68struct Vertex 
     69{ 
     70  int id; 
     71  double x; 
     72  double y; 
     73}; 
     74 
    5675struct found_goal {}; // exception for termination 
    5776 
     77typedef adjacency_list < listS, vecS, directedS, Vertex, Edge > graph_t; 
     78 
     79typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; 
     80typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;  
     81       
    5882class Algorithm 
    5983{ 
    …… 
    6589    char *name; 
    6690 
     91    int   e_max_id; 
    6792 
    6893  public: 
    …… 
    82107                    
    83108    virtual bool addEdge(edge_descriptor *e, OGRFeature *edge, graph_t &graph) = 0; 
    84     virtual void fillFeature(OGRFeature **edges, edge_descriptor *e, graph_t &graph, int j) = 0; 
    85     virtual int  getRoute(int start, int end, OGRFeature **result, int *resultCount, graph_t &graph) = 0; 
    86     virtual int  makeResult(vertex_descriptor *target, vertex_descriptor *source,  
    87                           std::vector<vertex_descriptor> *predecessors,  
    88                           OGRFeature **result, int *resultCount, graph_t &graph) = 0; 
     109    virtual void fillFeature(OGRFeature **edges, unsigned int count, edge_descriptor *e, graph_t &graph, int j) = 0; 
     110    virtual int  getRoute(int start, int end, OGRFeature **edges, OGRFeature **result, int *resultCount, graph_t &graph) = 0; 
     111    virtual int  makeResult(vertex_descriptor target, vertex_descriptor source,  
     112                            OGRFeature **edges, 
     113                            std::vector<vertex_descriptor> &predecessors,  
     114                            OGRFeature **result, int *resultCount, graph_t &graph) = 0; 
    89115 
    90116    //Template method for shortest path calculation 
    91     int shortestPath(OGRFeature **edges, int count, int start,  
     117    int shortestPath(OGRFeature **edges, unsigned int count, int start,  
    92118                     int end, OGREnvelope *bbox, OGRFeature **result, int *resultCount) 
    93119    {       
    94       typedef adjacency_list < listS, vecS, directedS, Vertex, Edge > graph_t; 
    95  
    96       typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; 
    97       typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;   
    98120 
    99121      // FIXME: compute this value 
    100       const unsigned int num_nodes = ((IsDirected() && HasReverseCost() ? 2 : 1) * (*count)) + 100; 
     122      const unsigned int num_nodes = ((IsDirected() && HasReverseCost() ? 2 : 1) * count) + 100; 
    101123   
    102124      graph_t graph(num_nodes); 
     125       
     126      for (unsigned int z = 0; z < count; ++z) 
     127      { 
     128        if(edges[z]->GetFieldAsInteger(ID_FEATURE) > e_max_id) 
     129          e_max_id=edges[z]->GetFieldAsInteger(ID_FEATURE); 
     130      } 
    103131       
    104132      for (std::size_t j = 0; j < count; ++j) 
    …… 
    106134        edge_descriptor *e;  
    107135         
    108         fillFeatures(edges, e, graph, j);      
     136            fillFeature(edges, count, e, graph, j);    
    109137      } 
    110138       
    111       return getRoute(start, end, result, resultCount, graph);       
     139      return getRoute(start, end, edges, result, resultCount, graph);       
    112140    } 
    113141     

  • sandbox/orkney/astar.h

    r78 r81  
    3939using namespace std; 
    4040using namespace boost; 
    41  
    42 struct Edge 
    43 { 
    44   int id; 
    45   double cost; 
    46 }; 
    47          
    48 struct Vertex 
    49 { 
    50   int id; 
    51   double x; 
    52   double y; 
    53 }; 
    54  
    5541 
    5642// visitor that terminates when we find the goal 
    …… 
    9581             AStar(){} 
    9682             AStar( char *nameIn, bool directedIn, bool weightedIn, bool reverseCostIn ) 
    97              : Algorithm( nameIn, directedIn, weightedIn, reverseCostIn ) 
     83             : Dijkstra( nameIn, directedIn, weightedIn, reverseCostIn ){} 
    9884    virtual ~AStar();  
    9985 
    …… 
    10288      bool inserted; 
    10389     
    104       if (cost < 0) // edges are not inserted in the graph if cost is negative 
    105         return; 
     90      if (edge->GetFieldAsDouble(COST_FEATURE) < 0) // edges are not inserted in the graph if cost is negative 
     91        return false; 
    10692 
    10793      tie(*e, inserted) = add_edge(edge->GetFieldAsInteger(SOURCE_FEATURE),  
    10894                                   edge->GetFieldAsInteger(TARGET_FEATURE), graph); 
    10995 
    110       graph[e].cost = edge->GetFieldAsDouble(COST_FEATURE); 
    111       graph[e].id = edge->GetFieldAsInteger(ID_FEATURE); 
     96      graph[*e].cost = edge->GetFieldAsDouble(COST_FEATURE); 
     97      graph[*e].id = edge->GetFieldAsInteger(ID_FEATURE); 
    11298 
    113       OGRLineString *geom = static_cast<OGRLineString*>edge->GetGeometryRef(); 
     99      OGRLineString *geom = static_cast<OGRLineString*>(edge->GetGeometryRef()); 
    114100 
    115101      vertex_descriptor s = vertex(edge->GetFieldAsInteger(SOURCE_FEATURE), graph); 
    …… 
    120106      graph[t].x=geom->getX(geom->getNumPoints()-1); 
    121107      graph[t].y=geom->getY(geom->getNumPoints()-1); 
     108       
     109      return inserted; 
    122110    } 
    123111 
    124112 
    125     int getRoute(int start, int end, OGRFeature **result, int *resultCount, graph_t &graph) 
     113    int getRoute(int start, int end, OGRFeature **edges, OGRFeature **result, int *resultCount, graph_t &graph) 
    126114    { 
    127115      std::vector<vertex_descriptor> predecessors(num_vertices(graph)); 
    …… 
    129117      vertex_descriptor source = vertex(start, graph); 
    130118 
    131       if (source_vertex < 0)  
     119      if (source < 0)  
    132120      { 
    133121        return NO_SOURCE_FOUND; 
    …… 
    135123 
    136124      vertex_descriptor target = vertex(end, graph); 
    137       if (target_vertex < 0) 
     125      if (target < 0) 
    138126      { 
    139127        return NO_TARGET_FOUND; 
    140128      } 
    141129 
    142       std::vector<float8> distances(num_vertices(graph)); 
     130      std::vector<double> distances(num_vertices(graph)); 
    143131 
    144132      try  
    …… 
    155143      catch(found_goal fg)  
    156144      { 
    157         return makeResult(*target, *source, *predecessors, result, resultCount, graph); 
     145        return makeResult(target, source, edges, predecessors, result, resultCount, graph); 
    158146      }   
    159147    } 

  • sandbox/orkney/dijkstra.h

    r79 r81  
    3838using namespace boost; 
    3939 
    40 struct Edge 
    41 { 
    42     int id; 
    43     double cost; 
    44 }; 
    45  
    46 struct Vertex 
    47 { 
    48   int id; 
    49 }; 
    50  
    5140class Dijkstra : public Algorithm 
    5241{ 
    …… 
    6655    } 
    6756     
    68     virtual void fillFeatures(OGRFeature **edges, edge_descriptor *e, graph_t &graph, int j) 
     57    virtual void fillFeature(OGRFeature **edges, unsigned int count, edge_descriptor *e, graph_t &graph, int j) 
    6958    { 
    7059      bool inserted = addEdge(e, edges[j], graph); 
    …… 
    9382    } 
    9483 
    95     virtual int getRoute(int start, int end, OGRFeature **result, int *resultCount, graph_t &graph) 
     84    virtual int getRoute(int start, int end, OGRFeature **edges, OGRFeature **result, int *resultCount, graph_t &graph) 
    9685    { 
    9786      std::vector<vertex_descriptor> predecessors(num_vertices(graph)); 
    …… 
    9988      vertex_descriptor source = vertex(start, graph); 
    10089 
    101       if (source_vertex < 0)  
     90      if (source < 0)  
    10291      { 
    10392        return NO_SOURCE_FOUND; 
    …… 
    10594 
    10695      vertex_descriptor target = vertex(end, graph); 
    107       if (target_vertex < 0) 
     96      if (target < 0) 
    10897      { 
    10998        return NO_TARGET_FOUND; 
    11099      } 
    111100 
    112       std::vector<float8> distances(num_vertices(graph)); 
     101      std::vector<double> distances(num_vertices(graph)); 
    113102 
    114103      dijkstra_shortest_paths(graph, source, 
    115104                              predecessor_map(&predecessors[0]). 
    116                               weight_map(get(&Vertex::cost, graph)) 
     105                              weight_map(get(&Edge::cost, graph)) 
    117106                              .distance_map(&distances[0])); 
    118107 
    119       return makeResult(*target, *source, *predecessors, result, resultCount, graph); 
     108      return makeResult(target, source, edges, predecessors, result, resultCount, graph); 
    120109 
    121110    }   
    122111 
    123     virtual int  makeResult(vertex_descriptor *target, vertex_descriptor *source,  
    124                           std::vector<vertex_descriptor> *predecessors,  
    125                           OGRFeature **result, int *resultCount, graph_t &graph) 
     112    virtual int makeResult(vertex_descriptor target, vertex_descriptor source, 
     113                           OGRFeature **edges, 
     114                           std::vector<vertex_descriptor> &predecessors,  
     115                           OGRFeature **result, int *resultCount, graph_t &graph) 
    126116    { 
    127117      vector<int> path_vect; 
    128118      int max = MAX_NODES; 
    129       path_vect.push_back(end); 
     119      path_vect.push_back(target); 
    130120 
    131121      while (target != source)  
    …… 
    140130            if (!max--)  
    141131            { 
    142               return OVERFLOW; 
     132              return RESULT_OVERFLOW; 
    143133            } 
    144134      } 
    …… 
    146136      //*result = (OGRFeature *) malloc(sizeof(OGRFeature) * (path_vect.size() + 1)); 
    147137      //Let's try to do it in C++ style 
    148       *result = new OGRFeature * [path_vect.size() + 1]; 
     138      result = new OGRFeature* [path_vect.size() + 1]; 
    149139      *resultCount = path_vect.size(); 
     140      int i, j; 
    150141 
    151       for(int i = path_vect.size() - 1, int j = 0; i >= 0; i--, j++) 
     142      for(i = path_vect.size() - 1, j = 0; i >= 0; i--, j++) 
    152143      { 
    153144            graph_traits < graph_t >::vertex_descriptor v_src; 
    …… 
    169160              graph_traits < graph_t >::vertex_descriptor v, targ; 
    170161              e = *out_i; 
    171               v = source(e, graph); 
    172               targ = target(e, graph); 
     162              v = boost::source(e, graph); 
     163              targ = boost::target(e, graph); 
    173164                                                                 
    174165              if (targ == v_targ) 
    175166              { 
    176                 (*result)[j] = (*edges)[graph[*out_i].id]; 
     167                result[j] = edges[graph[*out_i].id]; 
    177168                break; 
    178169              } 

  • sandbox/orkney/shootingstar.h

    r80 r81  
    3232#include <boost/graph/adjacency_list.hpp> 
    3333#include <boost/vector_property_map.hpp> 
    34 #include <shooting_star_search.hpp> 
    3534 
    3635#include <math.h>    // for sqrt and fabs 
    3736 
    3837#include "algorithm.h" 
     38#include "shooting_star_search.hpp" 
    3939 
    4040 
    …… 
    4646using namespace std; 
    4747using namespace boost; 
    48  
    49 struct Edge 
    50 { 
    51   int id; 
    52   int source; 
    53   int target; 
    54   double cost; 
    55   double distance; 
    56   double rank; 
    57   std::map< int, vector< std::pair<float, std::vector<int> > >, std::less<int> > adjacent_edges; 
    58   default_color_type color; 
    59 }; 
    60          
    61 struct Vertex 
    62 { 
    63   int id; 
    64   double x; 
    65   double y; 
    66 }; 
    6748 
    6849// visitor that terminates when we find the goal 
    …… 
    9071 
    9172template <class Graph, class CostType> 
    92 class distance_heuristic 
     73class edge_distance_heuristic 
    9374{ 
    9475public: 
    9576  typedef typename graph_traits<Graph>::edge_descriptor Edge; 
    96   distance_heuristic(Graph& g, Edge goal):m_g(g), m_goal(goal){} 
     77  edge_distance_heuristic(Graph& g, Edge goal):m_g(g), m_goal(goal){} 
    9778  CostType operator()(Edge e) 
    9879  { 
    …… 
    11798             ShootingStar():offset(1), rule_num(0){} 
    11899             ShootingStar( char *nameIn, bool directedIn, bool weightedIn, bool reverseCostIn ) 
    119              : Algorithm( nameIn, directedIn, weightedIn, reverseCostIn ):offset(1), rule_num(0){} 
     100             : Algorithm( nameIn, directedIn, weightedIn, reverseCostIn ), offset(1), rule_num(0){} 
    120101    virtual ~ShootingStar(); 
    121102 
    …… 
    131112      bool inserted; 
    132113     
    133       if (cost < 0) // edges are not inserted in the graph if cost is negative 
    134         return; 
     114      if (edge->GetFieldAsDouble(COST_FEATURE) < 0) // edges are inserted as unpassable if cost is negative 
     115        edge->SetField(COST_FEATURE, MAX_COST); 
    135116 
    136117      tie(*e, inserted) = add_edge(edge->GetFieldAsInteger(SOURCE_FEATURE),  
    137118                                   edge->GetFieldAsInteger(TARGET_FEATURE), graph); 
    138119 
    139       graph[e].cost = edge->GetFieldAsDouble(COST_FEATURE); 
    140       graph[e].id = edge->GetFieldAsInteger(ID_FEATURE); 
    141  
    142       graph[e].source = edge->GetFieldAsInteger(SOURCE_FEATURE); 
    143       graph[e].target = edge->GetFieldAsInteger(TARGET_FEATURE); 
    144  
    145       graph[e].adjacent_edges = adjacent_edges; 
    146  
    147       graph[e].rank = 0; 
    148       graph[e].distance = 0; 
    149  
    150       OGRLineString *geom = static_cast<OGRLineString*>edge->GetGeometryRef(); 
     120      graph[*e].cost = edge->GetFieldAsDouble(COST_FEATURE); 
     121      graph[*e].id = edge->GetFieldAsInteger(ID_FEATURE); 
     122 
     123      graph[*e].source = edge->GetFieldAsInteger(SOURCE_FEATURE); 
     124      graph[*e].target = edge->GetFieldAsInteger(TARGET_FEATURE); 
     125 
     126      graph[*e].adjacent_edges = adjacent_edges; 
     127 
     128      graph[*e].rank = 0; 
     129      graph[*e].distance = 0; 
     130 
     131      OGRLineString *geom = static_cast<OGRLineString*>(edge->GetGeometryRef()); 
    151132 
    152133      vertex_descriptor s = vertex(edge->GetFieldAsInteger(SOURCE_FEATURE), graph); 
    …… 
    160141      graph[t].x=geom->getX(geom->getNumPoints()-1); 
    161142      graph[t].y=geom->getY(geom->getNumPoints()-1); 
    162     } 
    163  
    164     virtual void fillFeatures(OGRFeature **edges, edge_descriptor *e, graph_t &graph, int j) 
     143       
     144      return inserted; 
     145    } 
     146 
     147    virtual void fillFeatures(OGRFeature **edges, unsigned int count, edge_descriptor *e, graph_t &graph, int j) 
    165148    { 
     149      int src, trg; 
    166150       
    167151      //Vertex ids renumbering moved here 
    …… 
    181165      } 
    182166      edges[j]->SetField(TARGET_FEATURE, vertices[trg]); 
    183      
    184       for(z=0; z<edges[j]->GetFieldAsIntegerList(RULE_FEATURE).size();++z) 
    185       { 
    186         if(edges[j]->GetFieldAsIntegerList(RULE_FEATURE)[z] > 0) 
    187         { 
    188           rule.push_back(edges[j]->GetFieldAsIntegerList(RULE_FEATURE)[z]); 
     167       
     168      int *rule_cnt; 
     169      const int *rule_list; 
     170       
     171      rule_list = edges[j]->GetFieldAsIntegerList(RULE_FEATURE, rule_cnt); 
     172     
     173      for(int z=0; z< *rule_cnt;++z) 
     174      { 
     175        if(rule_list[z] > 0) 
     176        { 
     177          rule.push_back(rule_list[z]); 
    189178        } 
    190179      } 
    …… 
    193182      { 
    194183        adjacent_edges[edges[j]->GetFieldAsInteger(ID_FEATURE)].push_back( 
    195                                 std::pair<float8, vector<int> > (GetFieldAsDouble(TO_COST_FEATURE), rule) ); 
     184                                std::pair<double, vector<int> > (edges[j]->GetFieldAsDouble(TO_COST_FEATURE), rule) ); 
    196185        rule.clear(); 
    197186      } 
    …… 
    209198        { 
    210199 
    211           if(adjacent_edges[edges_array[j].id].size() > 0) 
     200          if(adjacent_edges[edges[j]->GetFieldAsInteger(ID_FEATURE)].size() > 0) 
    212201          { 
    213202            adjacent_edges[edges[j]->GetFieldAsInteger(ID_FEATURE)+e_max_id].assign(  
    …… 
    244233    } 
    245234 
    246     int getRoute(int start, int end, OGRFeature **result, int *resultCount, graph_t &graph) 
     235    int getRoute(int start, int end, OGRFeature **edges, OGRFeature **result, int *resultCount, graph_t &graph) 
    247236    {       
    248237      edge_descriptor source_edge; 
    …… 
    253242      graph_traits<graph_t>::edge_iterator ei, ei_end; 
    254243 
    255       for(tie(ei, ei_end) = edges(graph); ei != ei_end; ++ei)  
     244      for(tie(ei, ei_end) = boost::edges(graph); ei != ei_end; ++ei)  
    256245      { 
    257246        if(graph[*ei].id == start) 
    …… 
    269258 
    270259 
    271       for(tie(ei, ei_end) = edges(graph); ei != ei_end; ++ei)  
     260      for(tie(ei, ei_end) = boost::edges(graph); ei != ei_end; ++ei)  
    272261      { 
    273262        if(graph[*ei].id == end) 
    …… 
    288277      std::map< int, edge_descriptor, std::less<int> > predecessors; 
    289278   
    290       property_map<graph_t, float Edge::*>::type rank = get(&Edge::rank, graph); 
    291       property_map<graph_t, float Edge::*>::type distance = get(&Edge::distance, graph); 
     279      property_map<graph_t, double Edge::*>::type rank = get(&Edge::rank, graph); 
     280      property_map<graph_t, double Edge::*>::type distance = get(&Edge::distance, graph); 
    292281   
    293282      try  
    …… 
    295284        shooting_star_search 
    296285          (graph, source_edge, 
    297            distance_heuristic<graph_t, float>(graph, target_edge), 
     286           edge_distance_heuristic<graph_t, float>(graph, target_edge), 
    298287           weight_map(get(&Edge::cost, graph)). 
    299288           weight_map2(get(&Edge::adjacent_edges, graph)). 
    …… 
    307296      catch(found_goal &fg)  
    308297      { 
    309         return makeResult(*target, *source, *predecessors, result, resultCount, graph); 
     298        return makeResult(target_edge, source_edge, edges, predecessors, result, resultCount, graph); 
    310299      }   
    311300    } 
    312301     
    313     virtual int  makeResult(edge_descriptor *target_edge, edge_descriptor *source_edge,  
    314                           std::map< int, edge_descriptor, std::less<int> > *predecessors,  
    315                           OGRFeature **result, int *resultCount, graph_t &graph) 
     302    int  makeResult(edge_descriptor target_edge, edge_descriptor source_edge,  
     303                            OGRFeature **edges, 
     304                            std::map< int, edge_descriptor, std::less<int> > &predecessors,  
     305                            OGRFeature **result, int *resultCount, graph_t &graph) 
    316306    { 
    317307    vector<edge_descriptor> path_vect; 
    …… 
    334324        if (!max--)  
    335325            { 
    336            return OVERFLOW; 
     326           return RESULT_OVERFLOW; 
    337327            } 
    338328      } 
    …… 
    340330      //*result = (OGRFeature *) malloc(sizeof(OGRFeature) * (path_vect.size() + 1)); 
    341331      //Let's try to do it in C++ style 
    342       *result = new OGRFeature * [path_vect.size() + 1]; 
    343       *path_count = path_vect.size(); 
     332      result = new OGRFeature * [path_vect.size() + 1]; 
     333      *resultCount = path_vect.size(); 
    344334 
    345335      for(int i = path_vect.size() - 1, j = 0; i >= 0; i--, j++) 
    …… 
    354344        } 
    355345       
    356         (*result)[j] = graph[e].id; 
     346        result[j] = edges[graph[e].id]; 
    357347      } 
    358348