使用整数索引访问boost :: graph中的特定边 [英] Accessing specific edges in boost::graph with integer index

查看：152 发布时间：2018/5/25 17:01:54 c++ boost graph

本文介绍了使用整数索引访问boost :: graph中的特定边的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

这与昨天关于使用整数索引访问顶点的问题有关。该线程在这里：

  #include< boost / config.hpp> 
 #include< iostream> 
 #include< fstream> 
 
 #include< boost / graph / graph_traits.hpp> 
 #include< boost / graph / adjacency_list.hpp> 
 
使用命名空间boost; 
 
 typedef adjacency_list_traits< vecS，vecS，directedS>性状; 
 
 typedef adjacency_list< 
 vecS，vecS，directedS，
 property< 
 vertex_name_t，std :: string，
 property< vertex_index_t，int，
 property< vertex_color_t，boost :: default_color_type，
 property< vertex_distance_t，double，
 property< vertex_predecessor_t，Traits :: edge_descriptor> > > > >，
 
 property< 
 edge_index_t，int，
 property< edge_capacity_t，double，
 property< edge_weight_t，double，
 property< edge_residual_capacity_t，double，
 property< edge_reverse_t，Traits :: edge_descriptor> ; > > > > > 
图形; 
 
 int main（）{
 int nonodes = 4; 
 const int maxnoedges = 4; //我想避免使用这个。 
图g（非节点）; 
 
 property_map< Graph，edge_index_t> :: type E = get（edge_index，g）; 
 
 int从[maxnoedges]，到[maxnoedges]; //我想避免使用这个。 
 
 
 //创建边缘
 Traits :: edge_descriptor ed; 
 
 int eindex = 0; 
 
 ed =（add_edge（0，1，g））。 $ [eindex] = 0; b $ b;到[eindex] = 1; //我想避免使用这个。 
 E [ed] = eindex ++; 
 
 
 ed =（add_edge（0，2，g））。 $ [eindex] = 0; b $ b;到[eindex] = 2; //我想避免使用这个。 
 E [ed] = eindex ++; 
 
 ed =（add_edge（1，3，g））。来自[eindex] = 1的
;到[eindex] = 3; //我想避免使用这个。 
 E [ed] = eindex ++; 
 
 ed =（add_edge（2，3，g））。来自[eindex] = 2的
;到[eindex] = 3; //我想避免使用这个。 
 E [ed] = eindex ++; 
 
 graph_traits<图表> :: out_edge_iterator ei，e_end; 
 for（int vindex = 0; vindex< num_vertices（g）; vindex ++）{
 printf（顶点％d的排出次数为％d \ n，vindex，out_degree（vindex， G））; 
 for（tie（ei，e_end）= out_edges（vindex，g）; ei！= e_end; ++ ei）
 printf（From％d to％d\\\
，source（* ei，g），target（* ei，g））; 
 
 
 printf（边数为％d \ n，num_edges（g））; 
 
 //是否有任何有效的方法boost提供
 //代替必须显式维护数组
 //对部分开发人员？ （int eindex = 0; eindex< num_edges（g）; eindex ++）
 printf（Edge％d从％d到％d \ n，eindex，来自[eindex]为[eindex]）; 
 
}

代码无错地编译和编译。使用 vindex 的循环的与 out_edges 和 out_degree 工作正常，将参数作为整数索引。

 
 
 有没有办法对下一个 for 循环直接使用boost :: graph数据结构打印边缘？
 
 
 我看了下面一个处理类似问题的线程：

建议的答案是使用 unordered_map 。在使用这个方法时有没有权衡，而不是从[] 和到[] 数组中使用？是否还有其他计算效率高的访问边缘的方法？

解决方案

b

 
 使用不同的图形模型

外部边缘索引
 
 
 概念
 
 
 您可能对  AdjacencyMatrix 概念。它并不完全符合整体边缘标识符，但 AdjacencyMatrix 也具有按源/目标顶点查找边缘的功能。
 
 
 <要获得真正完整的边描述符，您可能需要编写您自己的图模型类（建模一组现有的BGL概念）。您可能还对 grid_graph<> 感兴趣（每个顶点有一组固定的编号边，顶点是网格）。
 
  
  如何在boost :: grid_graph 中使用给定的vertex_descriptor访问edge_descriptor   - 您可以设计一个全局数字方案，从而获得线性查询时间
 
 
 
 邻接列表
 
 
 下面是对前一个答案的修改，显示了一个外部索引。这与您的解决方案类似。我选择了 bimap ，所以至少你可以自动地进行反向查找。
  //创建边缘
 boost :: bimaps :: bimap< int，Graph :: edge_descriptor> edge_idx; 
 $ b $ auto new_edge_pair = [&，edge_id = 0]（int from，int to）mutable {
 auto single = [&]（int from，int to）{
 auto d = add_edge（from，to，EdgeProperty {edge_id，4}，g）.first; 
 if（！edge_idx.insert（{edge_id ++，d}）。second）
 throw std :: invalid_argument（duplicate key）; 
 return d; 
}; 
 
 auto a =单个（from，to），b = single（to，from）; 
 rev [a] = b; 
 rev [b] = a; 
}; 
 
 new_edge_pair（0，1）; 
 new_edge_pair（0，2）; 
 new_edge_pair（1，3）; 
 new_edge_pair（2,3）; 
  
现在您可以通过edge id来完成循环：
  auto& by_id = edge_idx.left; 
 for（auto const& e：by_id）{
 std :: cout<< 边缘＃<< e.first<< 是（<<源（e.second，g）<><<<<<> \\\
; 
} 
  
您可以直接通过id查找边缘：
  auto ed = by_id.at（random）; 
 std :: cout<< 随机边缘＃<<随机<< 是（<< source（ed，g）<><<<（ed，g）<<）\\\
; 
  
反向查找有点多余，因为您可以很容易地使用BGL执行相同操作：
  std :: cout<< 反向查找：<< by_desc.at（ed）<< \\\
; //相反，虽然不是很壮观
 std :: cout<< 经典属性查找：<< g [ed] .id<< \\\
; //因为可以使用boost轻松完成
  
    Live Live Coliru    
  #include< boost / graph / adjacency_list.hpp> 
 #include< boost / property_map / transform_value_property_map.hpp> 
 #include< boost / graph / boykov_kolmogorov_max_flow.hpp> 
 #include< functional> 
 #include< iostream> 
 
 #include< boost / bimap.hpp> 
 #include< random> 
 
 std :: mt19937 prng {std :: random_device {}（）}; 
 
使用命名空间boost; 
 
 struct VertexProperty {std :: string name; }; 
 
 struct EdgeProperty {
 int id; 
双容量，residual_capacity; 
 
 EdgeProperty（int id，double cap，double res = 0）
：id（id），容量（cap），residual_capacity（res）
 {} 
 }; 
 
 typedef adjacency_list< vecS，vecS，directedS，VertexProperty，EdgeProperty>图形; 
 
 int main（）{
 int nonodes = 4; 
图g（非节点）; 
 
 //反向边缘图
 auto rev = make_vector_property_map< Graph :: edge_descriptor>（get（&EdgeEdperty :: id，g））; 
 
 //创建边线
 boost :: bimaps :: bimap< int，Graph :: edge_descriptor> edge_idx; 
 $ b $ auto new_edge_pair = [&，edge_id = 0]（int from，int to）mutable {
 auto single = [&]（int from，int to）{
 auto d = add_edge（from，to，EdgeProperty {edge_id，4}，g）.first; 
 if（！edge_idx.insert（{edge_id ++，d}）。second）
 throw std :: invalid_argument（duplicate key）; 
 return d; 
}; 
 
 auto a =单个（from，to），b = single（to，from）; 
 rev [a] = b; 
 rev [b] = a; 
}; 
 
 new_edge_pair（0，1）; 
 new_edge_pair（0，2）; 
 new_edge_pair（1，3）; 
 new_edge_pair（2,3）; 
 
 //属性映射
结构VertexEx {
 default_color_type color; 
双倍距离; 
 Graph :: edge_descriptor pred; 
}; 
 
 auto idx = get（vertex_index，g）; 
 auto vex = make_vector_property_map< VertexEx>（idx）; 
 auto pred = make_transform_value_property_map（std :: mem_fn（& VertexEx :: pred），vex）; 
 auto color = make_transform_value_property_map（std :: mem_fn（& VertexEx :: color），vex）; 
 auto dist = make_transform_value_property_map（std :: mem_fn（& VertexEx :: distance），vex）; 
 
 auto cap = get（&EdgeProperty :: capacity，g）; 
 auto rescap = get（& EdgeProperty :: residual_capacity，g）; 
 
 //算法
 double flow = boykov_kolmogorov_max_flow（g，cap，rescap，rev，pred，color，dist，idx，0，3）; 
 std :: cout<< 流程：<<流量< \\\
; 
 
 {
 auto& by_id = edge_idx.left; 
 auto& by_desc = edge_idx.right; 
 
 for（auto const& e：edge_idx.left）{
 std :: cout<< 边缘＃<< e.first<< 是（<<源（e.second，g）<><<<<<> \\\
; 
} 
 int random = prng（）％num_edges（g）; 
 auto ed = by_id.at（随机）; 
 std :: cout<< 随机边缘＃<<随机<< 是（<< source（ed，g）<><<<（ed，g）<<）\\\
; 
 
 std :: cout<< 反向查找：<< by_desc.at（ed）<< \\\
; //相反，虽然不是很壮观
 std :: cout<< 经典属性查找：<< g [ed] .id<< \\\
; //因为可以使用boost轻松完成
 
 
 code 
 
 
 打印
 
 pre $ code $ 8 
边缘＃0是（0-> 1）
边缘＃1是（1-> 0）
边缘＃2是（0-> 2）
边缘＃3是（2-> 0）
边缘＃4是（1-> 3）
边缘＃5是（3-> 1）
边缘＃6是（2-> 3）
边缘＃7是（3-> 2）
随机边缘＃2是（0-> 2）
反向查找：2 
经典属性查找：2 
  
 
 
 
邻接矩阵
 
 
 保持一切，除了更改模型： 
 
 
  #include< boost / graph / adjacency_matrix.hpp> 
 typedef adjacency_matrix< directedS，VertexProperty，EdgeProperty>图形; 
  
现在您可以通过顶点添加查找功能了：
 
 
    直播Coliru    
  std :: cout<< 查找（3,1）导致边缘＃<< by_desc.at（边（3,1，g）.first）<< \\\
; 
  
打印
 找到（3,1）结果为边缘＃5 
  
 
This is related to a question I had yesterday about accessing vertices using integer indices. That thread is here: Accessing specific vertices in boost::graph

The solution there indicated that using vecS as the type for vertices, it is indeed possible to access specific vertices using the integer index. I was wondering if there is a similar method provided by boost to access arbitrary edges efficiently using integer indices.

Attached is a code that depicts the former (valid access of vertices with integer indices) and accessing the edges based on the developer explicitly maintaining two arrays, from[] and to[], that store the source and the target, respectively of the edges.

The code creates the following graph:

#include <boost/config.hpp>
#include <iostream>
#include <fstream>

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

using namespace boost;

typedef adjacency_list_traits<vecS, vecS, directedS> Traits;

typedef adjacency_list<
    vecS, vecS, directedS,
    property<
    vertex_name_t, std::string,
    property<vertex_index_t, int,
    property<vertex_color_t, boost::default_color_type,
    property<vertex_distance_t, double,
    property<vertex_predecessor_t, Traits::edge_descriptor> > > > >,

    property<
    edge_index_t, int,
    property<edge_capacity_t, double,
    property<edge_weight_t, double,
    property<edge_residual_capacity_t, double,
    property<edge_reverse_t, Traits::edge_descriptor> > > > > >
    Graph;

int main() {
    int nonodes = 4;
    const int maxnoedges = 4;//I want to avoid using this.
    Graph g(nonodes);

    property_map<Graph, edge_index_t>::type             E = get(edge_index, g);

    int from[maxnoedges], to[maxnoedges];//I want to avoid using this.


    // Create edges
    Traits::edge_descriptor ed;

    int eindex = 0;

    ed = (add_edge(0, 1, g)).first;
    from[eindex] = 0; to[eindex] = 1;//I want to avoid using this.
    E[ed] = eindex++;


    ed = (add_edge(0, 2, g)).first;
    from[eindex] = 0; to[eindex] = 2;//I want to avoid using this.
    E[ed] = eindex++;

    ed = (add_edge(1, 3, g)).first;
    from[eindex] = 1; to[eindex] = 3;//I want to avoid using this.
    E[ed] = eindex++;

    ed = (add_edge(2, 3, g)).first;
    from[eindex] = 2; to[eindex] = 3;//I want to avoid using this.
    E[ed] = eindex++;

    graph_traits < Graph >::out_edge_iterator ei, e_end;
    for (int vindex = 0; vindex < num_vertices(g); vindex++) {
        printf("Number of outedges for vertex %d is %d\n", vindex, out_degree(vindex, g));
        for (tie(ei, e_end) = out_edges(vindex, g); ei != e_end; ++ei)
            printf("From %d to %d\n", source(*ei, g), target(*ei, g));
    }

    printf("Number of edges is %d\n", num_edges(g));

    //Is there any efficient method boost provides 
    //in lieu of having to explicitly maintain from and to arrays
    //on part of the developer?
    for (int eindex = 0; eindex < num_edges(g); eindex++)
        printf("Edge %d is from %d to %d\n", eindex, from[eindex], to[eindex]);

}
The code builds and compiles without error. The for loop with vindex works fine with out_edges and out_degree working fine taking as parameters integer indices.

Is there a way to do likewise for the next for loop that prints the edges using boost::graph data structures directly?

I looked at the following thread dealing with a similar question:

Boost graph library: Get edge_descriptor or access edge by index of type int

The suggested answer there was to use an unordered_map. Is there any tradeoff in using this as opposed to having the from[] and to[] arrays? Are there any other computationally efficient methods of accessing edges?
 解决方案 
You can only do this if you 


use a different graph model
an external edge index


Concepts

You could be interested in the AdjacencyMatrix concept. It doesn't exactly sport integral edge ids, but AdjacencyMatrix has lookup of edge by source/target vertices as well.

To get truly integral edge descriptors, you'd probably need write your own graph model class (modeling a set of existing BGL concepts). You might also be interested in grid_graph<> (which has a fixed set of numbered edges per vertex, where the vertices are a grid).


How to access edge_descriptor with given vertex_descriptor in boost::grid_graph - you could devise a "global" numering scheme and thus get linear lookup time


Adjacency List

Here's a modification from the previous answer showing an external index. It's akin to your solution. I chose bimap so at least you get the reverse lookup "automagically".
// Create edges
boost::bimaps::bimap<int, Graph::edge_descriptor> edge_idx;

auto new_edge_pair = [&,edge_id=0](int from, int to) mutable {
    auto single = [&](int from, int to) {
        auto d = add_edge(from, to, EdgeProperty { edge_id, 4 }, g).first;
        if (!edge_idx.insert({edge_id++, d}).second)
            throw std::invalid_argument("duplicate key");
        return d;
    };

    auto a = single(from, to), b = single(to, from);
    rev[a] = b;
    rev[b] = a;
};

new_edge_pair(0, 1);
new_edge_pair(0, 2);
new_edge_pair(1, 3);
new_edge_pair(2, 3);
Now you can do the loop by edge id:
auto& by_id = edge_idx.left;
for (auto const& e : by_id) {
    std::cout << "Edge #" << e.first << " is (" << source(e.second, g) << " -> " << target(e.second, g) << ")\n";
}
You can directly lookup an edge by it's id:
auto ed = by_id.at(random);
std::cout << "Random edge #" << random << " is (" << source(ed, g) << " -> " << target(ed, g) << ")\n";
The reverse lookup is a bit redundant, because you can do the same using BGL quite easily:
std::cout << "Reverse lookup: " << by_desc.at(ed) << "\n"; // reverse, though not very spectacular
std::cout << "Classic property lookup: " << g[ed].id << "\n"; // because it can be done using boost easily
Live On Coliru
#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <functional>
#include <iostream>

#include <boost/bimap.hpp>
#include <random>

std::mt19937 prng { std::random_device{}() };

using namespace boost;

struct VertexProperty { std::string name; };

struct EdgeProperty {
    int id;
    double capacity, residual_capacity;

    EdgeProperty(int id, double cap, double res = 0)
        : id(id), capacity(cap), residual_capacity(res)
    { }
};

typedef adjacency_list<vecS, vecS, directedS, VertexProperty, EdgeProperty> Graph;

int main() {
    int nonodes = 4;
    Graph g(nonodes);

    // reverse edge map
    auto rev    = make_vector_property_map<Graph::edge_descriptor>(get(&EdgeProperty::id, g));

    // Create edges
    boost::bimaps::bimap<int, Graph::edge_descriptor> edge_idx;

    auto new_edge_pair = [&,edge_id=0](int from, int to) mutable {
        auto single = [&](int from, int to) {
            auto d = add_edge(from, to, EdgeProperty { edge_id, 4 }, g).first;
            if (!edge_idx.insert({edge_id++, d}).second)
                throw std::invalid_argument("duplicate key");
            return d;
        };

        auto a = single(from, to), b = single(to, from);
        rev[a] = b;
        rev[b] = a;
    };

    new_edge_pair(0, 1);
    new_edge_pair(0, 2);
    new_edge_pair(1, 3);
    new_edge_pair(2, 3);

    // property maps
    struct VertexEx {
        default_color_type color;
        double distance;
        Graph::edge_descriptor pred;
    };

    auto idx    = get(vertex_index, g);
    auto vex    = make_vector_property_map<VertexEx>(idx);
    auto pred   = make_transform_value_property_map(std::mem_fn(&VertexEx::pred),     vex);
    auto color  = make_transform_value_property_map(std::mem_fn(&VertexEx::color),    vex);
    auto dist   = make_transform_value_property_map(std::mem_fn(&VertexEx::distance), vex);

    auto cap    = get(&EdgeProperty::capacity, g);
    auto rescap = get(&EdgeProperty::residual_capacity, g);

    // algorithm
    double flow = boykov_kolmogorov_max_flow(g, cap, rescap, rev, pred, color, dist, idx, 0, 3);
    std::cout << "Flow: " << flow << "\n";

    {
        auto& by_id   = edge_idx.left;
        auto& by_desc = edge_idx.right;

        for (auto const& e : edge_idx.left) {
            std::cout << "Edge #" << e.first << " is (" << source(e.second, g) << " -> " << target(e.second, g) << ")\n";
        }
        int random = prng() % num_edges(g);
        auto ed = by_id.at(random);
        std::cout << "Random edge #" << random << " is (" << source(ed, g) << " -> " << target(ed, g) << ")\n";

        std::cout << "Reverse lookup: " << by_desc.at(ed) << "\n"; // reverse, though not very spectacular
        std::cout << "Classic property lookup: " << g[ed].id << "\n"; // because it can be done using boost easily
    }
}
Printing
Flow: 8
Edge #0 is (0 -> 1)
Edge #1 is (1 -> 0)
Edge #2 is (0 -> 2)
Edge #3 is (2 -> 0)
Edge #4 is (1 -> 3)
Edge #5 is (3 -> 1)
Edge #6 is (2 -> 3)
Edge #7 is (3 -> 2)
Random edge #2 is (0 -> 2)
Reverse lookup: 2
Classic property lookup: 2


Adjacency Matrix

Keeps everything the same, except for changing the model:
#include <boost/graph/adjacency_matrix.hpp>
typedef adjacency_matrix<directedS, VertexProperty, EdgeProperty> Graph;
And now you get the added capability of lookup by vertices:

Live On Coliru
std::cout << "Finding (3, 1) results in Edge #" << by_desc.at(edge(3, 1, g).first) << "\n";
Prints
Finding (3, 1) results in Edge #5


                        
这篇关于使用整数索引访问boost :: graph中的特定边的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！


                    
                        查看全文

邻接列表

邻接矩阵

Concepts

Adjacency List

Adjacency Matrix

使用整数索引访问boost :: graph中的特定边 [英] Accessing specific edges in boost::graph with integer index

问题描述

概念

相关文章

C/C++开发最新文章

热门教程

热门工具

登录关闭

使用整数索引访问boost :: graph中的特定边 [英] Accessing specific edges in boost::graph with integer index

问题描述

概念

邻接列表

邻接矩阵

Concepts

Adjacency List

Adjacency Matrix

相关文章

C/C++开发最新文章

热门教程

热门工具

登录 关闭

登录关闭