How to iterate over boost graph to get incoming and outgoing edges of vertex?

user_14407275 0
Viewed 126

I am trying to iterate over boost graph. While iterating, I am trying to find incoming edges and outgoing edges from that vertex. But I am getting segmentaion fault.
I tried to debug and found the line where it throws segmentation fault.

(vertex -> vertex of the graph of which incoming and outgoing edges needs to find out)
(graph -> boost graph )

//Finding out edges of vertex
    boost::graph_traits<BGType>::out_edge_iterator ei, ei_end;
    boost::tie(ei, ei_end) = out_edges( vertex, graph ); // error at this line
    for( boost::tie(ei, ei_end) = out_edges(vertex, graph); ei != ei_end; ++ei)
    {
        auto target = boost::target ( *ei, graph );
        graph[target]._isVisible = false;
    }

    //Finding in edges of vertex
    boost::graph_traits<BGType>::in_edge_iterator ein, ein_end;
    boost::tie(ein, ein_end) = in_edges( vertex, graph ); // error at this line
    for( boost::tie(ein, ein_end) = in_edges(vertex, graph); ein != ein_end; ++ein)
    {
        auto source = boost::source ( *ein, graph ); 
        graph[source]._isVisible = false;
    }
c++17 graph c++11 boost c++
1 Answers
boost::tie(ei, ei_end) = out_edges( vertex, graph ); // error at this line
boost::tie(ein, ein_end) = in_edges( vertex, graph ); // error at this line

Both comments suggest that either graph or vertex are invalid. Check that graph is still a valid reference to an object.

If so, then "obviously" vertex is incorrect. It could be out-of-range. Consider checking it:

void hide_neighbours(BGV vertex, BGType& graph) {
    assert(vertex < num_vertices(graph));

And while you're at it, we can simplify the implementation:

void hide_neighbours(BGV vertex, BGType& graph) {
    assert(vertex < num_vertices(graph));
    using boost::make_iterator_range;

    for (auto e : make_iterator_range(out_edges(vertex, graph)))
        graph[target(e, graph)]._isVisible = false;
    for (auto e : make_iterator_range(in_edges(vertex, graph)))
        graph[source(e, graph)]._isVisible = false;
}

Live Demo

Live On Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/property_map/function_property_map.hpp>

struct VertexProps {
    bool _isVisible = true;
};

using BGType = boost::adjacency_list< //
    boost::vecS,                      //
    boost::vecS,                      //
    boost::bidirectionalS,            //
    VertexProps>;
using BGV = BGType::vertex_descriptor;

void hide_neighbours(BGV vertex, BGType& graph) {
    assert(vertex < num_vertices(graph));
    using boost::make_iterator_range;

    for (auto e : make_iterator_range(out_edges(vertex, graph)))
        graph[target(e, graph)]._isVisible = false;
    for (auto e : make_iterator_range(in_edges(vertex, graph)))
        graph[source(e, graph)]._isVisible = false;
}

int main() {
    BGType graph(8);
    add_edge(1, 5, graph);
    add_edge(5, 3, graph);
    add_edge(3, 7, graph);
    add_edge(7, 4, graph);

    add_edge(6, 5, graph);
    add_edge(2, 5, graph);

    auto annotate = boost::make_function_property_map<BGV>([&graph](auto v) {
        auto id = std::to_string(v);
        return graph[v]._isVisible ? id : "(" + id + ")";
    });

    print_graph(graph, annotate, std::cout << std::boolalpha);

    hide_neighbours(4, graph);
    print_graph(graph, annotate, std::cout << "\nNeigbours of 4 hidden:\n");

    hide_neighbours(5, graph);
    print_graph(graph, annotate, std::cout << "\nNeigbours of 5 hidden:\n");
}

Prints

0 --> 
1 --> 5 
2 --> 5 
3 --> 7 
4 --> 
5 --> 3 
6 --> 5 
7 --> 4 

Neigbours of 4 hidden:
0 --> 
1 --> 5 
2 --> 5 
3 --> (7) 
4 --> 
5 --> 3 
6 --> 5 
(7) --> 4 

Neigbours of 5 hidden:
0 --> 
(1) --> 5 
(2) --> 5 
(3) --> (7) 
4 --> 
5 --> (3) 
(6) --> 5 
(7) --> 4

Note that if you specify an invalid vertex you'll get:

sotest: /home/sehe/Projects/stackoverflow/test.cpp:17: void hide_neighbours(BGV, BGType&): Assertion `vertex < num_vertices(graph)' failed.

OTHER HINTS

If the above doesn't immediately remove/expose the issue then you have Undefined Behaviour. Perhaps graph is indeed a dangling reference, or graph has been modified in illegal ways (e.g. removing vertices that weren't cleared).

Feel free to post another question with more relevant code if you need help finding such causes.

user_853710
Related