相关疑难解决方法(0)

更新:问题可能在中介代码中.如果我注释掉brandes_betweenness_centrality代码的调用将编译.问题可能不是以前认为的索引设置.如果您能够提出另一个对Brandes_betweenness_centrality的调用,我将授予赏金,这将允许将索引保持在外部.

我正在尝试将一些旧的vecS代码转换为listS,特别是brandes_betweenness_centrality算法.

我试图保持Vertex和Edge属性非常轻,并且主要使用外部属性.这样做的原因是我不知道在这一点上我想要与他们联系的是什么.

我得到的错误来自内部adjacency_list.hpp所以我认为问题出在我们的老朋友vertex_index_tlistS上.

以下代码显示了如何重现编译错误.在此工作示例中,您可以更改定义以将vertex_index填充到图形定义中,并在完整工作代码(正确运行中介性)的中介方法中更改设置.

完整的例子:

#include <iostream>
#include <algorithm>
#include <vector>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/betweenness_centrality.hpp>

#include <boost/timer.hpp>

using namespace std;

enum edge_t {A,B};

struct VertexProperties{
    std::string id;
};

struct EdgeProperties{
    edge_t type;
};

//vertex_index in as internal property, switch to this graph and change below vertex map for working code
//typedef boost::adjacency_list < boost::listS, boost::listS, boost::undirectedS,
//      boost::property<boost::vertex_index_t,size_t,VertexProperties>, EdgeProperties > DynamicNet;

// No internal vertex_index
typedef boost::adjacency_list < …

我对Boost图表很新.我试图调整一个例子来找到使用VertexList = vecS的Dijkstra最短路径算法.我将顶点容器更改为ListS.我了解到,如果我们使用listS,我们必须提供自己的vertex_index才能使算法正常工作.

int main(int, char *[])
{
  typedef float Weight;
  typedef boost::property<boost::edge_weight_t, Weight> WeightProperty;
  typedef boost::property<boost::vertex_name_t, std::string> NameProperty;
  typedef boost::property<boost::vertex_index_t, int> IndexProperty;

  typedef boost::adjacency_list < boost::listS, boost::listS, boost::directedS,
  NameProperty, WeightProperty > Graph;

  typedef boost::graph_traits < Graph >::vertex_descriptor Vertex;
  typedef boost::graph_traits <Graph>::vertex_iterator Viter;

  typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap;
  typedef boost::property_map < Graph, boost::vertex_name_t >::type NameMap;

  typedef boost::iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& > PredecessorMap;
  typedef boost::iterator_property_map < Weight*, IndexMap, Weight, Weight& > DistanceMap;

  Graph g;


  Vertex v0 = …

我有一个图表(adjacency_list(listS,vecS,bidirectionalS,VertexVal)),我需要删除100,000多个节点.每个节点还包含2个64位整数和另一个64位整数的结构.下面代码中发生的guid检查是检查结构中的第一个整数.

根据VTune,在我的笔记本电脑(i7 2.7GHz,16GB RAM)上大约需要88秒.

以下是我删除节点的方法:

  vertex_iterator vi,vi_end;
  boost::tie(vi, vi_end) = boost::vertices(m_graph);
  while (vi!=vi_end) {
    if (m_graph[*vi].guid.part1 == 0) {
      boost::remove_vertex(*vi,m_graph);
      boost::tie(vi, vi_end) = boost::vertices(m_graph);
    } else 
      ++vi;
  }

Vtune显示boost :: remove_vertex()调用需要88.145秒.有没有更有效的方法来删除这些顶点？

我正在尝试从专有图库迁移到开源图库.

编辑:因为很少有人知道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和再见指针.

主要问题. …