我正在使用 Boost 的图 C++ 库，在询问网格图的顶点数时我偶然发现了一个问题。
\n下面的代码片段创建了一个形状为 5 x 6 的二维网格图，然后打印该图的顶点数，即5x6 = 30。\n但是，这不会编译并出现错误：
\n\n错误：\xe2\x80\x98num_vertices\xe2\x80\x99 不是 \xe2\x80\x98boost\xe2\x80\x99 的成员
\n
#include <boost/graph/grid_graph.hpp>\n#include <iostream>\n\nint main()\n{\n typedef boost::grid_graph<2> Graph;\n Graph g({5, 6});\n std::cout << "Num vertices: " << boost::num_vertices(g) << std::endl;\n\n return 0;\n}\n如果我将代码更改为包含using namespace boost;在开头，那么它确实有效：
#include <boost/graph/grid_graph.hpp>\n#include <iostream>\n\nusing namespace boost;\n\nint main()\n{\n typedef grid_graph<2> Graph;\n Graph g({5, 6});\n std::cout << "Num vertices: " << num_vertices(g) << std::endl;\n\n return 0;\n}\n奇怪的是，当我使用不同的 Boost 图类型（例如boost::adjacency_list<>. …
我想对boost :: graph的边缘列表进行排序,如下所示:
struct Vertex{
int index;
};
struct Edge{
double weight;
};
boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, Vertex, Edge> Graph;
添加顶点和边后,如何对边列表进行排序.首先获得最高重量的边缘？
我知道可以使用
std::sort(edgeIt_begin,edgeIt_end,compare);
对于向量,但它不适用于std :: list.
我目前正在尝试定义增强图的外部属性.我使用一些捆绑属性作为内部属性:
struct VertexProperties
{
int demand;
};
struct EdgeProperties
{
uint capacity;
int cost;
};
typedef adjacency_list <vecS, vecS, bidirectionalS, VertexProperties, EdgeProperties> Graph;
然而,在算法期间我需要一些外部属性,即我希望能够将我的图形的边/顶点映射到存储在std :: vector中的元素,以便我可以通过operator [](Edge)访问它们E).我站在提升文档前面,没有任何线索.好像我需要一个property_map,但我不知道如何将这些与vector一起使用.到目前为止,我发现的唯一例子涉及从顶点到矢量的映射,但由于顶点是无符号整数,因此这是微不足道的.
到目前为止,我对提升感到非常沮丧,我认为这样可以节省我很多时间来自己实现和测试图表类,我真的没有得到这个疯狂的模板元编程的东西......
我想从图G中删除与邻居的顶点w.
我的代码:
// remove all neighbours
MyGraph::adjacency_iterator n_iter, n_end;
for (tr1::tie(n_iter, n_end) = boost::adjacent_vertices (*w, G1); n_iter != n_end; ++n_iter)
{
boost::remove_vertex(*n_iter, G1);
}
MyGraph::vertex_iterator vertex_iter, vertex_end;
Vertex vertex_w = G[*w];
// remove vertex himself
for (tr1::tie(vertex_iter, vertex_end) = boost::vertices(G1);vertex_iter != vertex_end; ++vertex_iter)
{
Vertex vertex = G1[*vertex_iter];
if (vertex.p_index == vertex_w.p_index)
{
boost::remove_vertex(*vertex_iter, G1);
break;
}
}
我试图迭代相邻的顶点并删除它们.之后,我试图删除顶点w.
但是在启动程序时出现了一些异常和错误.
有人提示我从图表中移除所有邻居并使用Vertex w吗？
更新: 现在我明白为什么上面的代码不起作用(我使用VertexList = vecS).我现在尝试将"顶点"标记为"已删除",并希望删除所有边缘.
图形:
0 1
o-----o
| |
| |
o-----o
2 3
码:
typedef boost::adjacency_list<boost::listS, …我有一个有向图(通过boost :: graph库中的adjacency_graph实现),我试图找到某个顶点的父顶点.
在过去(通过pygraph)我简单地颠倒了有向图,然后进行了邻居搜索,但似乎用boost :: reverse_graph反转图形会将我的有向图变成双向图,因此我不能使用adjacent_vertices方法了.
有没有更好的方法来获取父顶点？
谢谢.
这是我当前的示例代码:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/reverse_graph.hpp>
#include <iostream>
typedef boost::adjacency_list< boost::setS, boost::vecS, boost::directedS > Graph;
typedef boost::reverse_graph<Graph> Rgraph;
typedef Graph::vertex_descriptor Vertex;
int main()
{
Graph graph;
Vertex v0 = boost::add_vertex(graph);
Vertex v1 = boost::add_vertex(graph);
Vertex v2 = boost::add_vertex(graph);
Vertex v3 = boost::add_vertex(graph);
Vertex v4 = boost::add_vertex(graph);
Vertex v5 = boost::add_vertex(graph);
Vertex v6 = boost::add_vertex(graph);
boost::add_edge(v0,v1,graph);
boost::add_edge(v1,v2,graph);
boost::add_edge(v2,v3,graph);
boost::add_edge(v2,v4,graph);
boost::add_edge(v3,v5,graph);
boost::add_edge(v4,v5,graph);
boost::add_edge(v5,v6,graph);
Graph::adjacency_iterator ibegin, iend;
for (boost::tie(ibegin, iend) = boost::adjacent_vertices(v2, graph); ibegin != iend; …我在Boost图中遇到了Floyd Warshall(所有对最短路径)的问题.有没有办法直接提供有向加权图floyd_warshall_all_pairs_shortest_paths？看起来它的所有功能过载都需要一些我不完全理解的额外参数.以下是我正在编写的测试代码(因为我的调用floyd_warshall_all_pairs_shortest_paths不完整所以无法编译)
#include <iostream>
#include <map>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/floyd_warshall_shortest.hpp>
typedef boost::property<boost::edge_weight_t, double> EdgeWeightProperty;
typedef boost::adjacency_list<boost::vecS, boost::vecS,
boost::undirectedS, boost::no_property,
EdgeWeightProperty> Graph;
typedef unsigned long t_indx;
int main()
{
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_des;
std::map<vertex_des, std::map<vertex_des, int> > matrix;
Graph sp_graph;
int edgelet_sp[] = { 1, 2,
1, 3,
1, 4,
2, 5,
3, 4,
3, 6,
4, 5,
4, 6,
4, 7,
5, 7,
6, 7 };
double edgelet_vals[] = { 4,
10,
3,
1,
12,
20,
6, …我是新用的C++ boost库,尤其是boost图库,它需要尝试编码一些算法,我通常检查两个顶点的邻接并处理其他图形概念,如计算图形不变量.我所知道的是我们可以使用函数迭代相邻的顶点:adjacent_vertices(u, g)但是我正在寻找一种有效的方法来测试两个顶点u,v是否相邻而不进行线性搜索
我正在尝试从专有图库迁移到开源图库.
编辑:因为很少有人知道Boost Graph是如何工作的,如果你可以使用LEMON Graph Library提供解决方案,那也没关系.
目前,我的顶点具有类型,Graph_Vertex*并且可以具有void*用于存储相关信息的关联指针.对于类型的边缘使用类似的逻辑Graph_Edge*.我使用void*指针来存储我自己的结构Node_State,这是这样的
struct Node_State {
std::string name;
int id;
// other stuff
};
从我看到的BGL到现在,我可以使用adjacency_list结构和捆绑属性创建一个图表指向我的Node_State.然后,我将使用整数顶点索引,而不是使用顶点指针.
我一直在寻找的教程和一些问题 在这里,这似乎是可能的.我在想类似的东西
typedef adjacency_list < listS, vecS, bidirectionalS, Node_State> gr;
我会不时地从顶点移除所有边缘.非常不常见,我也可能删除一个节点.这就是我选择的原因listS, vecS.
我想很容易为无向边创建这个结构的第二个版本.我不确定这是否bidirectionalS是我案件的最佳选择.在这方面,您的意见是值得赞赏的.
但是还有另一个问题.现在,我可以使用外部地图按名称或使用唯一的整数id查找每个顶点.
std::map<int, Graph_Vertex*> nodes_by_id;
std::map<std::string, Graph_Vertex*> nodes_by_name();
如果我删除一个顶点,我只需要删除地图中相应的条目,并且事情继续有效.
根据我的理解,使用BGL实现这一点并不容易,因为删除顶点会触发使用更高ID 重新编号所有顶点,并且还可能导致内部结构的重新分配.再见ids和再见指针.
主要问题. …
我正在尝试重现本文中进行的实验,测量算法在DIMACS Vertex-Coloring基准图上的性能,可在此处找到.
这些图是DIMACS标准格式,我想将它们解析为C++ Boost Graph Library格式,因此我可以在它们上运行我的算法.
我尝试使用现有的Boost DIMACS函数解析它们,但是关于它们的文档相当稀疏,所以我不清楚如何使用这些函数.当我将图形打印到Graphviz时,结果似乎与DIMACS文件不匹配.
我在想:
使用Boost解析函数我做错了什么？(见下面的例子)
是否有更好的或替代的C++库可以轻松解析DIMACS标准图形格式？
这是我尝试解析和打印图形:
#include <cstdlib>
#include <iostream>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/dimacs.hpp>
#include <fstream>
using namespace boost::graph;
typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS > Graph;
typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
int main()
{
std::ifstream inGraphFile;
inGraphFile.open("myciel4.col");
dimacs_basic_reader reader(inGraphFile, false);
dimacs_basic_reader end;
dimacs_edge_iterator<dimacs_basic_reader> dimacsStart(reader);
dimacs_edge_iterator<dimacs_basic_reader> endIter(end);
Graph g2(dimacsStart, endIter, reader.n_vertices());
boost::write_graphviz(std::cout, g2);
}
我想push_relabel_max_flow在Boost.Graph库中使用它.我已经生成了我的图表,这是我的代码到目前为止:
struct EdgeProps {
double capacity;
double residual_capacity;
Traits::edge_descriptor reverse;
};
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property, EdgeProps > DirectedGraph;
DirectedGraph g;
std::vector<DirectedGraph::vertex_descriptor> vertices;
/* Filling the Graph with vertices and edges and saving the vertex-descriptors in "vertices" */
//...
//...
double flow = boost::push_relabel_max_flow(g,vertices[0],vertices[1],
vertex_index_map(boost::get(boost::vertex_index, g)).
residual_capacity_map(boost::get(&EdgeProps::residual_capacity, g)).
reverse_edge_map(boost::get(&EdgeProps::reverse, g)).
capacity_map(boost::get(&EdgeProps::capacity, g))
);
传递参数时遇到问题.我得到" 形成对void的引用 " - 错误:
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2696: error: forming reference to void
typedef value_type& reference;
^
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2697: error: forming reference to void
typedef const value_type& const_reference; …