Changeset 75

Timestamp:

12/13/07 18:07:01 (1 year ago)

Author:

anton

Message:

--

Files:

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

sandbox/orkney/algorithm.h

@@ -36 +36 @@
-struct found_goal {}; // exception for termination
-
-typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
-typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;    
-
-
-class Algorithm
-{
@@ -76 +72 @@
-                     int end, OGREnvelope *bbox, OGRFeature **result, int *resultCount)
-    {      
+      typedef adjacency_list < listS, vecS, directedS, Vertex, Edge > graph_t;
+
+      typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
+      typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;  
+
-      // FIXME: compute this value
-      const unsigned int num_nodes = ((IsDirected() && HasReverseCost() ? 2 : 1) * (*count)) + 100;

sandbox/orkney/astar.h

@@ -9 +9 @@
-#include <boost/graph/graph_traits.hpp>
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/dijkstra_shortest_paths.hpp>
-#include <boost/graph/astar_search.hpp>
+
+#include <math.h>    // for sqrt
-
-#include "dijkstra.h"
@@ -31 +32 @@
-};
-
-typedef adjacency_list < listS, vecS, directedS, no_property, Edge > graph_t;
-
-// visitor that terminates when we find the goal
@@ -72 +72 @@
-{
-  public:
-
-
+
+
+
-    virtual ~AStar(); 
-

sandbox/orkney/dijkstra.h

@@ -28 +28 @@
-};
-
-typedef adjacency_list < listS, vecS, directedS, no_property, Edge > graph_t;
-
-class Dijkstra : public Algorithm
-{
@@ -35 +33 @@
-             Dijkstra(){}
-             Dijkstra( char *nameIn, bool directedIn, bool weightedIn, bool reverseCostIn )
-
-
-
+
-    virtual ~Dijkstra(){}
-

sandbox/orkney/shootingstar.h

@@ -7 +7 @@
-
-#include <boost/config.hpp>
+
-#include <boost/graph/graph_traits.hpp>
-#include <boost/graph/adjacency_list.hpp>
+#include <boost/vector_property_map.hpp>
+#include <shooting_star_search.hpp>
+
+#include <math.h>    // for sqrt and fabs
-
-#include "algorithm.h"
+
-
-#define MAX_RULE_LENGTH 5
@@ -39 +45 @@
-};
-
+// visitor that terminates when we find the goal
+template <class Edge>
+class shooting_star_goal_visitor : public boost::default_shooting_star_visitor
+{
+public:
+  shooting_star_goal_visitor(Edge goal, int max_id) : m_goal(goal){}
+  shooting_star_goal_visitor(const shooting_star_goal_visitor &gv) : m_goal(gv.m_goal){}
+  ~shooting_star_goal_visitor(){}
+
+  template <class Graph>
+  void examine_edge(Edge e, Graph& g) 
+  {
+    if( g[e].id == g[m_goal].id)
+    {
+      throw found_goal();
+    }
+  }
+  template <class Graph>
+  void finish_edge(Edge e, Graph& g) {}
+private:
+  Edge m_goal;
+};
+
+template <class Graph, class CostType>
+class distance_heuristic
+{
+public:
+  typedef typename graph_traits<Graph>::edge_descriptor Edge;
+  distance_heuristic(Graph& g, Edge goal):m_g(g), m_goal(goal){}
+  CostType operator()(Edge e)
+  {
+    CostType dx = m_g[source(m_goal, m_g)].x - m_g[source(e, m_g)].x;
+    CostType dxt = m_g[target(m_goal, m_g)].x - m_g[target(e, m_g)].x;
+    CostType dy = m_g[source(m_goal, m_g)].y - m_g[source(e, m_g)].y;
+    CostType dyt = m_g[target(m_goal, m_g)].y - m_g[target(e, m_g)].y;
+    //You can choose any heuristical function from below
+    //return ::max(dx, dy);
+    //return ::sqrt(dx * dx + dy * dy)/2;
+    //return 0;
+    return (min(::fabs(dx),::fabs(dxt))+min(::fabs(dy),::fabs(dyt)))/2;
+  } 
+private:
+  Graph& m_g;
+  Edge m_goal;
+};
+
-class ShootingStar : public Algorithm
-{    
-  public:
-
-
+
+
+
-    virtual ~ShootingStar();
-
+  private:
+    std::map< int, vector< std::pair<float, vector<int> > >, std::less<int> > adjacent_edges;
+    std::map< int, int, std::less<int> > vertices;  
+    vector<int> rule;
+    int offset;
+    int rule_num;
+
+    bool addEdge(edge_descriptor *e, OGRFeature *edge, graph_t &graph)
+    {
+      bool inserted;
+    
+      if (cost < 0) // edges are not inserted in the graph if cost is negative
+        return;
+
+      tie(*e, inserted) = add_edge(edge->GetFieldAsInteger(SOURCE_FEATURE), 
+                                   edge->GetFieldAsInteger(TARGET_FEATURE), graph);
+
+      graph[e].cost = edge->GetFieldAsDouble(COST_FEATURE);
+      graph[e].id = edge->GetFieldAsInteger(ID_FEATURE);
+
+      graph[e].source = edge->GetFieldAsInteger(SOURCE_FEATURE);
+      graph[e].target = edge->GetFieldAsInteger(TARGET_FEATURE);
+
+      graph[e].adjacent_edges = adjacent_edges;
+
+      graph[e].rank = 0;
+      graph[e].distance = 0;
+
+      OGRLineString *geom = static_cast<OGRLineString*>edge->GetGeometryRef();
+
+      vertex_descriptor s = vertex(edge->GetFieldAsInteger(SOURCE_FEATURE), graph);
+      vertex_descriptor t = vertex(edge->GetFieldAsInteger(TARGET_FEATURE), graph);
+
+      graph[s].id = edge->GetFieldAsInteger(SOURCE_FEATURE);
+      graph[t].id = edge->GetFieldAsInteger(TARGET_FEATURE);
+
+      graph[s].x=geom->getX(0);
+      graph[s].y=geom->getY(0);
+      graph[t].x=geom->getX(geom->getNumPoints()-1);
+      graph[t].y=geom->getY(geom->getNumPoints()-1);
+    }
+
+    virtual void fillFeatures(OGRFeature **edges, edge_descriptor *e, graph_t &graph, int j)
+    {
+      
+    //Vertex ids renumbering moved here
+    src = edges_array[j].source;
+    trg = edges_array[j].target;
+    
+    if(vertices[src]==0)
+    {
+      vertices[src]=j+offset;
+    }
+    edges_array[j].source=vertices[src];
+    
+    if(vertices[trg]==0)
+    {
+      offset++;      
+      vertices[trg]=j+offset;
+    }
+    edges_array[j].target=vertices[trg];
+    
+    for(z=0; z<MAX_RULE_LENGTH;++z)
+    {
+      if(edges_array[j].rule[z] > 0)
+      {
+        rule.push_back(edges_array[j].rule[z]);
+      }
+    }
+
+    if(edges_array[j].to_cost > 0)
+    {
+      adjacent_edges[edges_array[j].id].push_back(std::pair<float8, vector<int> > (edges_array[j].to_cost, rule) );
+      rule.clear();
+    }
+
+    if((j < count-1 && edges_array[j].id != edges_array[j+1].id)||(j==count-1))
+    {
+
+      bool inserted = addEdge(e, edges[j], graph);
+
+      graph[*e].cost = edges[j]->GetFieldAsDouble(COST_FEATURE);//set cost
+      graph[*e].id = j;//set id
+
+
+      if (!IsDirected() || (IsDirected() && HasReverseCost()))
+      {
+
+        if(adjacent_edges[edges_array[j].id].size() > 0)
+        {
+          adjacent_edges[edges_array[j].id+e_max_id].assign( adjacent_edges[edges_array[j].id].begin(), adjacent_edges[edges_array[j].id].end() );
+          adjacent_edges.erase(edges_array[j].id);
+        }
+
+        edge_descriptor *er; 
+        //adding an edge for opposite direction
+        bool inserted = addEdge(er, edges[j], graph);
+
+        graph[*er].id = j;//set id
+    
+        if (HasReverseCost())
+        {
+          graph[*er].cost = edges[j]->GetFieldAsDouble(RC_FEATURE);//set reverse cost
+        }
+        else 
+        {
+          graph[*er].cost = edges[j]->GetFieldAsDouble(COST_FEATURE);//set cost
+        }
+
+      } 
+
+      adjacent_edges.clear();
+      rule_num = 0;
+    }
+    else
+    {
+      rule_num++;
+    }   
+  }
+
-};  
-