- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我有以下无向图类:
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Vertex, Edge> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor VertexDesc;
typedef boost::graph_traits<Graph>::edge_descriptor EdgeDesc;
typedef boost::graph_traits<Graph>::vertex_iterator VertexIter;
typedef boost::graph_traits<Graph>::edge_iterator EdgeIter;
struct GraphContainer
{
std::map<OcTreeNode*, VertexDesc> revmap;
Graph graph;
};
用顶点和加权边填充图形后,我尝试运行 Dijkstra 并提取一条从起点到终点的路径。
注:该图是空间中3D点的图,边权重由下式给出:
g->graph[e].weight = 1.0 + pow(coord.distance(coord1), 2) + 4 * pow(coord.z() - coord1.z(), 2);
所以它总是积极的。
这里是获取解决方案的代码:
GraphContainer *g = ...;
boost::print_graph(g->graph);
octomap::point3d startPos = ...;
VertexDesc start = closestVertexDescriptor(g, startPos);
std::cout << "start: " << start << " " << startPos << std::endl;
octomap::point3d goalPos = ...;
VertexDesc goal = closestVertexDescriptor(g, goalPos);
std::cout << "goal: " << goal << " " << goalPos << std::endl;
auto idmap = boost::get(boost::vertex_index, g->graph);
std::vector<VertexDesc> predecessors(boost::num_vertices(g->graph));
std::vector<int> distances(boost::num_vertices(g->graph));
dijkstra_shortest_paths(g->graph, goal,
boost::weight_map(boost::get(&Edge::weight, g->graph))
.distance_map(boost::make_iterator_property_map(distances.begin(), idmap))
.predecessor_map(boost::make_iterator_property_map(predecessors.begin(), idmap))
);
// extract path
std::vector<VertexDesc> path;
VertexDesc current = goal;
while(current != start)
{
std::cout << "extract path: " << current << " " << g->graph[current].coord << " <- " << predecessors[current] << std::endl;
path.push_back(current);
if(current == predecessors[current])
{
std::cout << "extract path: detected cycle!" << std::endl;
break;
}
current = predecessors[current];
}
path.push_back(start);
输出:(图形打印输出太大,在:https://drive.google.com/file/d/1nbTyCo_-tMfpH4bblurv-IYcumjjuKFK/view?usp=sharing 获取 graph.txt)
start: 8088 (0.725003 1.675 1.21072e-05)
goal: 10302 (2.925 4.025 3.77501)
extract path: 10302 (2.95 4.05 3.75) <- 10302
extract path: detected cycle!
代码来自 https://www.ics.uci.edu/~eppstein/161/python/dijkstra.py加上以下代码段:
G = {}
def add_edge(v0,v1,w=1):
global G
for v in (v0,v1):
if v not in G: G[v] = {}
G[v0][v1] = w
G[v1][v0] = w
with open('graph.txt','rt') as f:
for line in f:
v0, vs = line.rstrip().split(' <--> ')
for v1 in vs.split():
add_edge(v0,v1)
start = '8088'
goal = '10302'
print(' '.join(shortestPath(G, start, goal)))
我验证了解决方案存在(使用单一权重,因为 boost::print_graph 不打印权重,但它不应该是相关的):
8088 7803 7783 7759 5811 5809 5799 5796 5712 5702 5674 5666 2168 2009 1985 1967 1934 1928 1906 1900 1633 1626 1597 1617 1187 1303 1299 1319 1283 1370 1420 1448 1463 4942 4963 4969 4972 5083 5089 5100 5107 5421 5430 5443 5445 5480 5500 5528 5994 5998 6000 6001 6016 6194 6196 6198 6199 6200 6202 6204 6206 6208 6210 6212 6214 8368 8370 9790 9792 10010 10021 10026 10053 10094 10098 10110 10122 10190 10202 10302
那么为什么使用 boost 找不到解决方案和/或路径包含循环?
最佳答案
dijkstra_shortest_paths
初始化距离和前导图。您所看到的可能是顶点没有前驱的效果,因此它的前驱就是它本身。这会终止您的循环并(错误地)报告一个循环。
创建一个完全没有边的图很容易重现。
此外,我注意到您不小心将 goal
传递给了 dijkstra_shortest_paths
,而您本应传递 start
:
dijkstra_shortest_paths(gc.graph, start,
boost::weight_map(boost::get(&Edge::weight, gc.graph))
.distance_map(boost::make_iterator_property_map(distances.begin(), idmap))
.predecessor_map(boost::make_iterator_property_map(predecessors.begin(), idmap))
);
现在,最后,如果您希望边缘的权重成为该距离函数,请考虑使用距离函数:
插图更改:
rtree
而不是 octomap
(我不知道)。它有最近点查询和distance
函数weight_map()
函数closest()
、find_path()
、print()
,并添加save_dot
实现可视化random_device
以允许随机数据)int main() {
GraphContainer gc = GraphContainer::generate_random();
gc.print();
auto start = gc.closest({1,1,1}),
goal = gc.closest({10,10,10});
auto coordmap = get(&Vertex::coord, gc.graph());
std::cout << "start: " << start << " " << coordmap[start] << "\n";
std::cout << "goal: " << goal << " " << coordmap[goal] << "\n";
PathType const path = gc.find_path(start, goal);
std::cout << "Path: ";
for (auto vd : path)
std::cout << vd << " (" << coordmap[vd] << ") ";
if (path.front() != start)
std::cout << "PATH INCOMPLETE\n";
std::cout << "\n";
gc.save_dot("graph.dot", path);
}
请注意代码的整洁和结构。简单的辅助函数很简单:
#include <boost/graph/graph_utility.hpp>
void GraphContainer::print() const {
print_graph(_graph);
}
寻找最近的顶点:
VertexDesc closest(octomap::point3d const& where) const {
octomap::point3d closest[1];
size_t n = bgi::query(_tree, bgi::nearest(where, 1), closest);
assert(1 == n);
return revmap.at(*closest); // throws if missing revmap entry
}
直接从坐标寻找路径:
PathType find_path(octomap::point3d const& startPos, octomap::point3d const& goalPos) const {
return find_path(closest(startPos), closest(goalPos));
}
使用 boost::geometry::distance
实现即时计算权重:
struct Weight {
Graph const& g;
double operator()(EdgeDesc const& ed) const {
auto s = g[source(ed, g)].coord,
t = g[target(ed, g)].coord;
return bg::distance(s, t);
}
};
boost::function_property_map<Weight, EdgeDesc, double> weight_map() const {
return boost::make_function_property_map<EdgeDesc>(Weight{_graph});
}
最后,我们将图形保存为 GraphViz 格式,以便用例如渲染。 点
:
#include <boost/graph/graphviz.hpp>
void GraphContainer::save_dot(std::string const& fname, PathType const& mark) const {
boost::dynamic_properties dp;
auto idmap = boost::get(boost::vertex_index, _graph);
dp.property("node_id", idmap);
dp.property("label", weight_map());
auto emphasis = [&mark](VertexDesc vd) { return std::count(mark.begin(), mark.end(), vd); };
dp.property("color", boost::make_transform_value_property_map([=](VertexDesc vd) {
return emphasis(vd)? "red" : "black";
}, idmap));
dp.property("color", boost::make_function_property_map<EdgeDesc>([=](EdgeDesc ed) {
return emphasis(source(ed, _graph)) && emphasis(target(ed, _graph))? "red" : "black";
}));
std::ofstream ofs(fname);
write_graphviz_dp(ofs, _graph, dp);
}
它用红色
标记路径中涉及的节点/边:
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
namespace octomap {
struct point3d { double x,y,z; };
static inline std::ostream& operator<<(std::ostream& os, point3d const& pt) {
return os << "{" << pt.x << "," << pt.y << "," << pt.z << "}";
}
}
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/index/rtree.hpp>
namespace bg = boost::geometry;
BOOST_GEOMETRY_REGISTER_POINT_3D(octomap::point3d, double, bg::cs::cartesian, x, y, z)
#include <random>
static std::mt19937 s_prng { 2 }; // { std::random_device{}() };
namespace bgi = bg::index;
namespace MockupTree {
using octomap::point3d;
using Tree = bgi::rtree<point3d, bgi::rstar<32> >;
Tree generate_random() {
std::uniform_real_distribution<double> dist(-5, 5);
auto gen = [&] { return point3d { dist(s_prng), dist(s_prng), dist(s_prng) }; };
Tree tree;
for (auto i = 0; i < 10; ++i)
tree.insert(gen());
return tree;
}
}
using Tree = MockupTree::Tree;
using OcTreeNode = const Tree::value_type;
struct Vertex {
octomap::point3d coord;
OcTreeNode *node;
};
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, Vertex> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor VertexDesc;
typedef boost::graph_traits<Graph>::edge_descriptor EdgeDesc;
typedef boost::graph_traits<Graph>::vertex_iterator VertexIter;
typedef boost::graph_traits<Graph>::edge_iterator EdgeIter;
using PathType = std::vector<VertexDesc>;
class GraphContainer {
private:
GraphContainer() = default;
public:
static GraphContainer generate_random() {
GraphContainer result;
result._tree = MockupTree::generate_random();
auto& g = result._graph;
// add all the vertices (also in revmap)
for (auto& pt : result._tree) {
VertexDesc vd = add_vertex(Vertex{ pt, nullptr }, g);
auto insertion = result.revmap.emplace(pt, vd);
assert(insertion.second); // no duplicate points please
}
// add random part of edges
std::discrete_distribution<> p({50, 10}); // 1 out of 6
for (auto from : boost::make_iterator_range(vertices(g)))
for (auto to : boost::make_iterator_range(vertices(g))) {
if (from != to && p(s_prng)) {
auto e = boost::edge(from, to, g);
if (!e.second) // edge didn't exist yet
add_edge(from, to, g);
}
}
return result;
}
Graph const& graph() const { return _graph; }
VertexDesc closest(octomap::point3d const& where) const {
octomap::point3d closest[1];
size_t n = bgi::query(_tree, bgi::nearest(where, 1), closest);
assert(1 == n);
return revmap.at(*closest); // throws if missing revmap entry
}
PathType find_path(octomap::point3d const& startPos, octomap::point3d const& goalPos) const {
return find_path(closest(startPos), closest(goalPos));
}
PathType find_path(VertexDesc start, VertexDesc goal) const {
auto idmap = boost::get(boost::vertex_index, _graph);
std::vector<VertexDesc> predecessors(boost::num_vertices(_graph), _graph.null_vertex());
std::vector<int> distances(boost::num_vertices(_graph));
dijkstra_shortest_paths(_graph, start,
boost::weight_map(weight_map())
.distance_map(boost::make_iterator_property_map(distances.begin(), idmap))
.predecessor_map(boost::make_iterator_property_map(predecessors.begin(), idmap))
);
// extract path
VertexDesc current = goal;
PathType path { current };
do {
auto const pred = predecessors.at(current);
//std::cout << "extract path: " << current << " " << _graph[current].coord << " <- " << pred << std::endl;
if(current == pred)
break;
current = pred;
path.push_back(current);
} while(current != start);
std::reverse(path.begin(), path.end());
return path;
}
struct Weight {
Graph const& g;
double operator()(EdgeDesc const& ed) const {
auto s = g[source(ed, g)].coord,
t = g[target(ed, g)].coord;
return bg::distance(s, t);
}
};
boost::function_property_map<Weight, EdgeDesc, double> weight_map() const {
return boost::make_function_property_map<EdgeDesc>(Weight{_graph});
}
void print() const;
void save_dot(std::string const& fname, PathType const& emphasize = {}) const;
private:
Tree _tree;
Graph _graph;
//std::map<OcTreeNode*, VertexDesc> revmap;
struct PointCompare {
bool operator()(octomap::point3d const& a, octomap::point3d const& b) const {
return std::tie(a.x, a.y, a.z) < std::tie(b.x, b.y, b.z);
}
};
std::map<octomap::point3d, VertexDesc, PointCompare> revmap;
};
#include <boost/graph/graph_utility.hpp>
void GraphContainer::print() const {
print_graph(_graph);
}
#include <boost/graph/graphviz.hpp>
void GraphContainer::save_dot(std::string const& fname, PathType const& mark) const {
boost::dynamic_properties dp;
auto idmap = boost::get(boost::vertex_index, _graph);
dp.property("node_id", idmap);
dp.property("label", weight_map());
auto emphasis = [&mark](VertexDesc vd) { return std::count(mark.begin(), mark.end(), vd); };
dp.property("color", boost::make_transform_value_property_map([=](VertexDesc vd) {
return emphasis(vd)? "red" : "black";
}, idmap));
dp.property("color", boost::make_function_property_map<EdgeDesc>([=](EdgeDesc ed) {
return emphasis(source(ed, _graph)) && emphasis(target(ed, _graph))? "red" : "black";
}));
std::ofstream ofs(fname);
write_graphviz_dp(ofs, _graph, dp);
}
int main() {
GraphContainer gc = GraphContainer::generate_random();
gc.print();
auto start = gc.closest({1,1,1}),
goal = gc.closest({10,10,10});
auto coordmap = get(&Vertex::coord, gc.graph());
std::cout << "start: " << start << " " << coordmap[start] << "\n";
std::cout << "goal: " << goal << " " << coordmap[goal] << "\n";
PathType const path = gc.find_path(start, goal);
std::cout << "Path: ";
for (auto vd : path)
std::cout << vd << " (" << coordmap[vd] << ") ";
if (path.front() != start)
std::cout << "PATH INCOMPLETE\n";
std::cout << "\n";
gc.save_dot("graph.dot", path);
}
控制台输出:
0 <--> 7 1 3 6 9
1 <--> 0 4 3 9
2 <--> 4 7 9
3 <--> 0 1 7
4 <--> 1 2 5 9
5 <--> 4 6 9
6 <--> 5 0 7 9
7 <--> 0 3 6 2
8 <--> 9
9 <--> 4 6 8 0 1 2 5
start: 4 {-0.0143883,0.86797,2.19754}
goal: 3 {1.32738,3.18227,1.83026}
Path: 4 ({-0.0143883,0.86797,2.19754}) 1 ({-0.152509,-1.79464,-3.45573}) 3 ({1.32738,3.18227,1.83026})
graph.dot
中的 Graphviz 输出:
graph G {
0 [color=black];
1 [color=red];
2 [color=black];
3 [color=red];
4 [color=red];
5 [color=black];
6 [color=black];
7 [color=black];
8 [color=black];
9 [color=black];
0--7 [color=black, label=11.2344];
1--0 [color=black, label=10.4521];
1--4 [color=red, label=6.25045];
2--4 [color=black, label=5.59547];
3--0 [color=black, label=5.32263];
3--1 [color=red, label=7.40954];
3--7 [color=black, label=9.29024];
4--5 [color=black, label=3.96107];
4--9 [color=black, label=6.14037];
5--6 [color=black, label=4.45081];
6--0 [color=black, label=6.51876];
6--7 [color=black, label=8.683];
6--9 [color=black, label=7.2063];
7--2 [color=black, label=5.10893];
8--9 [color=black, label=2.78728];
9--0 [color=black, label=10.3583];
9--1 [color=black, label=3.8217];
9--2 [color=black, label=5.60891];
9--5 [color=black, label=5.63377];
}
关于python - boost dijkstra_shortest_paths : can't extract (or find? ) 路径(路径包含一个循环),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48367649/
我对这个错误很困惑: Cannot implicitly convert type 'System.Func [c:\Program Files (x86)\Reference Assemblies\
考虑这段代码: pub trait Hello { fn hello(&self); } impl Hello for Any { fn hello(&self) {
问题很简单。是否可以构造这样一个类型 T,对于它下面的两个变量声明会产生不同的结果? T t1 = {}; T t2{}; 我已经研究 cppreference 和标准一个多小时了,我了解以下内容:
Intellij idea 给我这个错误:“Compare (T, T) in Comparator cannot be applied to (T, T)” 对于以下代码: public class
任何人都可以告诉我 : n\t\t\t\t\n\t\t\t 在以下来自和 dwr 服务的响应中的含义和用途是什么. \r\n\t\t\t \r\n\t\t\t
让 T 成为一个 C++ 类。 下面三个指令在行为上有什么区别吗? T a; T a(); T a = T(); T 为不带参数的构造函数提供了显式定义这一事实是否对问题有任何改变? 后续问题:如果
Rust中的智能指针是什么 智能指针(smart pointers)是一类数据结构,是拥有数据所有权和额外功能的指针。是指针的进一步发展 指针(pointer)是一个包含内存地
比如我有一个 vector vector > v={{true,1},{true,2},{false,3},{false,4},{false,5},{true,6},{false,7},{true,8
我有一个来自 .xls 电子表格的数据框,我打印了 print(df.columns.values) 列,输出包含一个名为:Poll Responses\n\t\t\t\t\t。 我查看了 Excel
This question already has answers here: What are good reasons for choosing invariance in an API like
指针类型作为类型前缀与在类型前加斜杠作为后缀有什么区别。斜线到底是什么意思? 最佳答案 语法 T/~ 和 T/& 基本上已被弃用(我什至不确定编译器是否仍然接受它)。在向新向量方案过渡的初始阶段,[T
我正在尝试找到一种方法来获取模板参数的基类。 考虑以下类: template class Foo { public: Foo(){}; ~Foo(){};
这是一个让我感到困惑的小问题。我不知道如何描述它,所以只看下面的代码: struct B { B() {} B(B&) { std::cout ::value #include
为什么有 T::T(T&) 而 T::T(const T&) 更适合 copy ? (大概是用来实现move语义的???) 原始描述(被melpomene证明是错误的): 在C++11中,支持了一种新
在 Java 7 中使用 eclipse 4.2 并尝试实现 List 接口(interface)的以下方法时,我收到了警告。 public T[] toArray(T[] a) { ret
假设有三个函数: def foo[T](a:T, b:T): T = a def test1 = foo(1, "2") def test2 = foo(List(), ListBuffer()) 虽
我对柯里化(Currying)和非柯里化(Currying)泛型函数之间类型检查的差异有点困惑: scala> def x[T](a: T, b: T) = (a == b) x: [T](a: T,
考虑一个类A,我如何编写一个具有与相同行为的模板 A& pretty(A& x) { /* make x pretty */ return x; } A pretty(A&& x) {
Eclipse 表示由于泛型类型橡皮擦,类型参数不允许使用 instanceof 操作。 我同意在运行时不会保留任何类型信息。但是请考虑以下类的通用声明: class SomeClass{ T
在 C++14 中: 对于任何整数或枚举类型 T 以及对于任何表达式 expr: 有没有区别: struct S { T t { expr }; }; 和 struct S { T t = { exp
我是一名优秀的程序员,十分优秀!