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

user_3478105 0
Viewed 121

My question is very simple. I'm looking to find out an edge given the vertices it's connecting. The complicated way would be to iterate through all edges and compare each source and target with the vertices im using. I figured there would have to be a better way to do this which is why I'm asking

boost-graph c++
1 Answers

It depends on your graph model: https://valelab4.ucsf.edu/svn/3rdpartypublic/boost/libs/graph/doc/graph_concepts.html

AdjacencyMatrix has what you want directly:

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

(where e, v and u are descriptors).

Assuming you have a non-bidirectional instance of AdjacencyList you will have to look through the adjacencies of the source vertex:

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

In the case of Bidirectional graphs you have the option of going from the target vertex.

DEMO

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

Prints e.g.

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)

Further Optimization

In the case of setS vertex selector you MIGHT be able to optimize using std::binary_search and friends (std::lower_bound, std::upper_bound or std::equal_range).

I would heavily consult my profiler to see whether that actually improves performance. I have a feeling it might not unless you have very very high out-degrees.

user_853710
Related