标签: boost-graph

我正在调查使用boost图库,以便将它们应用到我想到的各种网络问题中.

在示例中,我一直在查看图形边缘值("权重")总是初始化为整数,例如在这些Bellman-Ford和Kruskal算法中,例如:

int weights[] = { 1, 1, 2, 7, 3, 1, 1, 1 };

我的问题是,如果我尝试将权重更改为加倍,我会得到一堆关于转换等的警告消息,到目前为止,我还无法弄清楚如何克服.

有没有人看到这个方法？

只是想让我了解Boost Graph库，我有几个问题。我正在写一些代码，它是围绕BGL图的包装器类。我的想法是，我可以随意操作图形，然后调用包装器方法以GEXF（XML）格式输出图形。

我的代码是这样的：

struct Vertex {
   std::string label;
   ...
};

struct Edge {
   std::string label;
   double weight;
   ...
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Vertex, Edge> GraphType;

template <typename Graph>
class GEXF
{
   private:
      Graph graph;
   ...
};

template <typename Graph>
void GEXF<Graph>::buildXML()
{
   ...

   // output the edges
   property_map<adjacency_list<>, edge_index_t>::type edge_id = get(edge_index, graph);
   GraphType::edge_iterator e, e_end;
   for(tie(e, e_end) = edges(graph); e != e_end; ++e)
   {
      xmlpp::Element *edge = ePtr->add_child("edge");

      // next line gives an error, property not found
      edge->set_attribute("id", …

我希望所有的边缘都具有属性,重量和容量.我发现BGL已经定义了这两个.所以我为Graph定义了Edge和Vertex属性

 typedef property<vertex_name_t, string> VertexProperty;
 typedef property<edge_weight_t, int, property<edge_capacity_t, int> > EdgeProperty;
 typedef adjacency_list<listS,vecS, undirectedS, VertexProperty, EdgeProperty > Graph;

这是我尝试将边添加到图中的位置:

172: EdgeProperty prop = (weight, capacity);
173: add_edge(vertex1,vertex2, prop, g);

如果我只有一个属性,我知道它将是prop = 5; 但是,有两个我对格式化感到困惑.

这是我收到的错误:

graph.cc: In function ‘void con_graph()’:
graph.cc:172: warning: left-hand operand of comma has no effect

我在一个部分(？)隐式的图上运行astar算法 - 它是从一个大的分页数据源构建的,但是图是持久的.每当astar算法到达一个未完全分页的区域时,我需要在图形的新部分处理分页 - 理想情况下,不完全启动astar搜索.

我尝试了几种解决方案,但遇到了一些障碍,我想知道我是否遗漏了一些显而易见的问题,或者只是接近问题.

我目前正在使用boost 1.45但计划升级到1.51.

首先,我尝试修改astar访问者,以便当它确定需要在新数据中进行分页时,它会调用图上的函数并加载它 - 但是,由于图是const,所以这是不可能的.我环顾四周,发现另一个问题是提升隐式图和astar_search_no_init引用了一个表示有人完成了这项工作的演示文稿,但看起来实际代码不可用.

其次,当我到达需要在更多数据中分页的地方时,我想我可以退出算法,并保存distance_map,predecessor_map和color_map的状态,以便我可以使用它们来"恢复"使用astar_search_no_init进行搜索.我不确定这是否会起作用,因为一旦我切换到使用astar_search_no_init,我看到当访问者似乎做了寻路工作时,前一个地图是空的 - 因为我使用前一个来构建路径之后访问者完成后,我需要知道访问者如何构建路径.

这是我的图表的定义以及我如何调用astar_search,如果这有帮助的话.

typedef adjacency_list<
     vecS,         
     vecS,        
     undirectedS, 
     VertexInfo,        //contains geographic location     
     EdgeInfo,          //contains weight information             
     no_property,     
     setS>            
        BoostGraph;
...
ColorMap cmap = get(vertex_color_t, myGraph);           
astar_search(
     myGraph, 
     source,
     distance_heuristic(myGraph, destination), //geometric distance heuristic
     predecessor_map(&srcPredmap[0]).
     distance_map(&distMap[0]).
     color_map(cmap).
     visitor(astar_goal_visitor<vertex_descriptor>(destination, this)). //throws an exception when it finds the goal
     weight_map(make_function_property_map<edge_descriptor>(  //copied make_function_property_map functionality from boost 1.51 since I can't upgrade just yet
        EdgeWeightAdjuster(&myGraph, weightFactors))));       //modifies edge weights based on …

如何在Boost.Graph中合并两个顶点/合约边？

我需要将边缘从顶点A移动到顶点B,并删除顶点A - 是否有任何内置函数？或者也许adjacency_list有一些特别的东西？

如果没有这样的功能 - 为什么呢？我认为这是常见的图形操作.

编辑:我知道可以手动完成,但有一些极端情况(如保留边缘属性),这就是为什么它是在库中的好候选人.

我最感兴趣的是知道Boost.Graph是否已经有了这个操作(可能有一些奇特的名字？).如果不是 - 为什么这样的原始操作/算法不在图形库中.也许我错过了一些东西,而且这种操作不是原始的或很少使用.

我不需要半生不熟的快速概念验证

我正在为一些项目使用Boost Graph库,我想在图中找到边重复的次数.例如,

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Node_Info, Edge_Info > Graph_t;  
//node_info and Edge_info are external node and edge properties (structures)

假设我有两个节点,node1和node2,它们之间有一条边(node1,node2).每个边的edge属性包含一个时间戳start,end ..并且图中可能有许多这样的边具有不同的时间戳.例如.

edge1 = (node1, node2) with start = 100, end = 200.
edge2 = (node1, node2) with start = 250, end = 400.

我知道在增强图中,给定两个顶点,我们可以使用以下内容查找图中是否存在边.

std::pair < edge_t, bool > p = boost::edge( node1, node2, myGraph );
if(p.second == 1)  cout << "edge exists!" << endl;
else cout << " does not exist " << endl;

但这可能意味着即使多个边缘存在不同的边缘属性,它也只会返回任何一个边缘 - >问题

任何人都可以建议如何在两个给定节点之间获得这样的多边？谢谢!

   int main()
   {
   using namespace std;
   using namespace boost;
   typedef adjacency_list< listS, vecS, directedS > digraph;

   // instantiate a digraph object with 8 vertices
   digraph g;


   // add some edges
   add_edge(0, 1, g);
   add_edge(1, 5, g);
   add_edge(5, 6, g);``
   add_edge(2, 3, g);
   add_edge(2, 4, g);

   // represent graph in DOT format and send to cout
   write_graphviz(cout, g);
   return 0;
   }       

请告诉我如何添加彩色边缘而不是彩色顶点.例如,顶点0和1之间的边缘我希望它给它一些颜色,例如红色,所以所有其他边缘应该是不同的颜色,顶点0和1之间的边缘应该是红色,我该如何设置该属性.

我想使用boost的dijkstra算法(因为我在程序的其他部分使用了boost).我遇到的问题是添加自定义对象(我相信它们被称为property)adjacency_list.

基本上我有一个自定义边缘类,它维护有关边缘和通过它连接的顶点的各种信息.我想用我所需的边缘属性存储我的自定义数据对象adjaceny_list

我已经成功实现了提升提供的玩具示例.我试图使用自定义属性无济于事(提升示例,提升属性).我只是将我的VEdge数据结构封装在一个结构或其他东西中,我只需要能够检索它.但我无法弄清楚如何将自定义数据结构包含在boost adjaceny_list结构中.

在我的情况下,我有以下程序:

Main.cpp的:

#include <iostream>
#include <fstream>
#include "dijkstra.h"
#include <vector>

int
main(int, char *[])
{
  // Generate the vector of edges from elsewhere in the program
  std::vector<VEdge*> edges; //someclass.get_edges();

  td* test = new td(edges);
  test->run_d();

  test->print_path();

  return EXIT_SUCCESS;
}

Dijkstra.cpp:

#include <iostream>
#include <fstream>
#include "dijkstra.h"

using namespace boost;

td::td() {
    kNumArcs = sizeof(kEdgeArray) / sizeof(Edge);
    kNumNodes = 5;
}

td::td(std::vector<VEdge*> edges) {
    // …

我已经花了几天的时间来处理Boost图形库。据我了解，在考虑VertexList和EdgeList存储时：

vecS：

• 拥有索引，因此可以对其进行访问
• 删除顶点时，迭代器无效

listS：

• 没有索引
• 不会使迭代器无效

这有点短，但这是我的问题的关键。我需要这些索引号，并且希望以后能够轻松删除顶点。

我有这种图形结构的工作算法：

typedef boost::adjacency_list<
        boost::vecS, boost::vecS, boost::undirectedS, 
        topologicalmap::Intersection_Graph ,
        boost::edge_weight_t, 
        boost::no_property > Graph_boost;

我有一个Intersection_Graph需要使用的顶点自定义结构。在这里我使用vecS。

我想改用listS来删除顶点。同样，我希望以后能够与Dijkstra算法一起使用。

我有点理解我需要boost::vertex_index_t在列表中，但是我对如何做到并同时保留自定义结构感到非常困惑。

我尝试了一些方法：

typedef boost::adjacency_list<
        boost::listS, boost::listS, boost::undirectedS, 
        boost::property<boost::vertex_index_t, topologicalmap::Intersection_Graph>,
        boost::edge_weight_t, 
        boost::no_property > Graph_boost;

但是我什至无法访问我的自定义结构。另外，索引访问不起作用。

我真的需要那种索引访问功能，因为我的图的算法将取决于返回父节点的索引。我觉得我可以摆脱使用Vertex而不是索引的习惯，但这意味着代码需要大量重写，我想知道是否可以避免使用它。

所以我的问题是：在保持listS优势的同时，有什么方法可以使listS表现得像vecS一样？

请，如果这听起来很愚蠢，请忍受我。我现在很困惑，所以我可能会说些愚蠢的话。如果您需要更多信息，请询问。

编辑:正如@sehe指出的那样,错误位于中介中心性计算之前的某个位置.向前走!

我实现了一个最小的程序来计算的无向图的中介中心,在两个Python和C++.令人惊讶的是,networkx(Python)版本远远超过boost::graph(C++)实现,即使有人考虑加载开销等等.我做的事情是完全无效的吗？

Python代码的要点很简单

# load graph and start chrono
clist = nx.betweenness_centrality(g)
# output

对于C++,我们有

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

typedef boost::property_map< Graph, boost::vertex_index_t>::type VertexIndexMap;

int main() {
    Graph g;

    // ... 
    // load graph
    // ...

    VertexIndexMap v_index = get(boost::vertex_index, g);
    std::vector< double > vertex_property_vec(boost::num_vertices(g), 0.0);
    boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap >
          vertex_property_map(vertex_property_vec.begin(), v_index);


    boost::brandes_betweenness_centrality(g, vertex_property_map);

    // Output ...
    return 0;
}

请注意,两个库似乎都实现了完全相同的算法(Brandes 2001).