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

问题描述

这与我昨天遇到的关于使用整数索引访问顶点的问题有关.该线程在这里:

#include #include #include <fstream>#include #include 使用命名空间提升；typedef adjacency_list_traits性状；typedef adjacency_list<vecS, vecS, 定向,属性<顶点名称_t, std::string,属性>>>>,属性::type E = get(edge_index, g);int from[maxnoedges], to[maxnoedges];//我想避免使用这个.//创建边特性::edge_descriptor ed;int eindex = 0;ed = (add_edge(0, 1, g)).first;从[eindex] = 0;to[eindex] = 1;//我想避免使用这个.E[ed] = eindex++;ed = (add_edge(0, 2, g)).first;从[eindex] = 0;to[eindex] = 2;//我想避免使用这个.E[ed] = eindex++;ed = (add_edge(1, 3, g)).first;从[eindex] = 1;to[eindex] = 3;//我想避免使用这个.E[ed] = eindex++;ed = (add_edge(2, 3, g)).first;从[eindex] = 2;to[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
", vindex, out_degree(vindex, g));for (tie(ei, e_end) = out_edges(vindex, g); ei != e_end; ++ei)printf("从 %d 到 %d
", source(*ei, g), target(*ei, g));}printf("边数为 %d
", num_edges(g));//有没有boost提供的有效方法//代替必须显式维护 from 和 to 数组//开发者的一部分?for (int eindex = 0; eindex 

代码构建和编译没有错误.带有 vindex 的 for 循环与 out_edges 和 out_degree 一起工作正常，将整数索引作为参数.

有没有办法对下一个 for 循环做同样的事情，直接使用 boost::graph 数据结构打印边缘?

我查看了以下处理类似问题的线程:

Boost图库:通过 int 类型的索引获取 edge_descriptor 或访问边

建议的答案是使用 unordered_map.与使用 from[] 和 to[] 数组相比，使用它是否有任何权衡?是否有任何其他计算效率高的访问边缘的方法?

解决方案

你只能这样做

• 使用不同的图形模型
• 外部边缘索引

概念

您可能对 感兴趣AdjacencyMatrix 概念.它并不完全包含完整的边 ID，但是 AdjacencyMatrix 也可以通过源/目标顶点查找边.

要获得真正完整的边描述符，您可能需要编写自己的图形模型类(对一组现有的 BGL 概念进行建模).您可能还对 grid_graph<>(每个顶点有一组固定的编号边，其中顶点是网格)感兴趣.

• 如何在 boost::grid_graph 中使用给定的 vertex_descriptor 访问 edge_descriptor - 您可以设计一个全局"编号方案，从而获得线性查找时间

邻接表

这是对上一个答案的修改，显示了外部索引.它类似于您的解决方案.我选择了 bimap 所以至少你可以自动"进行反向查找.

//创建边boost::bimaps::bimapedge_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("重复键");返回d；};auto a = single(from, to), b = single(to, from);转[a] = b;转[b] = a;};new_edge_pair(0, 1);new_edge_pair(0, 2);new_edge_pair(1, 3);new_edge_pair(2, 3);

现在您可以通过边 ID 进行循环:

auto&by_id = edge_idx.left;for (auto const& e : by_id) {std::cout <<边#"<<e.首先<<" 是 (" << source(e.second, g) << " -> " << target(e.second, g) << ")
";}

您可以直接通过 id 查找边:

auto ed = by_id.at(random);std::cout <<随机边#"<<随机<<" 是 (" << source(ed, g) << " -> " << target(ed, g) << ")
";

反向查找有点多余，因为你可以很容易地使用 BGL 做同样的事情:

std::cout <<"反向查找:" <<by_desc.at(ed) <<"
";//反转，虽然不是很壮观std::cout <<"经典属性查找:" <<g[ed].id<<"
";//因为它可以很容易地使用 boost 来完成

生活在 Coliru

#include #include #include #include <功能>#include #include #include <随机>std::mt19937 prng { std::random_device{}() };使用命名空间提升；struct VertexProperty { std::string name;};结构边属性{内部标识；双倍容量，residual_capacity；EdgeProperty(int id, double cap, double res = 0): id(id)、容量(cap)、residual_capacity(res){ }};typedef adjacency_list图形;int main() {int nonodes = 4;图 g(nonodes);//反向边缘图auto rev = make_vector_property_map<Graph::edge_descriptor>(get(&EdgeProperty::id, g));//创建边boost::bimaps::bimapedge_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("重复键");返回d；};auto a = single(from, to), b = single(to, from);转[a] = b;转[b] = a;};new_edge_pair(0, 1);new_edge_pair(0, 2);new_edge_pair(1, 3);new_edge_pair(2, 3);//属性映射struct VertexEx {default_color_type 颜色；双倍距离；图::edge_descriptor pred;};自动 idx = get(vertex_index, g);auto vex = make_vector_property_map(idx);自动预测 = make_transform_value_property_map(std::mem_fn(&VertexEx::pred), vex);自动颜色 = 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);//算法双流 = boykov_kolmogorov_max_flow(g, cap, rescap, rev, pred, color, dist, idx, 0, 3);std::cout <<流程:"<<流量＜＜"
";{自动&by_id = edge_idx.left;自动&by_desc = edge_idx.right;for (auto const& e : edge_idx.left) {std::cout <<边#"<<e.首先<<" 是 (" << source(e.second, g) << " -> " << target(e.second, g) << ")
";}int 随机 = prng() % num_edges(g);自动 ed = by_id.at(random);std::cout <<随机边#"<<随机<<" 是 (" << source(ed, g) << " -> " << target(ed, g) << ")
";std::cout <<"反向查找:" <<by_desc.at(ed) <<"
";//反转，虽然不是很壮观std::cout <<"经典属性查找:" <<g[ed].id<<"
";//因为它可以很容易地使用 boost 来完成}}

打印

流程: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 typedef adjacency_matrix图形;

现在您获得了按顶点查找的附加功能:

生活在 Coliru

std::cout <<在边 # 中找到 (3, 1) 结果"<<by_desc.at(edge(3, 1, g).first) <<"
";

印刷品

在 Edge #5 中找到 (3, 1) 结果

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
", 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("Number of edges is %d
", 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
", 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) << ")
";
}

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) << ")
";

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) << "
"; // reverse, though not very spectacular
std::cout << "Classic property lookup: " << g[ed].id << "
"; // 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 << "
";

    {
        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) << ")
";
        }
        int random = prng() % num_edges(g);
        auto ed = by_id.at(random);
        std::cout << "Random edge #" << random << " is (" << source(ed, g) << " -> " << target(ed, g) << ")
";

        std::cout << "Reverse lookup: " << by_desc.at(ed) << "
"; // reverse, though not very spectacular
        std::cout << "Classic property lookup: " << g[ed].id << "
"; // 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) << "
";

Prints

Finding (3, 1) results in Edge #5

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