Changeset 73

Timestamp:

12/12/07 17:38:07 (1 year ago)

Author:

anton

Message:

Algorithm header files splitted

Files:

• sandbox/orkney/algorithm.h (modified) (4 diffs)
• sandbox/orkney/astar.h (added)
• sandbox/orkney/dijkstra.h (added)
• sandbox/orkney/shootingstar.h (added)

sandbox/orkney/algorithm.h

@@ -9 +9 @@
-#include <boost/graph/graph_traits.hpp>
-#include <boost/graph/adjacency_list.hpp>
-
-
+
-
-#define MAX_NODES 1000000
+
+#define ID_FEATURE     "id"
+#define COST_FEATURE   "cost"
+#define WEIGHT_FEATURE "weight"
+#define RC_FEATURE     "reverse_cost"
+
+#define SOURCE_FEATURE "source"
+#define TARGET_FEATURE "target"
+
+#define TO_COST_FEATURE "to_cost"
+#define RULE_FEATURE    "rule"
+
+#define EXIT_SUCCESS    0
+#define NO_SOURCE_FOUND 1
+#define NO_TARGET_FOUND 2
+#define NO_PATH_FOUND   3
+#define OVERFLOW        4
+
-
-using namespace std;
-using namespace boost;
-
-struct Edge
-{
-    int id;
-    double cost;
-};
-
-struct Vertex
-{
-  int id;
-  double x;
-  double y;
-};
-
-
-struct found_goal {}; // exception for termination
-
-// visitor that terminates when we find the goal
-template <class Vertex>
-class astar_goal_visitor : public boost::default_astar_visitor
-{
-public:
-  astar_goal_visitor(Vertex goal) : m_goal(goal) {}
-  template <class Graph>
-  void examine_vertex(Vertex u, Graph& g) {
-    if(u == m_goal)
-      throw found_goal();
-  }
-private:
-  Vertex m_goal;
-};
-
-template <class Graph, class CostType>
-class distance_heuristic : public astar_heuristic<Graph, CostType>
-{
-public:
-  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-  distance_heuristic(Graph& g, Vertex goal):m_g(g), m_goal(goal){}
-  CostType operator()(Vertex u)
-  {
-    CostType dx = m_g[m_goal].x - m_g[u].x;
-    CostType dy = m_g[m_goal].y - m_g[u].y;
-    //You can choose any heuristical function from below
-    //return ::max(dx, dy);
-    //return ::sqrt(dx * dx + dy * dy)/4;
-    //return 0;
-    return (::fabs(dx)+::fabs(dy))/2;
-  } 
-private:
-    Graph& m_g;
-    Vertex m_goal;
-};
-
-
-// FIXME: use a template for the directedS parameters
-typedef adjacency_list < listS, vecS, directedS, no_property, Edge > graph_t;
-
-typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
@@ -101 +64 @@
-            }
-    virtual ~Algorithm(){}
-    
-    static const char *costFeature;
-    static const char *weightFeature;
-    static const char *reverseCostFeature;
-    static const char *sourceFeature;
-    static const char *targetFeature;
-                   
-
-
-
+
+
+
+
+
+
-
-    //Template method for shortest path calculation
-*count, int *
-*
+count, int 
+
-    {      
-      // FIXME: compute this value
@@ -121 +81 @@
-      graph_t graph(num_nodes);
-      
-*
+
-      {
-        edge_descriptor *e; 
-        
-
-
-
-
-
+
-      }
-      
-Edges(
+ getRoute(start, end, result, resultCount, graph
-    }
-    
@@ -146 +102 @@
-};
-
-class Dijkstra : public Algorithm
-{
-  public:
-             Dijkstra(){}
-             Dijkstra( char *nameIn, bool directedIn, bool weightedIn, bool reverseCostIn )
-             : Algorithm( nameIn, directedIn, weightedIn, reverseCostIn )
-             {
-             } 
-    virtual ~Dijkstra(){}
-
-    static const char    *fieldList[];
-    static const int      fieldsCount;
-
-    bool addEdge(edge_descriptor *e, int source, int target, graph_t &graph)
-    {
-      bool inserted;  
-        
-      tie(*e, inserted) = add_edge(source, target, graph);
-      return inserted;
-    }
-    
-    void fillFeatures(OGRFeature **edges, edge_descriptor *e, graph_t &graph, int j)
-    {
-      graph[*e].cost = edges[j]->GetFieldAsDouble(Algorithm::costFeature);//set cost
-      graph[*e].id = j;//set id
-
-
-      if (!IsDirected() || (IsDirected() && HasReverseCost()))
-      {
-        edge_descriptor *er; 
-        //adding an edge for opposite direction
-        bool inserted = addEdge(er, edges[j]->GetFieldAsInteger(Algorithm::sourceFeature), 
-                                edges[j]->GetFieldAsInteger(Algorithm::targetFeature), graph);
-
-        graph[*er].id = j;//set id
-    
-        if (HasReverseCost())
-        {
-          graph[*er].cost = edges[j]->GetFieldAsDouble(Algorithm::reverseCostFeature);//set reverse cost
-        }
-        else 
-        {
-          graph[*er].cost = edges[j]->GetFieldAsDouble(Algorithm::costFeature);//set cost
-        }
-      }    
-    }  
-};
-
-class AStar : public Algorithm
-{
-  public:
-             AStar();
-             AStar(char*, bool, bool, bool);
-    virtual ~AStar();
-    
-    static const char    *fieldList[];
-    static const int      fieldsCount;    
-
-    bool addEdge(edge_descriptor *e, int source, int target, graph_t &graph)
-    {
-      bool inserted;  
-
-      // edges are not inserted in the graph if cost is negative
-      if (edges[j]->GetFieldAsDouble(Algorithm::costFeature) < 0) 
-      return;
-        
-      tie(*e, inserted) = add_edge(source, target, graph);
-      return inserted;
-    }
-
-
-}; 
-
-class ShootingStar : public Algorithm
-{    
-  public:
-             ShootingStar();
-             ShootingStar(char*, bool, bool, bool);
-    virtual ~ShootingStar();
-
-    static const char    *fieldList[];
-    static const int      fieldsCount;
-};  
-
-#endif