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
36namespace fawkes {
37
38namespace navgraph {
39typedef std::function<float(const fawkes::NavGraphNode &, const fawkes::NavGraphNode &)>
40 EstimateFunction;
41typedef std::function<float(const fawkes::NavGraphNode &, const fawkes::NavGraphNode &)>
42 CostFunction;
43
44extern const char *PROP_ORIENTATION;
45} // namespace navgraph
46
47class NavGraphConstraintRepo;
48
50{
51public:
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);
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() noexcept;
177
179 {
180 public:
181 virtual ~ChangeListener();
182 virtual void graph_changed() noexcept = 0;
183 };
184
185 void add_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
207private:
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
213private:
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() noexcept=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
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
void notify_of_change() noexcept
Notify all listeners of a change.
Definition: navgraph.cpp:1505
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.