Fawkes API  Fawkes Development Version
navgraph.h
1 
2 /***************************************************************************
3  * navgraph.h - Topological graph
4  *
5  * Created: Fri Sep 21 15:48:00 2012
6  * Copyright 2012 Tim Niemueller [www.niemueller.de]
7  ****************************************************************************/
8 
9 /* This program is free software; you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by
11  * the Free Software Foundation; either version 2 of the License, or
12  * (at your option) any later version. A runtime exception applies to
13  * this software (see LICENSE.GPL_WRE file mentioned below for details).
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU Library General Public License for more details.
19  *
20  * Read the full text in the LICENSE.GPL_WRE file in the doc directory.
21  */
22 
23 #ifndef _LIBS_NAVGRAPH_NAVGRAPH_H_
24 #define _LIBS_NAVGRAPH_NAVGRAPH_H_
25 
26 #include <core/utils/lockptr.h>
27 #include <navgraph/navgraph_edge.h>
28 #include <navgraph/navgraph_node.h>
29 #include <navgraph/navgraph_path.h>
30 
31 #include <functional>
32 #include <list>
33 #include <string>
34 #include <vector>
35 
36 namespace fawkes {
37 
38 namespace navgraph {
39 typedef std::function<float(const fawkes::NavGraphNode &, const fawkes::NavGraphNode &)>
40  EstimateFunction;
41 typedef std::function<float(const fawkes::NavGraphNode &, const fawkes::NavGraphNode &)>
42  CostFunction;
43 
44 extern const char *PROP_ORIENTATION;
45 } // namespace navgraph
46 
47 class NavGraphConstraintRepo;
48 
49 class NavGraph
50 {
51 public:
52  /** Connect mode enum for connect_node_* methods. */
53  typedef enum {
54  CLOSEST_NODE, ///< Connect to closest node
55  CLOSEST_EDGE, ///< Connect to closest edge
56  CLOSEST_EDGE_OR_NODE ///< try to connect to closest edge,
57  ///< if that fails, connect to closest node
59 
60  /** Mode to use to add edges. */
61  typedef enum {
62  EDGE_FORCE, ///< add nodes no matter what (be careful)
63  EDGE_NO_INTERSECTION, ///< Only add edge if it does not intersect
64  ///< with any existing edge
65  EDGE_SPLIT_INTERSECTION ///< Add the edge, but if it intersects with
66  ///< an existing edges add new points at the
67  ///< intersection points for both, the conflicting
68  ///< edges and the new edge
70 
71  NavGraph(const std::string &graph_name);
72  NavGraph(const NavGraph &g);
73  virtual ~NavGraph();
74 
75  std::string name() const;
76  const std::vector<NavGraphNode> & nodes() const;
77  const std::vector<NavGraphEdge> & edges() const;
79 
80  const std::map<std::string, std::string> &default_properties() const;
81  bool has_default_property(const std::string &property) const;
82 
83  std::string default_property(const std::string &prop) const;
84  float default_property_as_float(const std::string &prop) const;
85  int default_property_as_int(const std::string &prop) const;
86  bool default_property_as_bool(const std::string &prop) const;
87 
88  void set_default_property(const std::string &property, const std::string &value);
89  void set_default_property(const std::string &property, float value);
90  void set_default_property(const std::string &property, int value);
91  void set_default_property(const std::string &property, bool value);
92  void set_default_properties(const std::map<std::string, std::string> &properties);
93 
95 
96  NavGraphNode node(const std::string &name) const;
97 
98  NavGraphNode closest_node(float pos_x, float pos_y, const std::string &property = "") const;
99 
100  NavGraphNode closest_node_to(const std::string &node_name,
101  const std::string &property = "") const;
102 
103  NavGraphNode closest_node(float pos_x,
104  float pos_y,
105  bool consider_unconnected,
106  const std::string &property = "") const;
107 
108  NavGraphNode closest_node_to(const std::string &node_name,
109  bool consider_unconnected,
110  const std::string &property = "") const;
111 
113  closest_node_with_unconnected(float pos_x, float pos_y, const std::string &property = "") const;
114 
115  NavGraphNode closest_node_to_with_unconnected(const std::string &node_name,
116  const std::string &property = "") const;
117 
118  NavGraphEdge edge(const std::string &from, const std::string &to) const;
119  NavGraphEdge closest_edge(float pos_x, float pos_y) const;
120 
121  std::vector<NavGraphNode> search_nodes(const std::string &property) const;
122 
123  std::vector<std::string> reachable_nodes(const std::string &node_name) const;
124 
125  fawkes::NavGraphPath search_path(const std::string &from,
126  const std::string &to,
127  bool use_constraints = true,
128  bool compute_constraints = true);
129 
130  fawkes::NavGraphPath search_path(const std::string & from,
131  const std::string & to,
132  navgraph::EstimateFunction estimate_func,
133  navgraph::CostFunction cost_func,
134  bool use_constraints = true,
135  bool compute_constraints = true);
136 
138  const NavGraphNode &to,
139  bool use_constraints = true,
140  bool compute_constraints = true);
141 
143  const NavGraphNode & to,
144  navgraph::EstimateFunction estimate_func,
145  navgraph::CostFunction cost_func,
146  bool use_constraints = true,
147  bool compute_constraints = true);
148 
149  void add_node(const NavGraphNode &node);
150  void add_node_and_connect(const NavGraphNode &node, ConnectionMode conn_mode);
153  void add_edge(const NavGraphEdge &edge,
155  bool allow_existing = false);
156  void remove_node(const NavGraphNode &node);
157  void remove_node(const std::string &node_name);
158  void remove_orphan_nodes();
159  void remove_edge(const NavGraphEdge &edge);
160  void remove_edge(const std::string &from, const std::string &to);
161  void clear();
162 
163  void update_node(const NavGraphNode &node);
164  void update_edge(const NavGraphEdge &edge);
165 
166  bool node_exists(const NavGraphNode &node) const;
167  bool node_exists(const std::string &name) const;
168  bool edge_exists(const NavGraphEdge &edge) const;
169  bool edge_exists(const std::string &from, const std::string &to) const;
170 
171  void calc_reachability(bool allow_multi_graph = false);
172 
173  NavGraph &operator=(const NavGraph &g);
174 
175  void set_notifications_enabled(bool enabled);
176  void notify_of_change() throw();
177 
179  {
180  public:
181  virtual ~ChangeListener();
182  virtual void graph_changed() throw() = 0;
183  };
184 
185  void add_change_listener(ChangeListener *listener);
186  void remove_change_listener(ChangeListener *listener);
187 
188  /** Check if the default euclidean distance search is used.
189  * @return true if the default cost and cost estimation functions
190  * are used, false of custom ones have been set.
191  */
192  bool
194  {
195  return search_default_funcs_;
196  }
197 
198  void set_search_funcs(navgraph::EstimateFunction estimate_func, navgraph::CostFunction cost_func);
199 
200  void unset_search_funcs();
201 
202  float cost(const NavGraphNode &from, const NavGraphNode &to) const;
203 
204  static std::string format_name(const char *format, ...);
205  std::string gen_unique_name(const char *prefix = "U-");
206 
207 private:
208  void assert_valid_edges();
209  void assert_connected();
210  void edge_add_no_intersection(const NavGraphEdge &edge);
211  void edge_add_split_intersection(const NavGraphEdge &edge);
212 
213 private:
214  std::string graph_name_;
215  std::vector<NavGraphNode> nodes_;
216  std::vector<NavGraphEdge> edges_;
218  std::list<ChangeListener *> change_listeners_;
219  std::map<std::string, std::string> default_properties_;
220 
221  bool search_default_funcs_;
222  navgraph::EstimateFunction search_estimate_func_;
223  navgraph::CostFunction search_cost_func_;
224 
225  bool reachability_calced_;
226 
227  bool notifications_enabled_;
228 };
229 
230 } // end of namespace fawkes
231 
232 #endif
LockPtr<> is a reference-counting shared lockable smartpointer.
Definition: lockptr.h:55
Topological graph edge.
Definition: navgraph_edge.h:38
Topological graph node.
Definition: navgraph_node.h:36
Class representing a path for a NavGraph.
Definition: navgraph_path.h:37
Topological graph change listener.
Definition: navgraph.h:179
virtual void graph_changed()=0
Function called if the graph has been changed.
Topological map graph.
Definition: navgraph.h:50
ConnectionMode
Connect mode enum for connect_node_* methods.
Definition: navgraph.h:53
@ CLOSEST_EDGE
Connect to closest edge.
Definition: navgraph.h:55
@ CLOSEST_EDGE_OR_NODE
try to connect to closest edge, if that fails, connect to closest node
Definition: navgraph.h:56
@ CLOSEST_NODE
Connect to closest node.
Definition: navgraph.h:54
void update_node(const NavGraphNode &node)
Update a given node.
Definition: navgraph.cpp:716
void remove_change_listener(ChangeListener *listener)
Remove a change listener.
Definition: navgraph.cpp:1484
NavGraph & operator=(const NavGraph &g)
Assign/copy structures from another graph.
Definition: navgraph.cpp:107
std::vector< std::string > reachable_nodes(const std::string &node_name) const
Get nodes reachable from specified nodes.
Definition: navgraph.cpp:889
void clear()
Remove all nodes and edges from navgraph.
Definition: navgraph.cpp:747
NavGraphNode closest_node_to_with_unconnected(const std::string &node_name, const std::string &property="") const
Get node closest to another node with a certain property.
Definition: navgraph.cpp:231
virtual ~NavGraph()
Virtual empty destructor.
Definition: navgraph.cpp:94
void remove_orphan_nodes()
Remove orphan nodes.
Definition: navgraph.cpp:652
NavGraphEdge edge(const std::string &from, const std::string &to) const
Get a specified edge.
Definition: navgraph.cpp:329
void unset_search_funcs()
Reset actual and estimated cost function to defaults.
Definition: navgraph.cpp:944
bool has_default_property(const std::string &property) const
Check if graph has specified default property.
Definition: navgraph.cpp:769
NavGraphNode closest_node_with_unconnected(float pos_x, float pos_y, const std::string &property="") const
Get node closest to a specified point with a certain property.
Definition: navgraph.cpp:201
void add_edge(const NavGraphEdge &edge, EdgeMode mode=EDGE_NO_INTERSECTION, bool allow_existing=false)
Add an edge.
Definition: navgraph.cpp:584
bool default_property_as_bool(const std::string &prop) const
Get property converted to bol.
Definition: navgraph.cpp:814
void remove_edge(const NavGraphEdge &edge)
Remove an edge.
Definition: navgraph.cpp:677
void set_default_property(const std::string &property, const std::string &value)
Set property.
Definition: navgraph.cpp:824
std::string default_property(const std::string &prop) const
Get specified default property as string.
Definition: navgraph.cpp:779
const std::map< std::string, std::string > & default_properties() const
Get all default properties.
Definition: navgraph.cpp:759
float cost(const NavGraphNode &from, const NavGraphNode &to) const
Calculate cost between two adjacent nodes.
Definition: navgraph.cpp:1123
NavGraphNode closest_node(float pos_x, float pos_y, const std::string &property="") const
Get node closest to a specified point with a certain property.
Definition: navgraph.cpp:186
void update_edge(const NavGraphEdge &edge)
Update a given edge.
Definition: navgraph.cpp:733
void notify_of_change()
Notify all listeners of a change.
Definition: navgraph.cpp:1505
static std::string format_name(const char *format,...)
Create node name from a format string.
Definition: navgraph.cpp:1457
fawkes::LockPtr< NavGraphConstraintRepo > constraint_repo() const
Get locked pointer to constraint repository.
Definition: navgraph.cpp:152
std::vector< NavGraphNode > search_nodes(const std::string &property) const
Search nodes for given property.
Definition: navgraph.cpp:386
int default_property_as_int(const std::string &prop) const
Get property converted to int.
Definition: navgraph.cpp:804
void add_node(const NavGraphNode &node)
Add a node.
Definition: navgraph.cpp:460
bool uses_default_search() const
Check if the default euclidean distance search is used.
Definition: navgraph.h:193
void set_default_properties(const std::map< std::string, std::string > &properties)
Set default properties.
Definition: navgraph.cpp:834
void calc_reachability(bool allow_multi_graph=false)
Calculate eachability relations.
Definition: navgraph.cpp:1410
bool node_exists(const NavGraphNode &node) const
Check if a certain node exists.
Definition: navgraph.cpp:408
const std::vector< NavGraphNode > & nodes() const
Get nodes of the graph.
Definition: navgraph.cpp:133
EdgeMode
Mode to use to add edges.
Definition: navgraph.h:61
@ EDGE_SPLIT_INTERSECTION
Add the edge, but if it intersects with an existing edges add new points at the intersection points f...
Definition: navgraph.h:65
@ EDGE_NO_INTERSECTION
Only add edge if it does not intersect.
Definition: navgraph.h:63
@ EDGE_FORCE
add nodes no matter what (be careful)
Definition: navgraph.h:62
const std::vector< NavGraphEdge > & edges() const
Get edges of the graph.
Definition: navgraph.cpp:142
void set_notifications_enabled(bool enabled)
Enable or disable notifications.
Definition: navgraph.cpp:1498
float default_property_as_float(const std::string &prop) const
Get property converted to float.
Definition: navgraph.cpp:794
NavGraphEdge closest_edge(float pos_x, float pos_y) const
Get edge closest to a specified point.
Definition: navgraph.cpp:353
void connect_node_to_closest_node(const NavGraphNode &n)
Connect node to closest node.
Definition: navgraph.cpp:519
std::string gen_unique_name(const char *prefix="U-")
Generate a unique node name for the given prefix.
Definition: navgraph.cpp:1440
void remove_node(const NavGraphNode &node)
Remove a node.
Definition: navgraph.cpp:612
void set_search_funcs(navgraph::EstimateFunction estimate_func, navgraph::CostFunction cost_func)
Set cost and cost estimation function for searching paths.
Definition: navgraph.cpp:931
fawkes::NavGraphPath search_path(const std::string &from, const std::string &to, bool use_constraints=true, bool compute_constraints=true)
Search for a path between two nodes with default distance costs.
Definition: navgraph.cpp:1000
NavGraphNode node(const std::string &name) const
Get a specified node.
Definition: navgraph.cpp:163
std::string name() const
Get graph name.
Definition: navgraph.cpp:124
NavGraph(const std::string &graph_name)
Constructor.
Definition: navgraph.cpp:65
void apply_default_properties(NavGraphNode &node)
Set default properties on node for which no local value exists.
Definition: navgraph.cpp:875
bool edge_exists(const NavGraphEdge &edge) const
Check if a certain edge exists.
Definition: navgraph.cpp:433
void add_change_listener(ChangeListener *listener)
Add a change listener.
Definition: navgraph.cpp:1475
void connect_node_to_closest_edge(const NavGraphNode &n)
Connect node to closest edge.
Definition: navgraph.cpp:532
void add_node_and_connect(const NavGraphNode &node, ConnectionMode conn_mode)
Add a node and connect it to the graph.
Definition: navgraph.cpp:499
NavGraphNode closest_node_to(const std::string &node_name, const std::string &property="") const
Get node closest to another node with a certain property.
Definition: navgraph.cpp:216
Fawkes library namespace.