vf2_sub_graph_iso.hpp: fix bug when subgraph is filtered

[count0]

This fixes a bug when num_vertices() returns a value that does not match the actual number of vertices. This happens for instances of filtered_graph<>.

The fix involves looping over the graph to count the actual number of vertices. The performance overhead is negligible.

[jeremy-murphy]

Thanks for contributing a fix. Could I ask you to please also add a small unit test that demonstrates the new functionality? (I.e. the test should fail without your changes.)

I don't know the details of this algorithm -- do we only have to check if one graph is filtered, and not the other one?

[jakobandersen]

I don't know the details of this algorithm -- do we only have to check if one graph is filtered, and not the other one?

Both graphs can be potentially be filtered, but I think the PR covers it. The check in success() is for whether all the vertices in the "small" graph has been mapped, and with the initial vertex count checks that is enough.

[count0]

Thanks for contributing a fix. Could I ask you to please also add a small unit test that demonstrates the new functionality? (I.e. the test should fail without your changes.)

This problem has been noticed in graph-tool (which is built on top of BGL), for which there is a simple example where the code fails: https://git.skewed.de/count0/graph-tool/-/issues/715

If necessary I could translate it to a minimal C++ code.

[jeremy-murphy]

If necessary I could translate it to a minimal C++ code.

Yes, please, that is what I would like.

The develop branch appears to be green now, so we can actually merge this when it's done.

[jeremy-murphy]

@count0 do you have time to address the issues I commented on and add the unit test?