graph icon indicating copy to clipboard operation
graph copied to clipboard

connected_components called on empty filtered graph

Open pgerell opened this issue 5 years ago • 1 comments

The connected_components function returns (std::numeric_limits<comp_type>::max)() + 1 when called on a filtered graph with all vertices filtered out.

An example of this problem can be found here: https://godbolt.org/z/vWsG8j

If the line

    if (num_vertices(g) == 0) return 0;

was replaced with

   typedef typename boost::graph_traits<Graph>::vertex_iterator vi;
    std::pair<vi, vi> verts = vertices(g);
    if (verts.first == verts.second)
      return 0;

the function would work as expected.

pgerell avatar Oct 29 '20 14:10 pgerell

Searching for "if (num_vertices" in the source tree finds more algorithms that may not work as expected on filtered graphs.

pgerell avatar Nov 10 '20 17:11 pgerell