标签: boost-graph

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

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

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

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

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

我正在使用BGL来存储我的DAG.顶点有状态.给定一个顶点中的状态变化,我想更新依赖顶点.这我可以使用boost :: depth_first_search和自定义访问者.

现在的逻辑是,如果顶点处于特定状态,我不想更新搜索的顶点及其相关因素.基本上我想控制dfs或bfs中顶点的排队.在BGL中实现这一目标的最佳方法是什么.

谢谢.

由于我的图形使用setS for vertex,我必须为我的图形提供vertex_index属性映射,或者为write_graphviz提供一个显式的vertex_id参数,以便能够使用write_graphviz. My graph is defined as: typedef adjacency_list<setS, setS, undirectedS, NodeData, EdgeData> Graph; NodeData和EdgeData是结构的地方.你能给我一个如何为我的图提供vertex_index属性映射的一个非常简单的例子吗？或者如何给write_graphviz一个明确的vertex_id参数？

谢谢

我有一组节点AG,Z,定义了加权边,其中AG是漏斗中的各种节点,Z位于最底部.

可视化具有各种边缘的漏斗(V形),但最终指向最终节点Z,就像水流向单点Z.我们希望找到最便宜的路径,直到Z,覆盖漏斗中的所有节点.

以下是约束:

• 没有孤立节点(所有节点都连接/包含)
• 我们希望最小化加权边的总和
• "共享边缘",如水向下流动时合并,仅计算共享边缘的重量一次(换句话说,它可以自由地沿湿路径流动)

我应该使用哪种增强图算法来找到这个问题的最佳边缘集？

• ABDEZ是一条覆盖大量节点的廉价路径
• CGZ有点被迫,因为G只有一条到Z的路径
• FZ看起来便宜,但后来我们注意到,由于CGZ被迫,FGZ实际上比FZ便宜(因为我们不需要对GZ段进行双重计算,FG的增量成本仅为1)

所以,边缘集应该是(AB,BD,DE,EZ,CG,FG,GZ)

我确信这不是一个新问题:我只是不知道足够的图论来识别/命名算法.

更新

在对问题进行更多研究的同时,我发现如果图不是定向的,那么问题就会减少到最小生成树.换句话说,如果我们没有先验地指出Z是图中的最低点(通过使用箭头),并允许水在两个方向上流动(通常是真的,除非我们有阀门),那么这第二个模型将正常工作.

当然,我们现在可以选择新的FZ无向边缘,而不是被迫使用旧的GZ定向边缘.

根据这些结果,如果我们真的需要指向边缘,liori的答案是对原始问题的最佳响应(即算法需要编码).

产量

D <--> E with weight of 1
F <--> G with weight of 1
A <--> B with weight of 2
E <--> Z with weight of 2
C <--> G with weight of 2
F <--> Z with weight of 2
B <--> D with weight of 3 …

我正在尝试使用boost图库,当我尝试使用boost :: edge()时,我遇到了段错误.完整的代码可以在这里找到,但是我在这里制作了一个具有相同问题的最小程序(我用"g ++ minimal.cpp"编译):

#include<stdio.h>
#include<boost/graph/adjacency_list.hpp>

using namespace boost;
using namespace std;

typedef adjacency_list<> graph_t;
typedef graph_traits<graph_t>::edge_descriptor edge_descriptor;

int main(){
    graph_t G;
    //add_edge(1,3,G);
    //remove_edge(1,3,G);
    pair<edge_descriptor, bool> res = edge(1,3,G);
    printf("G does %shave an edge 1->3\n", res.second ? "" : "not ");
    return 0;
}

如果我取消注释add_edge,remove_edge行,则不会发生段错误,程序会打印出预期的

G does not have an edge 1->3

但有没有办法避免这样的hackery？谢谢!

使用Boost图库我正在寻找一种方法来提取邻接矩阵从由任一代表的底层的图boost::adjacency_list或boost::adjacency_matrix.我想结合使用这个矩阵boost::numeric::ublas来求解一个联立线性方程组.

这是一个让你前进的最小例子:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>

using namespace boost;

typedef boost::adjacency_list< listS, vecS, directedS > ListGraph;
typedef boost::adjacency_matrix< directedS > MatrixGraph;

int main(){ 

  ListGraph lg; 
  add_edge (0, 1, lg); 
  add_edge (0, 3, lg); 
  add_edge (1, 2, lg); 
  add_edge (2, 3, lg); 

  //How do I get the adjacency matrix underlying lg?

  MatrixGraph mg(3); 
  add_edge (0, 1, mg); 
  add_edge (0, 3, mg); 
  add_edge (1, 2, mg); 
  add_edge (2, 3, mg); 

  //How do …

我知道有几个版本的Graphviz作为库.但我有点困惑的是哪一个被认为是当前+推荐.我想从linux GUI应用程序生成并显示一些图表.

根据第22页的http://www.graphviz.org/doc/libgraph/Agraph.pdf,Libgraph被Cgraph取代.但该文件被称为Agraph,我觉得很奇怪.

在第23页,它还说Lgraph是Cgraph的C++继承者,因为我使用C++,我想知道更多,但我似乎无法在任何地方找到Lgraph.

也许是相关的,我确实看到有一个名为BGL的Boost库,它支持导入和导出graphviz文件.寻找关于是否优先使用BGL直接使用Graphviz或Lgraph的意见.

如果sudo apt-get install libgraphviz-dev我得到Cgraph,它看起来像在Ubuntu上.在这种情况下,这个问题是确认Cgraph是推荐的库,并询问是否值得考虑Lgraph或BGL.

如何将adjacency_list类型的图形复制到另一个类型为adjacency_list的图形中？

typedef adjacency_list<setS, setS, undirectedS, NodeDataStruct, EdgeDataStruct> MyGraph;
MyGraph g1, g2;

// processing g1: adding vertices and edges ...
// processing g2: adding some vertices and edges ...

g1.clear();
g1 = g2 // this gives an execution error (exception)
g1 = MyGraph(g2); // this also gives an execution error
g2.clear();

我知道在通用编程中,算法与容器分离.因此,将通用算法实现为实例方法是没有意义的(相同的算法应该适用于多个具体类;我们不希望它们都从一个ABC继承,因为它会以指数方式增加类的数量).

但是source()对于Boost图库中的函数,我不明白它为什么是全局函数而不是图类的实例方法.

据我所知,通过阅读BGL源代码,source(e, g)需要知道图形的实现细节和传递给它的边缘对象; 只知道他们的界面是不够的.

所以source()不是通用算法.换句话说,它需要知道图形实例的具体类.那么为什么不把它作为实例方法放在同一个类中呢？它不是比制作一个需要为每个被调用的类定制的全局函数更清晰/更少混淆吗？

UPDATE

相关源代码:

  // dwa 09/25/00 - needed to be more explicit so reverse_graph would work.
  template <class Directed, class Vertex,
      class OutEdgeListS,
      class VertexListS,
      class DirectedS,
      class VertexProperty,
      class EdgeProperty,
      class GraphProperty, class EdgeListS>
  inline Vertex
  source(const detail::edge_base<Directed,Vertex>& e,
         const adjacency_list<OutEdgeListS, VertexListS, DirectedS,
                 VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)
  {
    return e.m_source;
  }


namespace boost {

  namespace  detail {

    template <typename Directed, …

最小的例子:

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

struct vertex
{
    int number;
};
struct edge {};

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, vertex, edge> graph_t;
typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_t;
typedef boost::graph_traits<graph_t>::edge_descriptor edge_t;

struct vertex_visitor : public boost::default_dfs_visitor
{
    void discover_vertex(vertex_t v, graph_t& g)
    {
        g[v].number = 42;
    }
};

int main()
{
    graph_t g;
    vertex_t v1 = boost::add_vertex(g);
    vertex_t v2 = boost::add_vertex(g);
    boost::add_edge(v1, v2, g);

    vertex_visitor vis;
    boost::depth_first_search(g, boost::visitor(vis));

    return 0;
}

它不起作用,因为图形需要像const在中一样被引用vertex_visitor::discover_vertex().

有没有比编写我自己的DFS算法(或使用const_cast)更好的方法来做我想做的事情？此外,您的解决方案是否允许在发现顶点时添加/删除边和顶点？