标签: boost-graph

我从昨天开始就被这个问题困住了。不幸/幸运的是，这个问题只占我超级庞大（对我来说，一个 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 …

我有一个const函数对象,并且对于时间,它返回无效.但可以返回int或double.我正在用c ++ 11样式编写代码,并且只是尝试使用auto作为返回类型.虽然代码编译,但我不确定它是否100%正确.这是代码.

template <typename graph_t>
 struct my_func { 
   public:
    my_func() {  } 
    my_func (graph_t&  _G) : G(_G) {  } 

   template <typename edge_t>
   auto operator()(edge_t   edge) -> void const {

     //do something with the edge.
   } //operator

   private:
    graph_t& G;
   };

   //call the functor: (pass graph G as template parameter)
   std::for_each(beginEdge, endEdge, my_func<Graph>(G));

此代码完美地编译并在串行模式下工作.现在我尝试使用intel TBB parallel_for_each()并行化上面的for_each.这要求函数对象为const.意味着不应该允许线程修改或更改函数对象的私有变量.

   //tbb::parallel_for_each
   tbb::paralle_for_each(beginEdge, endEdge, my_func<Graph>(G));

   Now, the compiler error comes: 
   passing const my_func< ... > ..  discards qualifiers

所以我不得不将operator()()更改为以下内容:

   template <typename edge_t>
   void operator()(edge_t  edge) …

我是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], …

(对于标题道歉,我无法想出一个短于140个字符的好文章......)

我正在为boost :: graph库编写一个图算法.在我的算法中,我需要保留关于节点的变量,权重和计数器.就文档和查看其他人的代码而言,执行此操作的典型方法是将这些属性直接附加到图形并使用属性映射访问它们.

但是,在库函数中,我不希望将特定的读/写映射与图形捆绑在一起,因此我创建了自己的外部属性映射.但这些需要一个std::map(或等效的),所以我最终创建了a std::map和a boost::associative_property_map<std::map>.关于这一点的好处是我有一个统一的方法来获取我的算法的属性和用户的属性(boost::get),但在不利方面,我似乎有两个冗余的地图.除了提到的均匀性之外,这样做有什么意义吗？我可以以某种方式让属性映射维护它自己的内部映射(我意识到内存中没有增益等,但是会有一个更少的成员变量来跟踪每个属性)？

我想要效率,如果效率(= 0.9*速度+0.1*其他)很高,我愿意自己编写代码.如果我要在LEDA图形或Boost图形之间进行选择,我应该选择哪一个？

我的算法非常耗时(有些甚至是非多项式的,在大图上工作).

使用boost :: graph库的boost示例通常使用如下图

using namespace boost;
typedef adjacency_list
    < vecS, // edge container 
      vecS, // vertex container
      undirectedS,
      property<vertex_index_t, int>,
      property<edge_index_t, int>
    > graph;

因此它们工作得很好。但是我有一个图

typedef adjacency_list
   < setS, // edge container 
     listS, // vertex container
     undirectedS,
     boost::no_property,  // vertex property
     boost::no_property // edge property
   > graph;

而且算法无法立即使用。在大多数情况下，必须提供用于查找特定顶点索引（整数值）的vertex_descriptor的映射。

我想检查我的图是否是平面的，并计算它的平面嵌入。我提供了一个顶点索引图，它确实以这种方式用于（例如connected_components）算法，但显然不适用于boyer_myrvold_planarity_test：

using namespace boost;

typedef adjacency_list
<boost::setS, boost::listS, undirectedS,
     boost::no_property, boost::no_property> graph;

typedef  boost::graph_traits<graph>::edge_descriptor    EdgeDesc;
typedef boost::graph_traits<graph>::vertex_descriptor   VertexDesc;

typedef std::map<VertexDesc, size_t> VertexDescMap;
typedef std::map<EdgeDesc, size_t> EdgeDescMap;
typedef boost::graph_traits<graph>::vertex_iterator VertexIterator;


graph K_4;

std::vector<VertexDesc> …

我使用Boost图库定义了一个Graph,

typedef boost::property<boost::edge_weight_t, int> EdgeWeightProperty;
typedef boost::adjacency_list<boost::listS, boost::vecS,boost::undirectedS,boost::no_property,EdgeWeightProperty> Graph;

使用添加边缘相当简单

boost::add_edge(vertice1, vertice2, weight, graph);

我还没有弄清楚如何设置边缘重量.一种可能的解决方案是删除边缘并使用更新的权重值重新添加它,但是,这看起来有点过分.

我想在BGL的labeled_graph中检索标记节点的标签,但找不到这样做的方法.

以下MWE演示了我在寻找的内容:

//g++ -O3 question.cpp -o question.exe -I. --std=c++11 -lprotobuf-lite -lpthread -lz -losmpbf
#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/labeled_graph.hpp>
#include <boost/graph/iteration_macros.hpp>

typedef long long node_id_t;

typedef boost::adjacency_list<
  boost::listS,           // Store out-edges of each vertex in a std::list
  boost::listS,           // Store vertex set in a std::list
  boost::bidirectionalS,  // The file dependency graph is directed
  boost::no_property,     // vertex properties
  boost::no_property      // edge properties
> AdjGraph;

typedef boost::labeled_graph<
  AdjGraph,
  node_id_t          // Node ID
> LabeledGraph;

int main(){
  LabeledGraph g;

  add_vertex( 10, g ); …