boostorg / graph

Boost.org graph module
http://boost.org/libs/graph
323 stars 206 forks source link

connected_components called on empty filtered graph #231

Open pgerell opened 4 years ago

pgerell commented 4 years ago

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 commented 3 years ago

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