Changeset 79

Timestamp:

12/17/07 16:41:08 (1 year ago)

Author:

anton

Message:

--

Files:

• sandbox/orkney/dijkstra.h (modified) (3 diffs)
• sandbox/orkney/shootingstar.h (modified) (3 diffs)

sandbox/orkney/dijkstra.h

@@ -78 +78 @@
-        edge_descriptor *er; 
-        //adding an edge for opposite direction
-
+    
-
-        graph[*er].id = j;//set id
-    
-        if (HasReverseCost())
-
+    
-          graph[*er].cost = edges[j]->GetFieldAsDouble(RC_FEATURE);//set reverse cost
-
-
-
-
-
+    
+    
+    
+    
+    
-      }    
-    }
@@ -131 +131 @@
-      while (target != source) 
-      {
-
-
-
-
-
+    
+    
+  
+    
+    
-
-
-
-
-
-
+    
+    
+    
+  
+    
-      }
-
@@ -151 +151 @@
-      for(int i = path_vect.size() - 1, int j = 0; i >= 0; i--, j++)
-      {
-
-
-
-
+    
+    
+    
+    
-        
-
-
-
-
+    
+    
+  
+    
-
-
-
+    
+    
-
-
-
-
-
-
-
-
+    
+    
+    
+    
+    
+    
+    
-                                                                
-
-
-
-
-
-
+    
+    
+    
+    
+    
+    
-      }
-

sandbox/orkney/shootingstar.h

@@ -214 +214 @@
-                              adjacent_edges[edges[j]->GetFieldAsInteger(ID_FEATURE)].begin(), 
-                              adjacent_edges[edges[j]->GetFieldAsInteger(ID_FEATURE)].end() );
-
+    
-          }
-
-          edge_descriptor *er; 
-          //adding an edge for opposite direction
-
+    
-
-          graph[*er].id = j;//set id
-    
-          if (HasReverseCost())
-
+    
-            graph[*er].cost = edges[j]->GetFieldAsDouble(RC_FEATURE);//set reverse cost
-
-
-
-
-
+    
+    
+    
+    
+    
-
-        }  
@@ -236 +236 @@
-        adjacent_edges.clear();
-        rule_num = 0;
+        
-      }
-      else
@@ -245 +246 @@
-};  
-
+    int getRoute(int start, int end, OGRFeature **result, int *resultCount, graph_t &graph)
+    {      
+      edge_descriptor source_edge;
+      edge_descriptor target_edge;
+  
+      bool source_found = false, target_found = false;      
+
+      graph_traits<graph_t>::edge_iterator ei, ei_end;
+
+      for(tie(ei, ei_end) = edges(graph); ei != ei_end; ++ei) 
+      {
+        if(graph[*ei].id == start)
+        {
+          source_edge = *ei;
+          source_found = true;
+          break;
+        }
+      }
+
+      if (!source_found) 
+      {
+        return NO_SOURCE_FOUND;
+      }
+
+
+      for(tie(ei, ei_end) = edges(graph); ei != ei_end; ++ei) 
+      {
+        if(graph[*ei].id == end)
+        {
+          target_edge = *ei;
+          target_found = true;
+          break;
+        }
+      }
+
+      if (!target_found)
+      {
+        return NO_TARGET_FOUND;
+      }
+
+      property_map<graph_t, int Edge::*>::type edge_index = get(&Edge::id, graph);
+
+      std::map< int, edge_descriptor, std::less<int> > predecessors;
+  
+      property_map<graph_t, float Edge::*>::type rank = get(&Edge::rank, graph);
+      property_map<graph_t, float Edge::*>::type distance = get(&Edge::distance, graph);
+  
+      try 
+      {
+        shooting_star_search
+          (graph, source_edge,
+           distance_heuristic<graph_t, float>(graph, target_edge),
+           weight_map(get(&Edge::cost, graph)).
+           weight_map2(get(&Edge::adjacent_edges, graph)).
+           edge_color_map(get(&Edge::color, graph)).
+           visitor(shooting_star_goal_visitor<edge_descriptor>(target_edge, e_max_id)),
+           edge_index,
+           distance, rank,
+           predecessors, e_max_id
+           );
+      } 
+      catch(found_goal &fg) 
+      {
+        return makeResult(*target, *source, *predecessors, result, resultCount, graph);
+      }  
+    }
+    
+    virtual int  makeResult(edge_descriptor *target_edge, edge_descriptor *source_edge, 
+                          std::map< int, edge_descriptor, std::less<int> > *predecessors, 
+                          OGRFeature **result, int *resultCount, graph_t &graph)
+    {
+    vector<edge_descriptor> path_vect;
+    int max = MAX_NODES;
+
+    path_vect.push_back(target_edge);
+    
+    while (target_edge != source_edge) 
+      {
+        
+        if ((target_edge == predecessors[graph[target_edge].id]) && (predecessors[graph[target_edge].id] != source_edge))
+            {
+          return NO_PATH_FOUND;    
+            }
+  
+            target_edge = predecessors[graph[target_edge].id];
+
+        path_vect.push_back(target_edge);
+
+        if (!max--) 
+            {
+           return OVERFLOW;
+            }
+      }
+
+      //*result = (OGRFeature *) malloc(sizeof(OGRFeature) * (path_vect.size() + 1));
+      //Let's try to do it in C++ style
+      *result = new OGRFeature * [path_vect.size() + 1];
+      *path_count = path_vect.size();
+
+      for(int i = path_vect.size() - 1, j = 0; i >= 0; i--, j++)
+      {
+        graph_traits < graph_t >::edge_descriptor e;
+
+        e = path_vect.at(i);
+
+        if(graph[e].id > e_max_id)
+        {
+          graph[e].id -= e_max_id;      
+        }
+      
+        (*result)[j] = graph[e].id;
+      }
+
+      return EXIT_SUCCESS;
+    }
+    
+}; 
+
-#endif