OdinAI
 All Classes Namespaces Functions Variables
DijkstraGraphSearch.h
1 #ifndef ODINAI_DIJKSTRA_GRAPH_SEARCH_H_
2 #define ODINAI_DIJKSTRA_GRAPH_SEARHC_H_
3 
4 #include "PriorityQueue.h"
5 #include <list>
6 
7 namespace OdinAI
8 {
22 template <class GraphType, class TargetCondition = int>
24 {
25 private:
26  typedef typename GraphType::EdgeType Edge;
27 
28 private:
29  const GraphType& m_Graph;
30 
31  std::vector<const Edge*> m_ShortestPathTree;
32 
33  std::vector<int> m_CostToThisNode;
34 
35  std::vector<const Edge*> m_SearchFrontier;
36 
37  int m_iSource;
38  int m_iTarget;
39 
43  void Search();
44 public:
45 
46  DijkstraGraphSearch(const GraphType &graph,
47  int source,
48  int target=-1) :
49  m_Graph(graph),
50  m_ShortestPathTree(graph.NumNodes()),
51  m_SearchFrontier(graph.NumNodes()),
52  m_CostToThisNode(graph.NumNodes()),
53  m_iSource(source),
54  m_iTarget(target)
55  {
56  Search();
57  }
58 
63  std::vector<const Edge*> GetSPT() const{ return m_ShortestPathTree; }
64 
69  std::list<int> GetPath() const;
70 
75  int GetCostToTarget()const{ return m_CostToThisNode[m_iTarget]; }
76 
81  int GetCostToNode(unsigned int nd) const { return m_CostToThisNode[nd]; }
82 };
83 
84 template <class GraphType, class TargetCondition>
85 void DijkstraGraphSearch<GraphType, TargetCondition>::Search()
86 {
87  IndexedPriorityQLow<double> pq(m_CostToThisNode, m_Graph.NumNodes());
88 
89  pq.insert(m_iSource);
90 
91  // While the queue is not empty
92  while(!pq.empty())
93  {
94  int nextClosestNode = pq.Pop();
95 
96  m_ShortestPathTree[NextClosestNode] = m_SearchFrontier[nextClosestNode];
97 
98  if ((m_iTarget != 1 && nextClosestNode == m_iTarget) || (m_iTarget == -1 && TargetCondition::)
99  {
100  m_iTarget = NextClosestNode;
101  return;
102  }
103 
104  GraphType::ConstEdgeIterator ConstEdgeItr(m_Graph, nextClosestNode);
105  for (const Edge* pE=ConstEdgeItr.begin();
106  !ConstEdgeItr.end();
107  pE=ConstEdgeItr.next())
108  {
109  int NewCost = m_CostToThisNode[nextClosestNode] + pE->Cost();
110 
111  if (m_SearchFrontier[pE->To()] == nullptr)
112  {
113  m_CostToThisNode[pE->To()] = NewCost;
114 
115  pq.insert(pE->To());
116 
117  m_SearchFrontier[pE->To()] = pE;
118  }
119  else if ((NewCost < m_CostToThisNode[pE->To()]) &&
120  (m_ShortestPathTree[pE->To()] == nullptr))
121  {
122  m_CostToThisNode[pE->To()] = NewCost;
123 
124  pq.ChangePriority(pE->To());
125 
126  m_SearchFrontier[pE->To()] = pE;
127  }
128  }
129  }
130 }
131 
132 //-----------------------------------------------------------------------------
133 template <class GraphType, class TargetCondition>
135 {
136  std::list<int> path;
137 
138  //just return an empty path if no target or no path found
139  if (m_iTarget < 0) return path;
140 
141  int nd = m_iTarget;
142  path.push_front(nd);
143 
144  while ((nd != m_iSource) && (m_ShortestPathTree[nd] != nullptr))
145  {
146  nd = m_ShortestPathTree[nd]->From();
147 
148  path.push_front(nd);
149  }
150 
151  return path;
152 }
153 }
154 #endif
Given a graph, and an optional target, it calculates the shortest path from the source node to the ta...
Definition: DijkstraGraphSearch.h:23
std::list< int > GetPath() const
Definition: DijkstraGraphSearch.h:134
std::vector< const Edge * > GetSPT() const
Definition: DijkstraGraphSearch.h:63
int GetCostToNode(unsigned int nd) const
Definition: DijkstraGraphSearch.h:81
int GetCostToTarget() const
Definition: DijkstraGraphSearch.h:75