标签: boost-graph

如何将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();

我从昨天开始就被这个问题困住了。不幸/幸运的是，这个问题只占我超级庞大（对我来说，一个 c++ 新手）算法的 0.5% 左右，因此需要一个现有代码库，一个可以适应并让事情正常工作的现有代码库。

我想检测并给出无向图中的所有圆圈。我的边缘没有加权。是的，我真正需要的是所有循环，即类似于有向图的所有哈密顿循环

我一直在玩boost图库，DFS算法似乎很有前途，但是，它只访问顶点一次，因此不能给出所有的哈密顿圆。

目前，我只需要代码工作，这样我就可以继续我的算法设计，之后我可能会考虑性能问题。即使是带有 5 个嵌套 for 循环的解决方案也是受欢迎的。

这是我从 boost 得到并玩过的代码，但我不知道如何记录和访问我的 back_edges 的前辈，即使解决了，boost DFS 也只会访问顶点一次：

struct detect_loops : public boost::dfs_visitor<>
{
   template <class Edge, class Graph>
   void back_edge(Edge e, const Graph& g) {
      std::cout << source(e, g)
        << " -- "
        << target(e, g) << "\n";
   }
};

int main(int,char*[])
{
    typedef std::pair<int,int> Edge;
    std::vector<Edge> edges;
    edges.push_back(Edge(0,1));
    edges.push_back(Edge(1,2));
    edges.push_back(Edge(2,3));
    edges.push_back(Edge(3,1));
    edges.push_back(Edge(4,5));
    edges.push_back(Edge(5,0));
    edges.push_back(Edge(4,0));
    edges.push_back(Edge(5,6));
    edges.push_back(Edge(2,6));

    typedef adjacency_list<
       vecS, vecS, undirectedS, no_property,
       property<edge_color_t, default_color_type>
    > graph_t;
    typedef …

我的问题基于:如何打印显示单个属性的图形

我正在使用捆绑属性:

 typedef struct vert{
   std::string name;
 };

 typedef struct edge{
   int capacity;
   int weight;
 }; 

typedef adjacency_list<listS, vecS, undirectedS, vert, edge> Graph;
Graph g;
vector<int,int> ele;

我在一个应该创建边的循环中调用以下内容:

  edge prop;
  prop.weight = 5;
  prop.capacity = 4;
  add_edge(ele.first,ele.second, prop, g);

此段是将图形打印为点格式的内容.

ofstream dot("graph.dot");
write_graphviz(dot, g, 
  boost::make_label_writer(boost::get(&vert::name, g)),
  boost::make_label_writer(boost::get(&edge::weight, g)),
  boost::make_label_writer(boost::get(&edge::capacity, g)));

错误是:

/usr/include/boost/graph/graphviz.hpp: In function ‘void boost::write_graphviz(std::ostream&, const Graph&, VertexPropertiesWriter, EdgePropertiesWriter, GraphPropertiesWriter, VertexID) [with Graph = boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, vert, edge, boost::no_property, boost::listS>, VertexPropertiesWriter = boost::label_writer<boost::bundle_property_map<boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, …

所以,我今天必须通过Boost文档一小时.我必须失明.我希望,我有一个简单的问题:

如何使用boost :: adjacency_list获取边的相应顶点？

我有以下代码,我想弄清楚:

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> Graph;
typedef boost::graph_traits<Graph>::edge_iterator EdgeIterator;
typedef std::pair<EdgeIterator, EdgeIterator> EdgePair;

EdgePair ep;
for (ep = edges(g); ep.first != ep.second; ++ep.first)
{
    // Get the two vertices that are joined by this edge...
}

有人知道怎么做吗？

谢谢

我需要遍历图形的边缘并检查每条边的权重.我没有修改边缘,因此我的函数对图形采用const引用.但是,我知道获得边权重的唯一方法是访问属性映射,这似乎违反了const-ness.

void printEdgeWeights(const Graph& graph) {
  typedef Graph::edge_iterator EdgeIterator;
  std::pair<EdgeIterator, EdgeIterator> edges = boost::edges(graph);

  typedef boost::property_map<Graph, boost::edge_weight_t>::type WeightMap;
  // The following line will not compile:
  WeightMap weights = boost::get(boost::edge_weight_t(), graph);

  EdgeIterator edge;
  for (edge = edges.first; edge != edges.second; ++edge) {
    std::cout << boost::get(weights, *edge) << std::endl;
  }
}

所以我必须这样做:

Graph& trust_me = const_cast<Graph&>(graph);
WeightMap weights = boost::get(boost::edge_weight_t(), trust_me);

有办法避免这种情况吗？

另一方面,属性映射查找是否是恒定时间？

作为参考,这是我对Graph的定义.

struct FeatureIndex { ... };
typedef boost::property<boost::vertex_index_t, int,
                        FeatureIndex>
        VertexProperty;
typedef boost::property<boost::edge_index_t, int,
        boost::property<boost::edge_weight_t, int> >
        EdgeProperty;
typedef …

我知道在通用编程中,算法与容器分离.因此,将通用算法实现为实例方法是没有意义的(相同的算法应该适用于多个具体类;我们不希望它们都从一个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)更好的方法来做我想做的事情？此外,您的解决方案是否允许在发现顶点时添加/删除边和顶点？

我是boost noob。我想知道为什么在以下代码中编译失败。我正在创建一组顶点，并尝试分配我自己的顶点索引和顶点名称。（我正在关注此页面：http : //fireflyblue.blogspot.com/2008/01/boost-graph-library.html。）

我知道vertS顶点列表Boost不需要明确的顶点 id 创建，我也在 Stackoverflow（如何为我的图提供 vertex_index 属性）中看到了这个非常相关的问题，它讨论了如何使用 anassociative_property_map来分配顶点索引。下面虽然 - 获取 vertex_index 映射，并分配键值对 - 似乎是一件相当简单的事情，我想了解它为什么失败。任何帮助是极大的赞赏！

编译错误如下：

error: expression is not assignable vertIndx[v] = i;

//Define graph
typedef boost::property<boost::vertex_name_t, std::string> sv_namePty;
typedef boost::property<boost::vertex_index_t, int, sv_namePty > sv_indx_n_name_pty;
typedef boost::property<boost::edge_weight_t, int> se_weightPty;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, 
        sv_indx_n_name_pty, se_weightPty> ScafGraph;

//descriptors
typedef boost::graph_traits<ScafGraph>::vertex_descriptor SV;
typedef boost::graph_traits<ScafGraph>::edge_descriptor SE;

//Graph Object
ScafGraph SG;

//property accessors
boost::property_map<ScafGraph, 
     boost::vertex_name_t>::type vertName = boost::get(boost::vertex_name, SG);
boost::property_map<ScafGraph, 
     boost::vertex_index_t>::type …

TL; DR：我非常希望in_edges 图上的迭代顺序（adjacency_list带有 edge_list of setS）是确定性的，但据我所知，迭代顺序是由一个比较运算符决定的，它只是指针比较---因此迭代顺序由 的变幻莫测决定 malloc。帮助！

为了具体起见，我的图表和相关类型是：

struct VertexCargo { int Id; ... };

typedef adjacency_list<setS, vecS, bidirectionalS, property<vertex_info_t, VertexCargo> > Graph;

typedef graph_traits<Graph>::edge_descriptor   ED;
typedef graph_traits<Graph>::vertex_descriptor VD;

我的逻辑，以防有人在任何地方发现谬误：

1. in_edges 迭代直接由边列表容器的迭代决定

2. setS隐含底层容器的边缘列表std::set<edge_desc_impl> 注意：这个假设是不正确的；它实际上是一个std::set<StoredEdge，它提供了一个比较边缘目标的比较器。

3. std::set<edge_desc_impl> 迭代顺序由 operator<(edge_desc_impl, edge_desc_impl)

4. operator<(edge_desc_impl, edge_desc_impl)最终只是一个指针比较；

operator< 在boost/graph/detail/edge.hpp(boost 1.58) 中定义：

30      template <typename Directed, typename Vertex>
31      class edge_desc_impl  : public edge_base<Directed,Vertex> {

...

35        typedef void                              property_type;
36
37 …

我正在尝试使用Boost vf2_subgraph_iso()来检测子图同构.

我可以在简单的图形上成功完成此操作,但不能在多图形(允许有多个边缘的图形)上执行此操作.

考虑检测以下G1和G2之间的子图同构:

G1是G2的子图,我想使用以下代码检测:

#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>

int main()
{
  // Define edge property
  typedef boost::property<
    boost::edge_name_t,
    char
  > edge_property;

  // Define graph type
  typedef boost::adjacency_list<
    boost::vecS,           // OutEdgeListS
    boost::vecS,           // VertexListS
    boost::bidirectionalS, // DirectedS
    boost::no_property,    // VertexProperties
    edge_property,         // EdgeProperties
    boost::no_property,    // GraphProperties
    boost::listS           // EdgeListS
  > MyGraphType;

  // Build graph G1
  MyGraphType g1;
  std::vector<MyGraphType::vertex_descriptor> v1(3);
  for (auto itr = v1.begin(); itr != v1.end(); ++itr) {
    *itr = boost::add_vertex(g1);
  }
  boost::add_edge(v1[0], v1[1], …