标签: boost-graph

目前，我有一个图表，我vertices通过. 因此，每当我需要访问标签属性时，我都会在地图中找到标签并获取.labelsexternal mapmapped vertex

/// vertex properties
struct VertexData
{
    std::string label;
    int num;
};

/// edges properties
struct EdgeData
{
    std::string edge_name;
    double edge_confidence;
};

/// define the boost-graph
typedef boost::adjacency_list<boost::vecS, boost::vecS,
        boost::bidirectionalS,
        boost::property<boost::edge_index_t , size_t , VertexData>,
        boost::property<boost::edge_weight_t, double, EdgeData> > Graph;

/// define vertexMap
std::map<std::string, vertex_t> vertexMap;

///loop through the vertices to make the vertexMap here ...
vertexMap.insert(std::pair<std::string, vertex_t> (label, v));

/// find any label in the map and access the corresponding …

我通常使用vecS以下容器boost::adjacency_list：

struct myVertexType { std::vector<Stuff> vec; /* and more */ };
struct myEdgeType { /* some data too */ };
using Graph = boost::adjacency_list<
        boost::vecS,
        boost::vecS,
        boost::directedS,
        myVertexType,
        myEdgeType
    >;

但是，我遇到的情况引发了一个问题：我正在引用一些作为顶点的捆绑属性存储的数据，当我创建另一个顶点时，这似乎使我的引用无效 (1)。

至少这是我通过阅读本页（“迭代器和描述符稳定性/失效”部分）所理解的。

所以我切换到listS，一切顺利：

using Graph = boost::adjacency_list<
        boost::listS,
        boost::listS,
        boost::directedS,
        myVertexType,
        myEdgeType
    >;

直到...

直到我注意到 with listS，boost::target( e1, g )无法编译！:

Graph g;
auto e1 = boost::add_edge(1, 0, g).first;
auto t = boost::target( e1, g );

这也无法构建：（参见 coliru …

我在使用Boost图形库的邻接列表时遇到问题.它似乎是一个循环依赖问题:我有一个模板的typedef T使用了一些类A.另外一个存储指向类型为T的对象的指针.现在编译器告诉我,T没有命名一个类型.

以下是我更具体文件的摘录:

//graphdefinitions.hpp
#include "lane.hpp"
#include "tie.hpp"

typedef boost::adjacency_list<boost::listS, boost::listS, 
                              boost::directedS, Tie, Lane> Map;
typedef boost::graph_traits<Map>::edge_descriptor edge_descriptor;

//lane.hpp
#include "graphdefinitions.hpp"
class Lane {
    ...
    edge_descriptor *left, *right;
};

//tie.hpp
//no important includes here
class Tie {
    ...
};

如何解决此依赖/包含顺序问题？

另一个编辑:我只是认为edge_descriptor的类型可能是像int这样的原始类型.这样就解决了这个问题,因为我可以通过普通的int变量替换Lane的edge_descriptors,因此可以删除tie.hpp中包含graphdefinitions.hpp.不幸的是我的想法很疯狂*我必须找到另一个解决方案.Edge_descriptor类型似乎是有原因的......

所以我使用了以下类型的增强图:

typedef boost::adjacency_list<boost::listS, boost::vecS, boost:directedS, VertexT, EdgeT> GraphT

VertexT和EdgeT都是保留我需要的许多属性的类.这些是捆绑属性.我不确定我是否有可能使用bgl的某些方式,所以如果你熟悉它们,我们将非常感谢帮助.

VertexT和EdgeT被认为是多态基类.我的理解是bgl不是用于指向这些属性的指针.如何使用BGL处理多态顶点和边缘属性？我想过使用共享指针,但我更喜欢自己管理内存.此外,这似乎可以防止在使用boost :: get生成boost布局的位置图时出现问题.

现在我只是通过让顶点包含另一个指向真正的多态类的指针来破解我的方式.但这似乎太复杂了.有什么建议？

我正在努力让自定义属性编写器与BGL一起工作.

struct IkGraph_VertexProperty {
    int id_ ;
    int type_ ;
    std::pair<int,int> gaussians_ ; // Type of Joint, Ids of Gaussians
};


struct IkGraph_VertexPropertyTag
{
typedef edge_property_tag kind;
static std::size_t const num; 
};

std::size_t const IkGraph_VertexPropertyTag::num = (std::size_t)&IkGraph_VertexPropertyTag::num;

typedef property<IkGraph_VertexPropertyTag, IkGraph_VertexProperty> vertex_info_type;

...方法中定义的自定义图形

typedef adjacency_list<setS, vecS, bidirectionalS, vertex_info_type, IkGraph_EdgeProperty> TGraph ;
TGraph testGraph ;
std::ofstream outStr(filename) ;
write_graphviz(outStr, testGraph, OurVertexPropertyWriter<TGraph,IkGraph_VertexPropertyTag, IkGraph_VertexProperty>(testGraph));

...

template <class Graph, class VertexPropertyTag, class VertexProperty>
struct OurVertexPropertyWriter {

  OurVertexPropertyWriter(Graph &g_) : g(g_) {}

 template <class Vertex>
 void …

在有向图上使用标准,

std::vector<size_type> dtime(N);
std::vector<size_type> ftime(N);
size_type t = 0;
dfs_time_visitor<size_type*> vis(&dtime[0], &ftime[0], t);
depth_first_search(graph, visitor(vis));

似乎总是从节点0启动dfs.

如何告诉算法从已知的"根节点"开始？

我知道如何在Boost Graph中创建具有整数或char顶点的图形（请参见下面的注释代码）。问题是如何重写此代码以使用字符串顶点？

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

using namespace boost;

int main (int argc, char **argv)
{
        typedef adjacency_list <vecS, vecS, undirectedS> vector_graph_t;

        //works
        //typedef std::pair <int, int> E;
        //E edges[] = { E (2, 5), E (5, 3), E (3, 1), E (5, 1)};
        //vector_graph_t g (&edges[0],&edges[0] + sizeof(edges) / sizeof(E), 4);

        //works
        //typedef std::pair <char, char> E;
        //E edges[] = { E ('a', 'b'), E ('a', 'c'), E ('x', 'a'), E ('b', 'x')};
        //vector_graph_t g (&edges[0],&edges[0] + sizeof(edges) …

boost函数boost :: graph :: copy_graph

 template <class VertexListGraph, class MutableGraph>  void
 copy_graph(const VertexListGraph& G, MutableGraph& G_copy,
     const bgl_named_params<P, T, R>& params = all defaults)

在参数描述中列出 UTIL/OUT: orig_to_copy(Orig2CopyMap c)了从复制中的顶点到原始顶点的映射.我需要这个映射!

(在http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/copy_graph.html上滚动到底部)

如何访问/提供最后一个参数orig_to_copy？你能给出一个代码示例,即为我完成这段代码吗？

void doSomething(graph_t& g){
  graph_t g_copy;
  copy_graph(g, g_copy, [...???...]);
  // here I would like to access the Orig2CopyMap
}

在使用BGL实现一些算法之后,我试图使用GraphML提供io功能.但是,我没有设法编译一个合适的运算符<<,它采用const Graph引用.

这是一个简单的例子:

// use bundled properties for vertices and edges
struct VertexProperty
{
   double error;
};

typedef boost::adjacency_list< boost::setS, boost::setS, boost::undirectedS, VertexProperty> Graph;

typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;

std::ostream& operator<<(std::ostream& os, const Graph& graph)
{
    typedef std::map<vertex_descriptor, std::size_t> IndexMap;
    IndexMap index_map;
    boost::associative_property_map<IndexMap> index_properties(index_map);

    std::size_t i = 0;
    for (const vertex_descriptor& v : boost::make_iterator_range(boost::vertices(graph)))
        index_properties[v] = i++;

    boost::dynamic_properties dp;
    typename boost::property_map<Graph, double VertexProperty::*>::const_type error_map = get(&VertexProperty::error, graph);

    dp.property("error", error_map);

    boost::write_graphml(os, graph,index_properties,dp);

    return os;
}

int main()
{ …

我是C++和Boost Spirit X3的新手.对于我的项目,我将两个文件中的地理社交图解析为具有以下结构,其中boost boost X3为boost图.

我有一个有效的实施.由于我之前没有任何图书馆的经验,我想知道你对这种方法的看法,以及你是否建议采取不同的方法.

在图形文件中,每条边有一条线.解析边缘时,我必须创建图形的节点,以防以前没有看到节点.我使用语义操作,每次遇到node-id时都会检查该节点是否已经在图中.阅读完一行后,我使用语义动作然后添加边缘.

在位置文件中,在给定时间每个节点的已知位置有一行.我存储了图中节点已知的第一个位置(使用自定义boost图属性).

我必须提出具体问题,但很乐意接受任何想法和建议:

• 是否可以像使用图形文件一样使用嵌套语义操作？这会伤害性能吗？
• 是否建议使用Spirit X3一次解析整个文件,还是应该使用Spirit X3单独解析每一行？

图表(表示图中的边)

[user1]     [user2]
0           3

地点

[user]  [check-in time]         [latitude]      [longitude]     [location id]
0       2010-10-19T23:55:27Z    30.2359091167   -97.7951395833      22847

Spirit X3解析代码

// Parse the gowalla edge file
boost::spirit::istream_iterator file_iterator(edge_file), eof;

x3::phrase_parse(file_iterator, eof,
        // Begin grammar
        (
         *((x3::int_[add_vertex] >> x3::int_[add_vertex])[add_edge])
        ),
        // End grammar
        x3::space
        );

// Fail if we couldn't parse the whole edges file
if (file_iterator != eof) {
    std::cerr << "Couldn't parse whole edges file" << …