在无向图中通过顶点查找边 [C++ BGL]

Question

我的问题很简单。我正在寻找给定它连接的顶点的边。复杂的方法是遍历所有边缘并将每个源和目标与我使用的顶点进行比较。我认为必须有更好的方法来做到这一点，这就是为什么我要问

Answer 1

这取决于您的图形模型：https://valelab4.ucsf.edu/svn/3rdpartypublic/boost/libs/graph/doc/graph_concepts.html

AdjacencyMatrix直接有你想要的：

 auto e = boost::edge(v, u, graph);

（其中 e、v 和 u 是描述符）。

假设您有一个非双向的 AdjacencyList 实例，您将不得不查看源顶点的邻接关系：

using Graph = boost::adjacency_list<>;
using V     = Graph::vertex_descriptor;
using E     = Graph::edge_descriptor;

E my_find_edge(V v, V u, Graph const& g)
{
    for (auto e : boost::make_iterator_range(out_edges(v, g))) {
        if (target(e, g) == u)
            return e;
    }
    throw std::domain_error("my_find_edge: not found");
}

在双向图的情况下，您可以选择从目标顶点出发。

演示

Live On Compiler Explorer

#include "boost/graph/adjacency_list.hpp"
#include <boost/range/iterator_range.hpp>

using Graph = boost::adjacency_list<>;
using V     = Graph::vertex_descriptor;
using E     = Graph::edge_descriptor;

E my_find_edge(V v, V u, Graph const& g)
{
    for (auto e : boost::make_iterator_range(out_edges(v, g))) {
        if (target(e, g) == u)
            return e;
    }
    throw std::domain_error("my_find_edge: not found");
}

#include "boost/graph/random.hpp"
#include <random>
int main() {
    std::mt19937 prng { std::random_device{}() };

    for (auto i = 0; i < 10; ++i)
        try {
            Graph g;
            generate_random_graph(g, 10, 20, prng);

            E e = my_find_edge(7, 2, g);
            std::cout << "Found: " << e << "\n";
        } catch (std::exception const& e) {
            std::cout << e.what() << "\n";
        }
}

打印例如

my_find_edge: not found
my_find_edge: not found
Found: (7,2)
Found: (7,2)
my_find_edge: not found
my_find_edge: not found
my_find_edge: not found
my_find_edge: not found
my_find_edge: not found
Found: (7,2)

进一步优化

在 setS 顶点选择器的情况下，您可以使用 std::binary_search 和朋友（std::lower_bound、std::upper_bound 或 std::equal_range）进行优化。

我会大量咨询我的探查器，看看这是否真的提高了性能。我有一种感觉，除非你有非常非常高的出度数，否则它可能不会。

在无向图中通过顶点查找边 [C++ BGL]

Find an Edge by its vertices in an undirected graph [C++ BGL]

c++

boost-graph

演示

进一步优化