关于C ++ boost图库的一些问题 [英] Some questions about the C++ boost graph library

查看：213
本文介绍了关于C ++ boost图库的一些问题的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

所以我发布这个，因为我目前正在研究一个算法项目，并可能会使用boost库从输入文本文件构建图形。所以我注意到图中的顶点有一个描述符，但是由于我有一个非常大的图来构建，我需要为该图中的每个顶点分配一个描述符吗？如果我不这样做，我可以在构建完成后遍历整个图表吗？

我是boost库的新手，这有点紧急，所以如果有人能解释这一点，我将非常感激！

解决方案

顶点描述符描述一个顶点（以便宜的，独立于图模型的方式）。

图形模型描述一个图形。



迭代器



当你想遍历一个使用迭代器遍历图： 

  typedef boost :: adjacency_list<>图形; 
 typedef Graph :: vertex_iterator Vit; 
 
 Vit开始，结束; 
 boost :: tie（begin，end）= vertices（g）;

取消引用有效的迭代器会为您提供描述符（对于边迭代器也是如此）。



简单演示：

Live Live Coliru 

  #include< boost / graph / adjacency_list.hpp> 
 #include< iostream> 
 
 int main（）{
 typedef boost :: adjacency_list<>图形; 
 typedef Graph :: vertex_iterator Vit; 
图g（10）; 
 
 add_edge（2,5，g）; 
 add_edge（5,3，g）; 
 add_edge（3,8，g）; 
 
 Vit开始，结束; 
 boost :: tie（begin，end）= vertices（g）; 
 
（Vit it = begin; it！= end; ++ it）{
 unsigned edges = out_degree（* it，g）; 
 if（edges）
 std :: cout<< 顶点＃<< *它 具有<<边缘<< 传出边缘\\\
; 
 
 
 $ / code $ / pre 
 $ b $ p  
 
 
 顶点＃2有1个传出边缘
顶点＃3有1个传出边缘
顶点＃5有1个传出边缘（s）
  
 
 
 
使用基于节点的顶点容器的图模型
 
 
 
并非所有的图都有整型的顶点描述符，所以添加边更加复杂，并且打印它们看起来并不那么友好 
 
 
  < kbd> 直播Coliru    
  #include< boost / graph / adjacency_list.hpp> 
 #include< iostream> 
 $ b $ int main（）{
 typedef boost :: adjacency_list< boost :: setS，boost :: listS / *，boost :: undirectedS * />图形; 
 typedef Graph :: vertex_iterator Vit; 
图g（10）; 
 
 Vit开始，结束; 
 boost :: tie（begin，end）= vertices（g）; 
 
 {
 std :: vector< Graph :: vertex_descriptor> vindex（开始，结束）; 
 add_edge（vindex [2]，vindex [5]，g）; 
 add_edge（vindex [5]，vindex [3]，g）; 
 add_edge（vindex [3]，vindex [8]，g）; 
 
 
（Vit it = begin; it！= end; ++ it）{
 unsigned edges = out_degree（* it，g）; 
 if（edges）
 std :: cout<< 顶点＃<< *它 具有<<边缘<< 传出边缘\\\
; 
 
 
 $ / code $ / pre 
 
打印
 
 
 顶点＃0x994d00有1个传出边缘
顶点＃0x994d70有1个传出边缘
顶点＃0x994e50有1个传出边缘s）
  
 
 
 
属性
 
 
 
在这种情况下，请考虑添加一个属性包。
 
 
 
通过这种方式，可以将任意应用程序特定的信息附加到模型顶点（或边或图）。
 
 
 
 
在我看来，主要的缺点是没有自然的属性索引，所以通过其（捆绑）属性查找图形实体可能会得到不好的性能（线性搜索），除非你手动在图表外保留一个额外的索引。 
 
    Live Live Coliru    
  #include< boost / graph / adjacency_list .HPP> 
 #include< iostream> 
 
 struct VertexProperties {
 std :: string name; 
 VertexProperties（std :: string name）：name（name）{} 
}; 
 
 int main（）{
 typedef boost :: adjacency_list< boost :: setS，boost :: listS，boost :: directedS，VertexProperties>图形; 
 typedef Graph :: vertex_iterator Vit; 
图形g; 
 
 add_vertex（VertexProperties（zero），g）; 
 add_vertex（VertexProperties（one），g）; 
 add_vertex（VertexProperties（two），g）; 
 add_vertex（VertexProperties（three），g）; 
 add_vertex（VertexProperties（four），g）; 
 add_vertex（VertexProperties（five），g）; 
 add_vertex（VertexProperties（six），g）; 
 add_vertex（VertexProperties（seven），g）; 
 add_vertex（VertexProperties（eight），g）; 
 add_vertex（VertexProperties（nine），g）; 
 
 Vit开始，结束; 
 boost :: tie（begin，end）= vertices（g）; 
 
 {
 std :: vector< Graph :: vertex_descriptor> vindex（开始，结束）; 
 
 add_edge（vindex [2]，vindex [5]，g）; 
 add_edge（vindex [5]，vindex [3]，g）; 
 add_edge（vindex [3]，vindex [8]，g）; 
 
 
（Vit it = begin; it！= end; ++ it）{
 unsigned edges = out_degree（* it，g）; 
 if（edges）
 std :: cout<< 顶点<< g [* it] .name<< '具有<<边缘<< 传出边缘\\\
; 
 
 
 $ / code $ / pre 
 
 $ p 
 
 
 顶点'two'有1个传出边缘
顶点'three'有1个传出边缘
顶点'five'有1传出边缘
  
 
So I'm posting this because I'm currently working on an algorithm project and might gonna use the boost library for building a graph from an input text file. So I have noticed that there is a descriptor for the vertex in a graph, but since I have a very large graph to be built, do I need to allocate a descriptor for every vertex in that graph? If I don't, can I traverse the whole graph after it's been built? 



I'm a newbie to the boost library and this is a little emergent so if anybody can explain this I will be very grateful! 
 解决方案 
A vertex descriptor describes a vertex (in cheap, graph model independent way).



A graph model describes a graph.



Iterators



When you want to traverse a graph, you traverse the graph, using the iterators:
typedef boost::adjacency_list<> Graph;
typedef Graph::vertex_iterator Vit;

Vit begin, end;
boost::tie(begin, end) = vertices(g);

Dereferencing a valid iterator gives you the descriptor (same thing goes for edge iterators).



Simple demo:



Live On Coliru
#include <boost/graph/adjacency_list.hpp>
#include <iostream>

int main () {
    typedef boost::adjacency_list<> Graph;
    typedef Graph::vertex_iterator Vit;
    Graph g(10);

    add_edge(2,5,g);
    add_edge(5,3,g);
    add_edge(3,8,g);

    Vit begin, end;
    boost::tie(begin, end) = vertices(g);

    for (Vit it = begin; it != end; ++it) {
        unsigned edges = out_degree(*it, g);
        if (edges)
            std::cout << "vertex #" << *it << " has " << edges << " outgoing edge(s)\n";
    }
}

Prints:
vertex #2 has 1 outgoing edge(s)
vertex #3 has 1 outgoing edge(s)
vertex #5 has 1 outgoing edge(s)




Graph Model With Node-Based Vertex Containers



Not all graph have integral vertex descriptors, so adding edges becomes more complicated, and printing them doesn't look so "friendly"



Live On Coliru
#include <boost/graph/adjacency_list.hpp>
#include <iostream>

int main () {
    typedef boost::adjacency_list<boost::setS, boost::listS/*, boost::undirectedS*/> Graph;
    typedef Graph::vertex_iterator Vit;
    Graph g(10);

    Vit begin, end;
    boost::tie(begin, end) = vertices(g);

    {
        std::vector<Graph::vertex_descriptor> vindex(begin, end);
        add_edge(vindex[2], vindex[5], g);
        add_edge(vindex[5], vindex[3], g);
        add_edge(vindex[3], vindex[8], g);
    }

    for (Vit it = begin; it != end; ++it) {
        unsigned edges = out_degree(*it, g);
        if (edges)
            std::cout << "vertex #" << *it << " has " << edges << " outgoing edge(s)\n";
    }
}

Printing
vertex #0x994d00 has 1 outgoing edge(s)
vertex #0x994d70 has 1 outgoing edge(s)
vertex #0x994e50 has 1 outgoing edge(s)




Properties



In such cases, consider adding a property bundle.



This way, arbitrary application-specific information can be attached to model vertices (or edges, or graphs).

  
The main downside, in my opinion, of this is that there's no natural indexing for the properties, so looking up a graph entity by its (bundled) property could get bad performance (linear search) unless you keep an extra index outside of the graph manually.


Live On Coliru
#include <boost/graph/adjacency_list.hpp>
#include <iostream>

struct VertexProperties {
    std::string name;
    VertexProperties(std::string name) : name(name) {}
};

int main () {
    typedef boost::adjacency_list<boost::setS, boost::listS, boost::directedS, VertexProperties> Graph;
    typedef Graph::vertex_iterator Vit;
    Graph g;

    add_vertex(VertexProperties ("zero"), g);
    add_vertex(VertexProperties ("one"), g);
    add_vertex(VertexProperties ("two"), g);
    add_vertex(VertexProperties ("three"), g);
    add_vertex(VertexProperties ("four"), g);
    add_vertex(VertexProperties ("five"), g);
    add_vertex(VertexProperties ("six"), g);
    add_vertex(VertexProperties ("seven"), g);
    add_vertex(VertexProperties ("eight"), g);
    add_vertex(VertexProperties ("nine"), g);

    Vit begin, end;
    boost::tie(begin, end) = vertices(g);

    {
        std::vector<Graph::vertex_descriptor> vindex(begin, end);

        add_edge(vindex[2], vindex[5], g);
        add_edge(vindex[5], vindex[3], g);
        add_edge(vindex[3], vindex[8], g);
    }

    for (Vit it = begin; it != end; ++it) {
        unsigned edges = out_degree(*it, g);
        if (edges)
            std::cout << "vertex '" << g[*it].name << "' has " << edges << " outgoing edge(s)\n";
    }
}

Prints
vertex 'two' has 1 outgoing edge(s)
vertex 'three' has 1 outgoing edge(s)
vertex 'five' has 1 outgoing edge(s)



                        
这篇关于关于C ++ boost图库的一些问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
相关文章
C/C++开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆