dijkstra.h
Go to the documentation of this file.
00001 // HOG-Man - Hierarchical Optimization for Pose Graphs on Manifolds
00002 // Copyright (C) 2010 G. Grisetti, R. Kümmerle, C. Stachniss
00003 // 
00004 // HOG-Man is free software: you can redistribute it and/or modify
00005 // it under the terms of the GNU Lesser General Public License as published
00006 // by the Free Software Foundation, either version 3 of the License, or
00007 // (at your option) any later version.
00008 // 
00009 // HOG-Man is distributed in the hope that it will be useful,
00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012 // GNU Lesser General Public License for more details.
00013 // 
00014 // You should have received a copy of the GNU Lesser General Public License
00015 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
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


hogman_minimal
Author(s): Maintained by Juergen Sturm
autogenerated on Mon Oct 6 2014 00:06:58