我正在编写一个用于操作键图的库,我正在使用Boost Graph Library为我存储数据.不幸的是,我似乎无法弄清楚如何使用它来实现正确的访问者模式,因为你不能将顶点子类化 - 你必须依赖'属性'.库中提供的访问者框架似乎非常适合使用某些算法,其中顶点都是相同的类型,但存储不同的信息.在我的问题中,顶点具有不同的类型并存储不同类型的信息 - 一些顶点是电阻器,而一些是电容器等.我如何编写基于顶点属性工作的访问者模式,而不是顶点本身？
到目前为止,我唯一想到的是编写一个小类来表示一个对象的类型,该对象指向我需要获取图形信息的原始顶点.然而,这似乎非常kludgy,邪恶的工作.
我有一个带有类型边的巨大图形(即带有类型属性的边).说
typedef adjacency_list<vecS, vecS, vertex_prop, edge_prop> Graph;
边缘的"类型"是edge_prop的成员,并且具有{A,B,C,D}中的值,
我想运行宽度优先的搜索算法,只考虑类型A或B的边缘.
你会怎样？去做 ？
我的任务是在矩阵中找到从一个点到另一个点的最短路径.可以仅在这样的方向上移动(向上,向下,向左,向右).
0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0
0 0 0 1 0 1 F 0
0 1 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 S 0 1 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0
S - 起点
F - 目的地(完成)
0 - 免费细胞(我们可以穿过它们)
1 - "墙壁"(我们不能穿过它们)
很明显,广度优先搜索以最佳方式解决了这个问题.我知道Boost库提供了这个算法,但我之前没有Boost.
如何使用Boost在我的案例中进行广度优先搜索？据我所知,Boost的广度优先搜索算法仅适用于图形.我想将矩阵转换为带m*n …
我一直试图让升级图lib的dijkstra_shortest_paths编译大约一个星期,现在没有用.我试图使用外部属性映射来模板化方法所需的不同命名参数.我的图形使用顶点和边缘的捆绑属性,我已经能够成功构建图形.我会告诉你我的代码:
// vertex bundled properties
struct BusStop
{
unsigned int id; //used for creating vertex index property map
string name;
Location* pLocation;
};
// edge bundled properties:
struct Route
{
string routeName;
BusType type;
float distance;
};
这是我的图表声明:
typedef boost::adjacency_list<boost::vecS, boost::setS, boost::undirectedS, BusStop, Route> BusRouteGraph;
这是我尝试在给定图形上执行dijkstra最短路径的方法:
template<typename Graph>
bool shortestPathSearch(Graph& g, typename
boost::graph_traits<Graph>::vertex_descriptor src,
typename boost::graph_traits<Graph>::vertex_descriptor dest)
{
bool bPathFound = false;
VertexIndexMap index_map = get(&BusStop::id, g);
// Initialize index_map
typedef typename graph_traits<Graph>::vertex_iterator V_Iter;
V_Iter v_iter, v_iter_end;
int c = …我在使用原始图中的相同组件过滤子图时遇到问题.我想在子图的向量中输出它们.按照`connected_components中的例子,我试图让它适应我的需要:
// Create a typedef for the Graph type
typedef adjacency_list<
vecS,
vecS,
undirectedS,
property<vertex_index_t,int >,
property<edge_index_t,int> > Graph;
//typedef subgraph < Graph > SubGraph;
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::edge_descriptor Edge;
typedef graph_traits<Graph> GraphTraits;
// Iterators
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
typedef graph_traits<Graph>::edge_iterator edge_iter;
typedef property_map<Graph, vertex_index_t>::type VertexIndexMap;
typedef property_map<Graph, edge_index_t>::type EdgeIndexMap;
std::vector<Graph> connected_components_subgraphs(const Graph &g)
{
std::vector<int> component(num_vertices(g));
int num = boost::connected_components(g, &component[0]);
for (int i=0; i<component.size(); i++)
cout << component[i] << endl;
cout << "NUM=" << num << …我有我的自定义顶点和边属性
namespace boost {
enum vertex_diagonal_t{vertex_diagonal = 999};
BOOST_INSTALL_PROPERTY(vertex, diagonal);
}
namespace boost {
enum edge_dominance_t{edge_dominance = 998};
BOOST_INSTALL_PROPERTY(edge, dominance);
}
我创建我的邻接列表 boost::property
typedef boost::adjacency_list<
boost::listS,
boost::vecS,
boost::bidirectionalS,
boost::property<boost::vertex_diagonal_t, const khut::diagonal*>,
boost::property<boost::edge_dominance_t, float>
> diagonal_dominance_graph;
typedef boost::property_map<diagonal_dominance_graph, boost::vertex_diagonal_t>::type diagonal_map_type;
typedef boost::property_map<diagonal_dominance_graph, boost::edge_dominance_t>::type dominance_map_type;
现在我想遍历我自己的容器并添加顶点
diagonal_dominance_graph graph;
for(storage_type::const_iterator i = repo_begining.begin(); i != repo_begining.end(); ++i){
diagonal_dominance_graph::vertex_descriptor dia_vertex = boost::add_vertex(graph);
//>> ?? HOW CAN I write Properties to dia_vertex HERE ?
//boost::property<boost::vertex_diagonal_t, const khut::diagonal*> p;
//boost::put(p, dia_vertex);
}
我没有得到的是如何通过vertex_descriptor. 可能是我缺少一个简单的功能。 …
我正在尝试使用 OpenMP 并行迭代我的 boost 图的顶点。这似乎需要一个支持随机访问元素的迭代器（例如，itr[i]获取第ith 个元素）。但是，vertices(g)返回 (a vertex_iterator)的迭代器似乎不支持这一点。有没有一种高效、干净的方法来实现这一目标？理想情况下，我只想要一个循环标准，例如：
for (int i = 0; i < num_vertices; i++) {
vertex v = itr[i];
// Compute on vertex
}
它将与 OpenMP 合作。谢谢！
我正在使用Boost Graph Libraries并且需要使用不是常数的weightmap,但它是参数K的函数(即边缘成本取决于K).在实践中,给出以下代码:
#include <boost/config.hpp>
#include <iostream>
#include <fstream>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/adjacency_list.hpp>
struct Edge {
Edge(float weight_) : weight(weight_) {}
float weight;
float getWeight(int K)
{
return K*weight;
}
};
int main(int, char**){
typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS, boost::no_property, Edge > graph_t;
typedef boost::graph_traits < graph_t >::vertex_descriptor vertex_t;
graph_t g;
vertex_t a = boost::add_vertex(g);
vertex_t b = boost::add_vertex(g);
vertex_t c = boost::add_vertex(g);
vertex_t d = boost::add_vertex(g);
boost::add_edge(a, b, Edge(3), g);
boost::add_edge(b, c, Edge(3), g);
boost::add_edge(a, d, …有没有办法检查使用Boost创建的图形中的顶点是否已经存在，而不是遍历这些顶点？
如果已经存在，如何使用其顶点描述符添加新边？
例：
Graph g;
vertex v;
v = add_vertex(1, g);
vertex_name[v] = "root";
v = add_vertex(2, g);
vertex_name[v] = "vert_2";
v = add_vertex(3, g);
vertex_name[v] = "vert_3";
// This is not possible
edge e1;
if (vertex.find("root") == vertex.end()) {
(boost::add_edge("root", "vert_2", g)).first
}
我有这样的自定义数据结构：
vector<myVertex *> my_vertices;
vector<myEdge *> my_edges;
我的类 myEdge 有 source() 和 target() 方法，返回 myVertex*，所以它应该已经准备好了，对吧？
我需要做哪些外部调整才能将 BGL 图与我的容器一起使用？我知道文档中的适配器示例，但非常感谢您的帮助！
我感兴趣的是纯粹的 adjacency_list 基本图类型，不确定我需要的图遍历概念。
到目前为止我对 adjacency_list 参数的理解：
adjacency_list<OutEdgeListS, VertexListS, DirectedS,
VertexProperty, EdgeProperty, GraphProperty, EdgeListS>
OutEdgeListS和VertexListS是容器的选择器，用于表示（1）每个顶点的边列表，以及（2）顶点列表。这些容器分别作为元素 vertex_descriptor和edge_descriptor。我的容器类型是简单的 std::vector，所以我想我不需要像 example/container_gen.cpp 那样创建新的容器类型。我必须简单地精确，可能使用 graph_traits，我的容器元素的类型是指向对象的指针。VertexProperty并且EdgeProperty旨在用作附加信息的内部大容量存储，例如颜色标签、边缘权重……并且几年来提供捆绑属性功能。我希望顶点和边描述符不是默认为整数，而是指向我的对象的指针。BGL 文档明确指出，这在本书的 2002 版12.1.2 中是可行的：
面向对象的图实现可能使用指向堆分配顶点对象的指针。对于图特征类，这些差异被顶点描述符关联类型隐藏。
虽然它似乎已经从当前的 1.70 在线文档中消失了。
理想情况下，我想像这样初始化：
MyGraph g(const& my_edges,const& my_vertices,
undirected_tag, some_color, someweights, allow_parallel_edges_tag);
PS我对在property_map中填充对象指针不感兴趣。我愿意不使用“默认 vecS”，这是一个 std::vector，其中描述符是一个整数。我愿意使用“自定义 vecS”作为对象指针的 std::vector …