g2o
hyper_dijkstra.h
Go to the documentation of this file.
1 // g2o - General Graph Optimization
2 // Copyright (C) 2011 R. Kuemmerle, G. Grisetti, W. Burgard
3 // All rights reserved.
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
7 // met:
8 //
9 // * Redistributions of source code must retain the above copyright notice,
10 // this list of conditions and the following disclaimer.
11 // * Redistributions in binary form must reproduce the above copyright
12 // notice, this list of conditions and the following disclaimer in the
13 // documentation and/or other materials provided with the distribution.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
16 // IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
17 // TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
18 // PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
21 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 
27 #ifndef G2O_AIS_GENERAL_DIJKSTRA_HH
28 #define G2O_AIS_GENERAL_DIJKSTRA_HH
29 
30 #include <map>
31 #include <set>
32 #include <limits>
33 
34 #include "hyper_graph.h"
35 
36 namespace g2o{
37 
40  virtual double operator() (HyperGraph::Edge* e, HyperGraph::Vertex* from, HyperGraph::Vertex* to)=0;
41  virtual ~CostFunction() { }
42  };
43 
45  virtual double perform(HyperGraph::Vertex* v, HyperGraph::Vertex* vParent, HyperGraph::Edge* e);
46  virtual double perform(HyperGraph::Vertex* v, HyperGraph::Vertex* vParent, HyperGraph::Edge* e, double distance);
47  };
48 
49 
51  friend struct HyperDijkstra;
53  HyperGraph::Vertex* _parent=0,
54  HyperGraph::Edge* _edge=0,
55  double _distance=std::numeric_limits<double>::max());
56  HyperGraph::Vertex* child() const {return _child;}
57  HyperGraph::Vertex* parent() const {return _parent;}
58  HyperGraph::Edge* edge() const {return _edge;}
59  double distance() const {return _distance;}
60  HyperGraph::VertexSet& children() {return _children;}
61  const HyperGraph::VertexSet& children() const {return _children;}
62  protected:
66  double _distance;
68  };
69 
70  typedef std::map<HyperGraph::Vertex*, AdjacencyMapEntry> AdjacencyMap;
72  HyperGraph::VertexSet& visited() {return _visited; }
73  AdjacencyMap& adjacencyMap() {return _adjacencyMap; }
74  HyperGraph* graph() {return _graph;}
75 
76  void shortestPaths(HyperGraph::Vertex* v,
78  double maxDistance=std::numeric_limits< double >::max(),
79  double comparisonConditioner=1e-3,
80  bool directed=false,
81  double maxEdgeCost=std::numeric_limits< double >::max());
82 
83  void shortestPaths(HyperGraph::VertexSet& vset,
85  double maxDistance=std::numeric_limits< double >::max(),
86  double comparisonConditioner=1e-3,
87  bool directed=false,
88  double maxEdgeCost=std::numeric_limits< double >::max());
89 
90 
91  static void computeTree(AdjacencyMap& amap);
92  static void visitAdjacencyMap(AdjacencyMap& amap, TreeAction* action, bool useDistance=false);
93  static void connectedSubset(HyperGraph::VertexSet& connected, HyperGraph::VertexSet& visited,
94  HyperGraph::VertexSet& startingSet,
96  HyperDijkstra::CostFunction* cost, double distance, double comparisonConditioner,
97  double maxEdgeCost=std::numeric_limits< double >::max() );
98 
99  protected:
100  void reset();
101 
102  AdjacencyMap _adjacencyMap;
105  };
106 
108  virtual double operator ()(HyperGraph::Edge* edge, HyperGraph::Vertex* from, HyperGraph::Vertex* to);
109  };
110 
111 }
112 #endif
const HyperGraph::VertexSet & children() const
HyperGraph::VertexSet & visited()
HyperGraph * graph()
HyperGraph::VertexSet & children()
HyperGraph::Vertex * parent() const
std::set< Vertex * > VertexSet
Definition: hyper_graph.h:136
HyperGraph::Edge * edge() const
HyperGraph::VertexSet _visited
HyperGraph * _graph
std::map< HyperGraph::Vertex *, AdjacencyMapEntry > AdjacencyMap
abstract Vertex, your types must derive from that one
Definition: hyper_graph.h:142
AdjacencyMap & adjacencyMap()
AdjacencyMap _adjacencyMap
#define G2O_CORE_API
Definition: g2o_core_api.h:29
HyperGraph::Vertex * child() const