23 #include <navgraph/navgraph.h> 24 #include <navgraph/constraints/constraint_repo.h> 25 #include <navgraph/search_state.h> 26 #include <core/exception.h> 27 #include <utils/search/astar.h> 28 #include <utils/math/common.h> 37 #include <Eigen/Geometry> 45 const char *PROP_ORIENTATION =
"orientation";
71 graph_name_ = graph_name;
74 search_default_funcs_ =
true;
77 reachability_calced_ =
false;
78 notifications_enabled_ =
true;
99 graph_name_ = g.graph_name_;
123 const std::vector<NavGraphNode> &
133 const std::vector<NavGraphEdge> &
147 return constraint_repo_;
158 std::vector<NavGraphNode>::const_iterator n =
159 std::find_if(nodes_.begin(), nodes_.end(),
161 return node.name() == name;
163 if (n != nodes_.end()) {
183 return closest_node(pos_x, pos_y,
false, property);
198 const std::string &property)
const 200 return closest_node(pos_x, pos_y,
true, property);
214 const std::string &property)
const 216 return closest_node_to(node_name,
false, property);
230 const std::string &property)
const 232 return closest_node_to(node_name,
true, property);
247 const std::string &property)
const 249 std::vector<NavGraphNode> nodes = search_nodes(property);
251 float min_dist = HUGE;
253 std::vector<NavGraphNode>::iterator i;
254 std::vector<NavGraphNode>::iterator elem = nodes.begin();
255 for (i = nodes.begin(); i != nodes.end(); ++i) {
256 if (! consider_unconnected && i->unconnected())
continue;
258 float dx = i->x() - pos_x;
259 float dy = i->y() - pos_y;
260 float dist = sqrtf(dx * dx + dy * dy);
261 if (sqrtf(dx * dx + dy * dy) < min_dist) {
267 if (elem == nodes.end()) {
286 const std::string &property)
const 289 std::vector<NavGraphNode> nodes = search_nodes(property);
291 float min_dist = HUGE;
293 std::vector<NavGraphNode>::iterator i;
294 std::vector<NavGraphNode>::iterator elem = nodes.begin();
295 for (i = nodes.begin(); i != nodes.end(); ++i) {
296 if (! consider_unconnected && i->unconnected())
continue;
298 float dx = i->x() - n.
x();
299 float dy = i->y() - n.
y();
300 float dist = sqrtf(dx * dx + dy * dy);
301 if ((sqrtf(dx * dx + dy * dy) < min_dist) && (i->name() != node_name)) {
307 if (elem == nodes.end()) {
325 std::vector<NavGraphEdge>::const_iterator e =
326 std::find_if(edges_.begin(), edges_.end(),
328 return (edge.from() == from && edge.to() == to) ||
329 (! edge.is_directed() && (edge.to() == from && edge.from() == to));
331 if (e != edges_.end()) {
351 float min_dist = std::numeric_limits<float>::max();
355 Eigen::Vector2f point(pos_x, pos_y);
357 const Eigen::Vector2f origin(edge.from_node().x(), edge.from_node().y());
358 const Eigen::Vector2f target(edge.to_node().x(), edge.to_node().y());
359 const Eigen::Vector2f direction(target - origin);
360 const Eigen::Vector2f direction_norm = direction.normalized();
361 const Eigen::Vector2f diff = point - origin;
362 const float t = direction.dot(diff) / direction.squaredNorm();
364 if (t >= 0.0 && t <= 1.0) {
366 float distance = (diff - direction_norm.dot(diff) * direction_norm).norm();
367 if (distance < min_dist) {
381 std::vector<NavGraphNode>
384 if (property ==
"") {
387 std::vector<NavGraphNode> rv;
389 std::vector<NavGraphNode>::const_iterator i;
390 for (i = nodes_.begin(); i != nodes_.end(); ++i) {
391 if ( i->has_property(property) ) rv.push_back(*i);
406 std::vector<NavGraphNode>::const_iterator n =
407 std::find(nodes_.begin(), nodes_.end(), node);
408 return (n != nodes_.end());
419 std::vector<NavGraphNode>::const_iterator n =
420 std::find_if(nodes_.begin(), nodes_.end(),
422 return node.name() == name;
424 return (n != nodes_.end());
434 std::vector<NavGraphEdge>::const_iterator e =
435 std::find(edges_.begin(), edges_.end(), edge);
436 return (e != edges_.end());
447 std::vector<NavGraphEdge>::const_iterator e =
448 std::find_if(edges_.begin(), edges_.end(),
450 return (from == e.from() && to == e.to()) ||
451 (! e.is_directed() && (from == e.to() && to == e.from()));
453 return (e != edges_.end());
463 if (node_exists(node)) {
464 throw Exception(
"Node with name %s already exists", node.
name().c_str());
466 nodes_.push_back(node);
467 apply_default_properties(nodes_.back());
468 reachability_calced_ =
false;
475 typename std::enable_if<!std::numeric_limits<T>::is_integer,
bool>::type
476 almost_equal(T x, T y,
int ulp)
480 return (std::abs(x-y) < std::numeric_limits<T>::epsilon() * std::abs(x+y) * ulp)
482 || std::abs(x-y) < std::numeric_limits<T>::min();
505 connect_node_to_closest_node(node);
509 connect_node_to_closest_edge(node);
512 case CLOSEST_EDGE_OR_NODE:
514 connect_node_to_closest_edge(node);
516 connect_node_to_closest_node(node);
531 new_edge.set_property(
"generated",
true);
532 add_edge(new_edge, EDGE_SPLIT_INTERSECTION);
547 if (almost_equal(closest_conn.
distance(p.x, p.y), 0.f, 2)) {
558 new_edge.set_property(
"created-for", cn.
name() +
"--" + n.
name());
559 add_edge(new_edge, EDGE_SPLIT_INTERSECTION);
562 remove_edge(closest);
567 new_edge_2.set_properties(closest.
properties());
568 new_edge_3.set_property(
"created-for", cn.
name() +
"--" + n.
name());
569 new_edge_3.set_property(
"generated",
true);
571 if (! node_exists(cn)) add_node(cn);
572 add_edge(new_edge_1, EDGE_SPLIT_INTERSECTION);
573 add_edge(new_edge_2, EDGE_SPLIT_INTERSECTION);
574 add_edge(new_edge_3, EDGE_SPLIT_INTERSECTION);
594 if (edge_exists(edge)) {
595 if (allow_existing)
return;
596 else throw Exception(
"Edge from %s to %s already exists",
597 edge.
from().c_str(), edge.
to().c_str());
600 case EDGE_NO_INTERSECTION:
601 edge_add_no_intersection(edge);
604 case EDGE_SPLIT_INTERSECTION:
605 edge_add_split_intersection(edge);
609 edges_.push_back(edge);
610 edges_.back().set_nodes(node(edge.
from()), node(edge.
to()));
614 reachability_calced_ =
false;
626 nodes_.erase(std::remove(nodes_.begin(), nodes_.end(), node));
628 std::remove_if(edges_.begin(), edges_.end(),
630 return edge.from() == node.
name() || edge.to() == node.
name();
632 reachability_calced_ =
false;
643 std::remove_if(nodes_.begin(), nodes_.end(),
645 return node.name() == node_name;
648 std::remove_if(edges_.begin(), edges_.end(),
650 return edge.from() == node_name || edge.to() == node_name;
652 reachability_calced_ =
false;
663 std::remove_if(edges_.begin(), edges_.end(),
665 return (edge.
from() == e.from() && edge.
to() == e.to()) ||
666 (! e.is_directed() && (edge.
from() == e.to() && edge.
to() == e.from()));
668 reachability_calced_ =
false;
680 std::remove_if(edges_.begin(), edges_.end(),
682 return (edge.from() == from && edge.to() == to) ||
683 (! edge.is_directed() && (edge.to() == from && edge.from() == to));
685 reachability_calced_ =
false;
698 std::vector<NavGraphNode>::iterator n =
699 std::find(nodes_.begin(), nodes_.end(), node);
700 if (n != nodes_.end()) {
703 throw Exception(
"No node with name %s known", node.
name().c_str());
716 std::vector<NavGraphEdge>::iterator e =
717 std::find(edges_.begin(), edges_.end(), edge);
718 if (e != edges_.end()) {
721 throw Exception(
"No edge from %s to %s is known",
722 edge.
from().c_str(), edge.
to().c_str());
735 default_properties_.clear();
742 const std::map<std::string, std::string> &
745 return default_properties_;
755 return default_properties_.find(property) != default_properties_.end();
765 std::map<std::string, std::string>::const_iterator p;
766 if ((p = default_properties_.find(prop)) != default_properties_.end()) {
810 default_properties_[property] = value;
820 default_properties_ = properties;
851 default_properties_[property] = value ?
"true" :
"false";
863 for (
const auto &p : default_properties_) {
875 std::vector<std::string>
878 std::vector<std::string> rv;
883 std::vector<NavGraphEdge>::const_iterator i;
884 for (i = edges_.begin(); i != edges_.end(); ++i) {
885 if (i->is_directed()) {
886 if (i->from() == node_name) {
887 rv.push_back(i->to());
890 if (i->from() == node_name) {
891 rv.push_back(i->to());
892 }
else if (i->to() == node_name) {
893 rv.push_back(i->from());
898 std::sort(rv.begin(), rv.end());
899 std::unique(rv.begin(), rv.end());
919 navgraph::CostFunction cost_func)
921 if (! search_default_funcs_) {
922 throw Exception(
"Custom actual and estimated cost functions have already been set");
924 search_default_funcs_ =
false;
925 search_estimate_func_ = estimate_func;
926 search_cost_func_ = cost_func;
934 search_default_funcs_ =
true;
960 bool use_constraints,
bool compute_constraints)
962 return search_path(from, to,
963 search_estimate_func_, search_cost_func_,
964 use_constraints, compute_constraints);
988 bool use_constraints,
bool compute_constraints)
990 return search_path(from, to,
991 search_estimate_func_, search_cost_func_,
992 use_constraints, compute_constraints);
1020 navgraph::EstimateFunction estimate_func,
1021 navgraph::CostFunction cost_func,
1022 bool use_constraints,
bool compute_constraints)
1026 return search_path(from_node, to_node, estimate_func, cost_func,
1027 use_constraints, compute_constraints);
1055 navgraph::EstimateFunction estimate_func,
1056 navgraph::CostFunction cost_func,
1057 bool use_constraints,
bool compute_constraints)
1059 if (! reachability_calced_) calc_reachability(
true);
1063 std::vector<AStarState *> a_star_solution;
1065 if (use_constraints) {
1066 constraint_repo_.lock();
1067 if (compute_constraints && constraint_repo_->has_constraints()) {
1068 constraint_repo_->compute();
1074 a_star_solution = astar.
solve(initial_state);
1075 constraint_repo_.unlock();
1079 a_star_solution = astar.
solve(initial_state);
1082 std::vector<fawkes::NavGraphNode> path(a_star_solution.size());
1084 for (
unsigned int i = 0; i < a_star_solution.size(); ++i ) {
1086 path[i] = solstate->node();
1090 (! a_star_solution.empty())
1091 ? a_star_solution[a_star_solution.size() - 1]->total_estimated_cost
1109 return search_cost_func_(from, to);
1115 NavGraph::assert_valid_edges()
1117 for (
size_t i = 0; i < edges_.size(); ++i) {
1118 if (! node_exists(edges_[i].from())) {
1119 throw Exception(
"Node '%s' for edge '%s' -> '%s' does not exist",
1120 edges_[i].from().c_str(), edges_[i].from().c_str(),
1121 edges_[i].to().c_str());
1124 if (! node_exists(edges_[i].to())) {
1125 throw Exception(
"Node '%s' for edge '%s' -> '%s' does not exist",
1126 edges_[i].to().c_str(), edges_[i].from().c_str(),
1127 edges_[i].to().c_str());
1134 NavGraph::edge_add_no_intersection(
const NavGraphEdge &edge)
1140 if (edge.
from() == ne.from() || edge.
from() == ne.to() ||
1141 edge.
to() == ne.to() || edge.
to() == ne.from())
continue;
1143 if (ne.intersects(n1.
x(), n1.
y(), n2.x(), n2.y())) {
1144 throw Exception(
"Edge %s-%s%s not added: intersects with %s-%s%s",
1146 ne.from().c_str(), ne.is_directed() ?
">" :
"-", ne.to().c_str());
1149 add_edge(edge, EDGE_FORCE);
1151 throw Exception(
"Failed to add edge %s-%s%s: %s",
1159 NavGraph::edge_add_split_intersection(
const NavGraphEdge &edge)
1161 std::list<std::pair<cart_coord_2d_t, NavGraphEdge>> intersections;
1169 if (e.intersection(n1.
x(), n1.
y(), n2.x(), n2.y(), ip)) {
1172 intersections.push_back(std::make_pair(ip, e));
1176 std::list<std::list<std::pair<cart_coord_2d_t, NavGraphEdge> >::iterator> deletions;
1178 for (
auto i1 = intersections.begin(); i1 != intersections.end(); ++i1) {
1179 const std::pair<cart_coord_2d_t, NavGraphEdge> &p1 = *i1;
1186 for (
auto i2 = std::next(i1); i2 != intersections.end(); ++i2) {
1187 const std::pair<cart_coord_2d_t, NavGraphEdge> &p2 = *i2;
1196 }
else if (e1.
to() == e2.
to() || e1.
to() == e2.
from()) {
1202 deletions.push_back(i1);
1207 for (
auto d = deletions.rbegin(); d != deletions.rend(); ++d) {
1208 intersections.erase(*d);
1211 if (intersections.empty()) {
1214 add_edge(e, EDGE_FORCE);
1216 Eigen::Vector2f e_origin(n1.
x(), n1.
y());
1217 Eigen::Vector2f e_target(n2.x(), n2.y());
1218 Eigen::Vector2f e_dir = (e_target - e_origin).normalized();
1220 intersections.sort([&e_origin, &e_dir](
const std::pair<cart_coord_2d_t, NavGraphEdge> &p1,
1221 const std::pair<cart_coord_2d_t, NavGraphEdge> &p2)
1223 const Eigen::Vector2f p1p(p1.first.x, p1.first.y);
1224 const Eigen::Vector2f p2p(p2.first.x, p2.first.y);
1225 const float k1 = e_dir.dot(p1p - e_origin);
1226 const float k2 = e_dir.dot(p2p - e_origin);
1230 std::string en_from = edge.
from();
1232 std::string prev_to;
1233 for (
const auto &i : intersections) {
1251 add_edge(e1, EDGE_FORCE,
true);
1252 add_edge(e2, EDGE_FORCE,
true);
1262 if (en_from != ip.
name() && prev_to != ip.
name()) {
1265 add_edge(e3, EDGE_FORCE,
true);
1269 en_from = ip.
name();
1273 if (en_from != edge.
to()) {
1276 add_edge(e3, EDGE_FORCE,
true);
1281 throw Exception(
"Failed to add edge %s-%s%s: %s",
1290 NavGraph::assert_connected()
1292 std::set<std::string> traversed;
1293 std::set<std::string> nodeset;
1294 std::queue<NavGraphNode> q;
1297 auto fcon = std::find_if_not(nodes_.begin(), nodes_.end(),
1299 {
return n.unconnected(); });
1300 if (fcon == nodes_.end()) {
1307 while (! q.empty()) {
1309 traversed.insert(n.
name());
1314 throw Exception(
"Node %s is marked unconnected but nodes are reachable from it",
1317 std::vector<std::string>::const_iterator r;
1318 for (r = reachable.begin(); r != reachable.end(); ++r) {
1321 throw Exception(
"Node %s is marked unconnected but is reachable from node %s\n",
1322 target.
name().c_str(), n.
name().c_str());
1324 if (traversed.find(*r) == traversed.end()) q.push(node(*r));
1329 std::vector<NavGraphNode>::iterator n;
1330 for (n = nodes_.begin(); n != nodes_.end(); ++n) {
1331 nodeset.insert(n->name());
1334 if (traversed.size() != nodeset.size()) {
1335 std::set<std::string> nodediff;
1336 std::set_difference(nodeset.begin(), nodeset.end(),
1337 traversed.begin(), traversed.end(),
1338 std::inserter(nodediff, nodediff.begin()));
1344 std::set<std::string>::const_iterator ud = nodediff.begin();
1345 while (ud != nodediff.end()) {
1351 throw Exception(
"Node %s is marked unconnected but nodes are reachable from it",
1354 #if __cplusplus > 201100L || defined(__GXX_EXPERIMENTAL_CXX0X__) 1355 ud = nodediff.erase(ud);
1357 std::set<std::string>::const_iterator delit = ud;
1359 nodediff.erase(delit);
1366 if (! nodediff.empty()) {
1367 std::set<std::string>::iterator d = nodediff.begin();
1368 std::string disconnected = *d;
1369 for (++d; d != nodediff.end(); ++d) {
1370 disconnected +=
", " + *d;
1372 throw Exception(
"The graph is not fully connected, " 1373 "cannot reach (%s) from '%s' for example",
1374 disconnected.c_str(), fcon->name().c_str());
1389 if (nodes_.empty())
return;
1391 assert_valid_edges();
1393 std::vector<NavGraphNode>::iterator i;
1394 for (i = nodes_.begin(); i != nodes_.end(); ++i) {
1395 i->set_reachable_nodes(reachable_nodes(i->name()));
1398 std::vector<NavGraphEdge>::iterator e;
1399 for (e = edges_.begin(); e != edges_.end(); ++e) {
1400 e->set_nodes(node(e->from()), node(e->to()));
1403 if (! allow_multi_graph) assert_connected();
1404 reachability_calced_ =
true;
1418 for (
unsigned int i = 0; i < std::numeric_limits<unsigned int>::max(); ++i) {
1419 std::string name = format_name(
"%s%i", prefix, i);
1424 throw Exception(
"Cannot generate unique name for given prefix, all taken");
1437 va_start(arg, format);
1440 if (vasprintf(&tmp, format, arg) != -1) {
1454 change_listeners_.push_back(listener);
1463 change_listeners_.remove(listener);
1478 notifications_enabled_ = enabled;
1485 if (! notifications_enabled_)
return;
1487 std::list<ChangeListener *> tmp_listeners = change_listeners_;
1489 std::list<ChangeListener *>::iterator l;
1490 for (l = tmp_listeners.begin(); l != tmp_listeners.end(); ++l) {
1491 (*l)->graph_changed();
void add_node_and_connect(const NavGraphNode &node, ConnectionMode conn_mode)
Add a node and connect it to the graph.
const std::string & from() const
Get edge originating node name.
NavGraphEdge closest_edge(float pos_x, float pos_y) const
Get edge closest to a specified point.
fawkes::LockPtr< NavGraphConstraintRepo > constraint_repo() const
Get locked pointer to constraint repository.
void remove_edge(const NavGraphEdge &edge)
Remove an edge.
float default_property_as_float(const std::string &prop) const
Get property converted to float.
void set_property(const std::string &property, const std::string &value)
Set property.
bool default_property_as_bool(const std::string &prop) const
Get property converted to bol.
float distance(const NavGraphNode &n)
Get euclidean distance from this node to another.
float distance(float x1, float y1, float x2, float y2)
Get distance between two 2D cartesian coordinates.
const std::map< std::string, std::string > & default_properties() const
Get all default properties.
float point_dist(float x1, float y1, float x2, float y2)
Get distance of two points.
Cartesian coordinates (2D).
bool points_different(float x1, float y1, float x2, float y2, float threshold=1e-4)
Check if two points are different with regard to a given threshold.
Fawkes library namespace.
void set_default_property(const std::string &property, const std::string &value)
Set property.
void remove_node(const NavGraphNode &node)
Remove a node.
Graph-based path planner A* search state.
NavGraph & operator=(const NavGraph &g)
Assign/copy structures from another graph.
void set_properties(const std::map< std::string, std::string > &properties)
Overwrite properties with given ones.
void set_default_properties(const std::map< std::string, std::string > &properties)
Set default properties.
bool is_directed() const
Check if edge is directed.
static float straight_line_estimate(const fawkes::NavGraphNode &node, const fawkes::NavGraphNode &goal)
Determine straight line estimate between two nodes.
void add_node(const NavGraphNode &node)
Add a node.
std::vector< AStarState * > solve(AStarState *initialState)
Solves a situation given by the initial state with AStar, and returns a vector of AStarStates that so...
static std::string format_name(const char *format,...)
Create node name from a format string.
bool has_property(const std::string &property) const
Check if node has specified property.
Class representing a path for a NavGraph.
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.
bool is_valid() const
Check if node is valid, i.e.
std::vector< NavGraphNode > search_nodes(const std::string &property) const
Search nodes for given property.
bool edge_exists(const NavGraphEdge &edge) const
Check if a certain edge exists.
const std::map< std::string, std::string > & properties() const
Get all properties.
virtual ~ChangeListener()
Virtual empty destructor.
const std::vector< NavGraphNode > & nodes() const
Get nodes of the graph.
void add_change_listener(ChangeListener *listener)
Add a change listener.
static int to_int(std::string s)
Convert string to an int value.
std::vector< std::string > reachable_nodes(const std::string &node_name) const
Get nodes reachable from specified nodes.
LockPtr<> is a reference-counting shared lockable smartpointer.
void update_edge(const NavGraphEdge &edge)
Update a given edge.
void set_search_funcs(navgraph::EstimateFunction estimate_func, navgraph::CostFunction cost_func)
Set cost and cost estimation function for searching paths.
void update_node(const NavGraphNode &node)
Update a given node.
std::string name() const
Get graph name.
Constraint repository to maintain blocks on nodes.
EdgeMode
Mode to use to add edges.
void unset_search_funcs()
Reset actual and estimated cost function to defaults.
std::string gen_unique_name(const char *prefix="U-")
Generate a unique node name for the given prefix.
NavGraph(const std::string &graph_name)
Constructor.
void add_edge(const NavGraphEdge &edge, EdgeMode mode=EDGE_NO_INTERSECTION, bool allow_existing=false)
Add an edge.
fawkes::cart_coord_2d_t closest_point_on_edge(float x, float y) const
Get the point on edge closest to a given point.
void set_notifications_enabled(bool enabled)
Enable or disable notifications.
Base class for exceptions in Fawkes.
const std::string & to() const
Get edge target node name.
std::string default_property(const std::string &prop) const
Get specified default property as string.
void set_property(const std::string &property, const std::string &value)
Set property.
void remove_change_listener(ChangeListener *listener)
Remove a change listener.
void connect_node_to_closest_edge(const NavGraphNode &n)
Connect node to closest edge.
NavGraphEdge edge(const std::string &from, const std::string &to) const
Get a specified edge.
NavGraphNode node(const std::string &name) const
Get a specified node.
const std::string & name() const
Get name of node.
bool node_exists(const NavGraphNode &node) const
Check if a certain node exists.
void clear()
Remove all nodes and edges from navgraph.
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.
void apply_default_properties(NavGraphNode &node)
Set default properties on node for which no local value exists.
void notify_of_change()
Notify all listeners of a change.
const std::vector< NavGraphEdge > & edges() const
Get edges of the graph.
virtual const char * what_no_backtrace() const
Get primary string (does not implicitly print the back trace).
float y() const
Get Y coordinate in global frame.
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.
int default_property_as_int(const std::string &prop) const
Get property converted to int.
bool unconnected() const
Check if this node shall be unconnected.
NavGraphNode closest_node_to(const std::string &node_name, const std::string &property="") const
Get node closest to another node with a certain property.
static float euclidean_cost(const fawkes::NavGraphNode &from, const fawkes::NavGraphNode &to)
Determine euclidean cost between two nodes.
virtual ~NavGraph()
Virtual empty destructor.
bool has_default_property(const std::string &property) const
Check if graph has specified default property.
float x() const
Get X coordinate in global frame.
static float to_float(std::string s)
Convert string to a float value.
static bool to_bool(std::string s)
Convert string to a bool value.
Topological graph change listener.
const std::vector< std::string > & reachable_nodes() const
Get reachable nodes.
ConnectionMode
Connect mode enum for connect_node_* methods.
static std::string to_string(unsigned int i)
Convert unsigned int value to a string.
void calc_reachability(bool allow_multi_graph=false)
Calculate eachability relations.
void connect_node_to_closest_node(const NavGraphNode &n)
Connect node to closest node.
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.
float cost(const NavGraphNode &from, const NavGraphNode &to) const
Calculate cost between two adjacent nodes.