标签: boost-graph

我有使用boost图库的C++程序.我想知道是否有任何方法可以在节点中包含的某个位置值之后可视化图形(节点和可选边).请查看下面的图像示例,以了解我想要想象的内容:http: //img11.hostingpics.net/pics/647608graphViz.png

谢谢.

我在C++模板上生锈了,我正在使用boost图库(致命的组合).我在网上搜索过,找不到关于如何采用自定义图形结构的任何直接指令,并且足够适合BGL(boost图形库),我可以使用增强图遍历算法.有没有熟悉图书馆帮助我的人？

编辑:所以,我一直遇到的主要问题是在哪里找到一个源,其中将任意图映射到BGL图的总要求.我是模板的新手,所以我很难阅读BGL的规范/示例.也许我应该寻找模板的一般来源？

我想用纯C++ 11等效替换顶点或边上的BGL迭代.BGL代码(来自:http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/quick_tour.html)是:

typename boost::graph_traits<Graph>::out_edge_iterator out_i, out_end;
typename boost::graph_traits<Graph>::edge_descriptor e;
for (std::tie(out_i, out_end) = out_edges(v, g);
     out_i != out_end; ++out_i)
{
  e = *out_i;
  Vertex src = source(e, g), targ = target(e, g);
  std::cout << "(" << name[get(vertex_id, src)]
            << "," << name[get(vertex_id, targ)] << ") ";
}

我从这里尝试了几个建议:用"纯"C++ 11替换替换BOOST_FOREACH？但没有运气.

我希望能够写出如下内容:

for (auto &e : out_edges(v, g))
{ ... }

或类似的东西:

for (std::tie(auto out_i, auto out_end) = out_edges(v, g);
     out_i != out_end; ++out_i)
{...}

可能吗？

我正广泛使用adjacency_list <vecS,vecS,bidirectionalS ...>.我有很多图表一次加载,内存成为一个问题.我正在进行静态程序分析,并将反汇编二进制文件的调用图和流程图存储在boost图中.因此,我可以拥有几万个函数== flowgraphs和一个巨大的调用图.我还是希望在使用BGL的同时减少图形的内存使用量.

由于我的图形在加载后是静态的,并且预先知道边缘和顶点计数,因此我看到了巨大的优化潜力.例如,我想为单个图的所有顶点/边分配一个缓冲区,让图只将索引存储到该缓冲区中.

更多问题:
1)使用顶点和边缘属性的内存开销是多少？我有很多.
2)是否有可能说服BGL使用收缩来拟合成语？据我所知,邻接列表使用push_back来添加边.是否可以通过将结果向量与自身副本交换来减少内存使用量？也许通过复制整个图表？
3)是否可以将升压池分配器与BGL一起使用？据我所知,BGL目前执行大量的小分配 - 我真的希望避免出于空间和运行时效率的原因.

有没有人已经构建了针对内存使用优化的BGL版本？我应该尝试使用现有的图形结构并使用自定义分配器或其他类似的增加它,或者编写我自己的实现并尝试保持与BGL的接口兼容性更有成效,以便我可以继续使用它的算法？

最好的祝福,

Sören

假设我找到符合我标准的节点,我需要停止搜索.

也许这是一个愚蠢的问题,但我正在尝试使用BGL dijkstra_shortest_paths,特别是使用我的Edge捆绑属性的字段作为权重图.我的尝试目前导致了数十页的编译器错误,所以我希望有人知道如何帮助我.这基本上就是我的代码:

struct GraphEdge {
    float length;
    // other cruft
};
struct GraphVertex {
    ...
};
typedef boost::adjacency_list
<boost::vecS, boost::vecS, boost::directedS,
 GraphVertex, GraphEdge> GraphType;

我可以毫无问题地填充图表,但是当涉及到呼叫时dijkstra_shortest_paths,我遇到了麻烦.我想用这个length领域.具体来说,我想知道在这样的通话中需要什么样的增强伏都教才能适应:

GraphType m_graph;

vector<int> predecessor(num_vertices(m_graph));
vector<float> distances(num_vertices(m_graph), 0.0f);
vector<int> vertex_index_map(num_vertices(m_graph));
for (size_t i=0; i<vertex_index_map.size(); ++i) {
    vertex_index_map[i] = i;
}

dijkstra_shortest_paths(m_graph, vertex_from, predecessor, distances, 
                        weightmap, vertex_index_map, 
                        std::less<float>(), closed_plus<float>(), 
                        (std::numeric_limits<float>::max)(), 0.0f,
                        default_dijkstra_visitor());
// How do I write the right version of weightmap here?

这样,weightmap会以某种方式将我的图形的特定边缘与length属性中的相应字段相关联.我确信有一种简单的方法可以做到这一点,但BGL的文档对我来说是非常不透明的.如果您可以告诉我描述示例的文档中的哪个位置,我也会非常高兴.

先感谢您!

我需要使用Boost库来获得从一个点到另一个点的最短路径.我查看了示例代码,它很容易理解.但是,该示例仅显示如何获得总距离.我试图弄清楚如何迭代前任映射以实际获得最短路径,我似乎无法弄明白.我已经阅读了关于这个主题的这两个问题:

具有VertexList的Dijkstra最短路径=增强图中的ListS

Boost :: Dijkstra Shortest Path,如何从路径迭代器获取顶点索引？

但是在提供的两个示例中,IndexMap typedef似乎不能与Visual Studio编译器一起使用,坦率地说,Boost typedef对我来说有点混乱,我在解决所有这些问题时遇到了一些麻烦.根据这里的Boost示例代码,有人能告诉我如何才能找到它的路径吗？我会非常感激.

http://www.boost.org/doc/libs/1_46_1/libs/graph/example/dijkstra-example.cpp

有向图和无向图的数据结构具有根本重要性.公知和广泛使用的实现方式中,如Boost图库和柠檬被设计为使得节点和边的连续整数索引不暴露于经由接口用户.

相反,用户通过(小)代表对象识别节点和边缘.一个优点是当节点和边缘的索引由于从图形中移除边缘或节点而改变时,这些对象被自动更新.

在我看来(!),这个优势被高估了.用户通常将节点和/或边缘的代表性对象存储在容器中,例如,std::vector.现在,如果从图形中移除节点或边缘并且它们的代表对象变得无效,则用户需要忽略该向量或重新排列向量以便保持有效的整数索引连续,即,完全执行设计所应的簿记.做不必要的.

因此,我的问题是:设计选择(隐藏用户的节点和边缘的连续整数索引)是否还有其他优点？

我正在从Python(networkx)和C++(BGL)中移植一些图形代码.在我的Python代码中,图的顶点和边是实现已建立接口的客户端定义的对象; 我继续在他们身上调用一堆方法.一切都好.

天真地看来,BGL似乎是为了支持具有"捆绑属性"的类似设计模式.这些基本上允许通过传递某些模板参数来定义顶点和边的自定义类型:

adjacency_list<OutEdgeList, VertexList,
               Directed, VertexProperties,
               EdgeProperties, GraphProperties,
               EdgeList>

这里的自定义顶点和边类型由VertexProperties和给出EdgeProperties.

在这个端口上工作时我注意到一些事情让我觉得BGL的捆绑属性接口实际上只是为了支持(或多或少)不可变类型:

• 边和顶点"描述符"

  如果你把某些东西放到图表中,你会得到一个"描述符",你必须用它来从那里引用它.有边和顶点的描述符,它们是图中的"键" - 实现为不可变的.因此,如果您有一个顶点并且想要找到相邻顶点,则必须(a)获取当前顶点描述符,(b)使用BGL方法查找其邻居的描述符,最后(c)引用每个邻居通过各自的描述符.

  所有这些簿记的最终结果是显然需要额外的容器 - std::map比如说 - 提供从顶点和边缘(再次,类型VertexProperty和EdgeProperty)到它们的描述符的反向查找.

• "BGL并不意味着存储指针."

  我在一个类似的SO问题中发现了这个主张,但是无法在任何地方的Boost文档中对其进行验证.从随后的讨论中我可以推测,约束实际上可能更强一些:"BGL并不意味着直接引用堆." 但这似乎并不完全合理,因为容器类型是可配置的(OutEdgeList以及VertexList上面的)和默认的标准内容,如矢量.

我是一个BGL的n00b和我无法理解有什么打算捆绑特性.(坦率地说,我觉得编程模型有点不知所措 - "属性","概念","特征","描述符",AHHHH!)问题:

1. 不要BGL图有效地支持复杂和可能堆结合的类型VertexProperty和EdgeProperty？或者这些是不可变数据的轻量级容器？

2. 如果是前者,有没有办法绕过所有描述符簿记？

3. 如果是后者,处理大型复杂事物的"正确方法"是什么,我们可能想要坚持BGL图？

即使图中没有循环,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; …