标签: boost-graph

作为对boost图库的新手,我发现通常很难弄清楚哪些示例与特定示例相关联以及哪些部分对于使用是通用的.

作为练习,我正在尝试制作一个简单的图形,为顶点指定颜色属性,并将结果输出到graphviz,因此颜色显示为渲染的颜色属性.任何帮助,将不胜感激!这是我到目前为止(更具体的使用问题在这里的评论):

#include "fstream"
#include "boost/graph/graphviz.hpp"
#include "boost/graph/adjacency_list.hpp"

struct vertex_info { 
    int color; 
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, vertex_info> Graph;
typedef std::pair<int, int> Edge;

int main(void) {
  Graph g;
  add_edge(0, 1, g);
  add_edge(1, 2, g);

  // replace this with some traversing and assigning of colors to the 3 vertices  ...
  // should I use bundled properties for this?
  // it's unclear how I would get write_graphviz to recognize a bundled property as the color attribute
  g[0].color = 1; 

  std::ofstream outf("min.gv"); …

即使图中没有循环,BGL的depth_first_search算法有时会对访问者调用back_edge().根据后沿的定义,根据Boost的DFS访客文档,这不应该发生.请注意,仅当listS用作顶点和边的表示时,这才是可重现的.

下面的代码示例(应该按原样编译)构造一个包含两个节点和一个边的图.它错误地打印"后边缘".我在这里做错了吗？或者这是一个错误？

#include <iostream>
using namespace std;

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/visitors.hpp>
using namespace boost;

typedef boost::property<boost::vertex_index_t,std::size_t> VertexProperties;
typedef boost::adjacency_list<boost::listS,
                              boost::listS,
                              boost::bidirectionalS,
                              VertexProperties> Graph;  // Graph object type

typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::graph_traits<Graph>::edge_descriptor Edge;

class VisitorClass : public dfs_visitor<> {
 public:
  VisitorClass() {}

  template <typename Edge, typename Graph>
  void back_edge(Edge, const Graph&) const {
    cout << "back edge" << endl;
  }
};

int
main() {
  Graph g;
  Vertex v = add_vertex(g);
  Vertex u = add_vertex(g);

  bool inserted; …

我正在使用增强图库并尝试初始化a MutableGraph以网格开始生活.边缘将在以后的生活中添加和删除,所以我认为adjacency_list<vecS,listS,undirectedS>是正确的选择.

我对BGL的阅读表明,用这些边缘初始化它的合理方法boost::grid_graph是利用 boost::copy_graph从一个boost::grid_graph可以为我免费制作所有初始边缘的复制.我认为这是有道理的 - copy_graph从模型VertexListGraph到模型的复制MutableGraph,这正是我所拥有的.

我最初尝试使用2参数版本copy_graph,模糊地希望其余的默认值会发生一些明智的事情.结果并非如此grid_graph(由于我无法弄清楚的原因)似乎没有使用PropertyMap带边或顶点的s 的工具,所以默认vertex_copy和edge_copy失败(带有编译器错误)复制属性.

由于2参数版本显然不合适,我继续尝试实现我自己的二元运算符来复制顶点和边.即使使用"无操作"副本,这也不如我希望的那样好(即它不会编译).

我已经汇总了一个说明问题的最小工作示例:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/grid_graph.hpp>
#include <boost/graph/copy.hpp>

struct Position {
  int x, y;
};

struct VertexProperties {
  Position pos;
};

typedef boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS, 
                      VertexProperties> Graph;

struct MyCopy {
  template <typename S, typename D>
  void operator()(const S& /*src*/, D& /*dest*/) {
    // Nothing for now, deduced types to …

我有一个增强图,每个边都有多个权重(想象一天中每小时一组权重).这些权重值中的每一个都存储在propretyEdge类中:

class propretyEdge {
    std::map<std::string,double> weights; // Date indexed 
}

我创建了一个包含这些属性的图形,然后用正确的值填充它.现在的问题是我想在图上的特定权重集上启动Dijkstra算法:例如,一个函数可能是:

void Dijkstra (string date, parameters ... )

那将使用

weights[date]

图的每个边的值.

我一遍又一遍地阅读文档,我无法清楚地知道自己要做什么.我当然需要写这样的东西,但我不知道要开始:

boost::dijkstra_shortest_paths (
    (*graph_m), 
    vertex_origin_num_l,
    // weight_map (get (edge_weight, (*graph_m)))
    // predecessor_map(boost::make_iterator_property_map(predecessors.begin(), get(boost::vertex_index, (*graph_m)))).
    // distance_map(boost::make_iterator_property_map(distances.begin (), get(vertex_index,(*graph_m) )))
    predecessor_map(predecessorMap).
    distance_map(distanceMap)
);

谢谢您的帮助.

编辑

感谢Sehe精彩的回答,我能够在MacOS和Ubuntu上做到我想要的.

但是当我们尝试在Visual Studio 2012上编译这段代码时,似乎VS并不是很擅长理解boost的指针功能.所以我们修改了Sehe的部分:

auto dated_weight_f = [&](Graph::edge_descriptor ed) {
    return g[ed].weights.at(date);
};

auto dated_weight_map = make_function_property_map<Graph::edge_descriptor, double>(dated_weight_f);

通过:

class dated_weight_f {
public:
  dated_weight_f(Graph* graph_p,std::string date_p){
    graph_m=graph_p;
    date_m=date_p;
  }
  typedef double …

考虑这段代码(或实例):

#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/range/iterator_range.hpp>

using std::cout;

int main() {
  boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> g;

  add_edge(0, 1, g);
  add_edge(1, 2, g);

  for(auto v : make_iterator_range(vertices(g))) {
    cout << v << " has " << degree(v, g) << " neighbor(s): ";
    for(auto w : make_iterator_range(adjacent_vertices(v, g))) cout << w << ' ';
    cout << '\n';
  }
  return 0;
}

为什么功能add_edge,make_iterator_range,vertices,degree和adjacent_vertices那来自无Boost库工作boost::空间前缀？

对我来说最令人费解的是,根据具体情况,有时需要前缀.下面是一个示例,当使用不同的图形结构时,会产生可以通过前缀修复的编译错误boost::make_iterator_range.

我看了一下 …

有人在那里使用BGL用于大型生产服务器吗？

• 您的网络包含多少个节点？
• 你如何处理社区检测
• BGL有没有很酷的方法来检测社区？
• 有时两个社区可能通过一条或两条边连接在一起,但这些边缘不可靠并且可能逐渐消失.有时根本没有边缘.

有人可以简单地谈谈如何解决这个问题.请敞开心扉,激励我.

到目前为止,我已经设法解决了两个节点是否在岛上(在社区中)以最昂贵的方式,但现在我需要弄清楚不同岛上的哪两个节点彼此最接近.我们只能极少使用不可靠的地理数据.

如果我们比喻它与大陆和岛屿比较,并把它从社会距离背景中拿出来.我想弄清楚哪两块土地最接近水体.

我目前正在查看Boost Dijkstra的文档 - http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/dijkstra_shortest_paths.html ; 我的目标是在计算距离时修改距离组合以获得"最大"而不是"加".医生说这个:

IN: distance_combine(CombineFunction cmb)
This function is used to combine distances to compute the distance of a path. The
CombineFunction type must be a model of Binary Function. The first argument typ
of the binary function must match the value type of the DistanceMap property map
and the second argument type must match the value type of the WeightMap property
map. The result type must be the same type as the distance value type.
Default: …

我有一个图像,保存分割结果,就像这个.

我需要建立一个贴片附近的图表,用不同的颜色着色.因此,我想要一个结构,代表以下内容

这里的数字表示单独的补丁,而线条表示补丁的邻域.目前我无法弄清楚从哪里开始,谷歌的关键词.

有人可以提出任何有用的建

图像存储在OpenCV的cv :: Mat类中,对于图形,我打算使用Boost.Graph库.

所以,请给我一些代码示例和算法或关键字的链接.

谢谢.

更新.在喝咖啡休息和一些讨论后,我想到了以下几点.

1. 构建一个大的点阵图,其中每个节点对应于每个图像像素,链接连接8或4个邻居.
2. 使用相应的像素值标记每个图形节点.
3. 尝试以某种方式合并具有相同标签的节点.

我的另一个问题是我不熟悉BGL(但这本书已经开始了:)).

那么,您对此解决方案有何看法？

Update2 可能这个链接可以提供帮助.

但是,仍然没有找到解决方案.

我在编译一个非常简单的图表的BFS时遇到了问题.无论我做什么,我得到了关于不匹配的方法调用的各种编译器消息(我已尝试boost::visitor和扩展boost::default_bfs_visitor等)

#include <stdint.h>
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

int main() {
  typedef boost::adjacency_list<boost::vecS, boost::hash_setS, boost::undirectedS, uint32_t, uint32_t, boost::no_property> graph_t;
  graph_t graph(4);
  graph_t::vertex_descriptor a = boost::vertex(0, graph);
  graph_t::vertex_descriptor b = boost::vertex(1, graph);
  graph_t::vertex_descriptor c = boost::vertex(2, graph);
  graph_t::vertex_descriptor d = boost::vertex(3, graph);
  graph[a] = 0;
  graph[b] = 1;
  graph[c] = 2;
  graph[d] = 3;
  std::pair<graph_t::edge_descriptor, bool> result = boost::add_edge(a, b, 0, graph);
  result = boost::add_edge(a, c, 1, graph);
  result = boost::add_edge(c, b, 2, graph); …

一般问题

当我迈出进入 BGL 的第一步时，我很难理解为什么最小惊讶原则在这里有点被欺负。

背景

因此，经过大量的努力，我可以构建一个树图，并且我期望能够写出类似的东西

tree.dfs(visitor);

现在我知道 BGL 并不是一个面向对象的 API，我想写类似的东西是有意义的

depth_first_search(tree, visitor)

然后，由于我了解到 BGL 中没有 Tree 类，因此设计选择是使根的存在成为值属性而不是类型属性。所以我想这解释了为什么我们必须传递根描述符，比如

depth_first_search(graph_that_is_a_tree, visitor, root);

是什么让我困惑

到目前为止，我感觉我（或多或少）遵循了设计。但为了让我的代码编译，我实际上必须编写：

  auto [root, tree] = my_stuff::to_k_ary_tree<my_vertex, my_edge>(ast);

  auto indexmap = boost::get(boost::vertex_index, tree);
  auto colormap = boost::make_vector_property_map<boost::default_color_type>(indexmap);

  MyVisitor<my_stuff::k_ary_tree<my_vertex,my_edge>> vis;
  std::vector<boost::default_color_type> colors(num_vertices(tree));
  boost::depth_first_search(tree, vis, colormap, root);

这就是我失去它的地方（直觉）：即使我被警告​​大多数算法都需要颜色图，我也不理解/欣赏为什么我需要这个签名。

我的问题

为什么DFS算法不能负责处理这些细节呢？

我能想到什么

• 是因为 if tree 不是一种类型吗？如果树和图之间没有类型区别，那么 DFS 就不可能知道不存在循环，因此它需要对所有情况下探索过的顶点进行着色 - 即使您绝对确定它是一个树，有根，无环。
• 如果是这样，那么它并不能完全向我解释为什么 DFS 无法在我们不知情的情况下创建/访问/销毁此颜色图。