Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef _AIS_DIJKSTRA_HH
00018 #define _AIS_DIJKSTRA_HH
00019
00020 #include <map>
00021 #include <set>
00022 #include <limits>
00023 #include "graph.h"
00024
00025 namespace AISNavigation{
00026
00027 struct Dijkstra{
00028 struct CostFunction {
00029 virtual double operator() (Graph::Edge* e, Graph::Vertex* from, Graph::Vertex* to)=0;
00030 };
00031
00032 struct TreeAction {
00033 virtual double perform(Graph::Vertex* v, Graph::Vertex* vParent, Graph::Edge* e)=0;
00034 };
00035
00036
00037 struct AdjacencyMapEntry{
00038 friend struct Dijkstra;
00039 AdjacencyMapEntry(Graph::Vertex* _child=0,
00040 Graph::Vertex* _parent=0,
00041 Graph::Edge* _edge=0,
00042 double _distance=std::numeric_limits<double>::max());
00043 inline Graph::Vertex* child() const {return _child;}
00044 inline Graph::Vertex* parent() const {return _parent;}
00045 inline Graph::Edge* edge() const {return _edge;}
00046 inline double distance() const {return _distance;}
00047 inline Graph::VertexSet& children() {return _children;}
00048 protected:
00049 Graph::Vertex* _child;
00050 Graph::Vertex* _parent;
00051 Graph::Edge* _edge;
00052 double _distance;
00053 Graph::VertexSet _children;
00054 };
00055
00056 typedef std::map<Graph::Vertex*, AdjacencyMapEntry> AdjacencyMap;
00057 Dijkstra(Graph* g);
00058 inline Graph::VertexSet& visited() {return _visited; }
00059 inline AdjacencyMap& adjacencyMap() {return _adjacencyMap; }
00060 inline Graph* graph() {return _graph;}
00061 void shortestPaths(Graph::Vertex* v,
00062 Dijkstra::CostFunction* cost,
00063 double maxDistance=std::numeric_limits< double >::max(),
00064 double comparisonConditioner=1e-3,
00065 bool directed=false);
00066
00067 static void computeTree(Graph::Vertex* v, AdjacencyMap& amap);
00068 static void visitAdjacencyMap(Graph::Vertex* v, AdjacencyMap& amap, TreeAction* action);
00069
00070 protected:
00071 void reset();
00072
00073 AdjacencyMap _adjacencyMap;
00074 Graph::VertexSet _visited;
00075 Graph* _graph;
00076
00077
00078 };
00079
00080 void connectedSubset(Graph::VertexSet& connected, Graph::VertexSet& visited,
00081 Graph::VertexSet& startingSet,
00082 Graph* g, Graph::Vertex* v,
00083 Dijkstra::CostFunction* cost, double distance, double comparisonConditioner);
00084
00085
00086 struct UniformCostFunction: public Dijkstra::CostFunction {
00087 virtual double operator ()(Graph::Edge* edge, Graph::Vertex* from, Graph::Vertex* to);
00088 };
00089
00090
00091
00092 }
00093 #endif