Visitor object is copied

[CodeFinder2]

Hi!

First of all: great work!

I am using your algorithm (as part of the boost library) very similiar to the example in hawick_circuits.cpp. The problem is that I am storing additional state in my (modified) cycle_printer struct and that state does not seem to change or, more precisely, the changes do not seem to persist/survive the call: boost::hawick_circuits(graph, visitor). More specifically, I am analyzing the detected cycles in my visitor and if a certain type of cycle is detected, I am setting a member variable within the cycle_printe::cycle() method to true. After running the algorithm, that variable is still false (as initialized in my visitor's constructor).

After taking a look at the source code, it seems that this line may cause this issue. Is it intended that the visitor parameter is passed by value (as even stated in the code comment) and not by reference (&)? Do you know whether it is safe to simply change this to create a call by reference here, like (see 63009c7f961f2984faac7e4055892bbe4c4ba9d8):

void call_hawick_circuits(Graph const& graph,
                          Visitor& visitor,
                          VertexIndexMap const& vertex_index_map) { ... }

? IMHO, the fact that a visitor survives a call of the associated algorithm is one of the advantages of having a "stateful callback" (= visitor) in general.

If this is really a bug, it should also be fixed in the boost implemenation. ;-)

Glad to hear your opinion on that, thanks you!

Edit: I just tested this fix and it seems to work fine.

Edit2: Would it be possible to let cycle_printer::cycle() return a boolean indicating whether to continue (true) or to abort (false) the search for elementary circuits? Would allow an early-abort which is useful in many situations. I guess this line would need an update, correct? However, a simple return true doesn't seem to be enough :-D (since there's more logic "above" circuit() that needs to be aborted as well).

[ldionne]

Sorry for the delay, I'm not monitoring this actively.

I don't remember why I decided to pass the visitor by value, however it looks intentional given the comment. I should have documented the reason, if any.

However, would it be possible for you to pass a reference_wrapper to the visitor instead? This is the canonical way of funnelling things by reference in generic algorithms.

Edit2: Would it be possible to let cycle_printer::cycle() return a boolean indicating whether to continue (true) or to abort (false) the search for elementary circuits? [...]

It seems like it would also require changing call_hawick_circuits to stop when the sub-algorithm reports that it wants to stop. I think this can be implemented. Do you still have a need for this?

[CodeFinder2]

Thanks for your reply! Can you elaborate on the idea redarding the reference_wrapper a bit? Never used it before. Do you mean something like (line 290):

void call_hawick_circuits(Graph const& graph,
                          std::reference_wrapper<Visitor> visitor,
                          VertexIndexMap const& vertex_index_map) { ...

? If yes, I just tested this modifcation and it caues some weird compiler errors (I guess many more lines need to be adapted for this to work but I am neither an expert regarding this Boost template voodoo nor regarding the std::reference_wrapper, sorry) :frowning_face: It would be really great, if you can find the time to add this (or at least, explain in more detail what to do).

Yes, I still have a need for it. I would really appreciate if you could add this functionality!

[CodeFinder2]

Any updates on this? :thinking: :see_no_evil:

[ldionne]

Sorry, not sure this is still relevant, but what I meant was to call the algorithm like so (for example from hawick_circuits.cpp):

cycle_printer<std::ostream> visitor(std::cout);
boost::hawick_circuits(graph, std::ref(visitor));

This should pass a std::reference_wrapper to hawick_circuits and avoid making copies.

[CodeFinder2]

This causes a compiler error (tested with your example hawick_circuits.cpp):

$ make
g++ -Wall -Wextra -pedantic -I `pwd` -o hawick_circuits hawick_circuits.cpp
In file included from hawick_circuits.cpp:10:
.../hawick_circuits-master/boost/graph/hawick_circuits.hpp: In instantiation of ‘bool boost::hawick_circuits_detail::hawick_circuits_from<Graph, Visitor, VertexIndexMap, Stack, ClosedMatrix, GetAdjacentVertices>::circuit(boost::hawick_circuits_detail::hawick_circuits_from<Graph, Visitor, VertexIndexMap, Stack, ClosedMatrix, GetAdjacentVertices>::Vertex, boost::hawick_circuits_detail::hawick_circuits_from<Graph, Visitor, VertexIndexMap, Stack, ClosedMatrix, GetAdjacentVertices>::Vertex) [with Graph = boost::directed_graph<>; Visitor = std::reference_wrapper<cycle_printer<std::basic_ostream<char> > >; VertexIndexMap = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, boost::property<boost::vertex_index_t, unsigned int, boost::no_property>, boost::property<boost::edge_index_t, unsigned int, boost::no_property>, boost::no_property, boost::listS>, unsigned int, const unsigned int&, boost::vertex_index_t>; Stack = std::vector<void*, std::allocator<void*> >; ClosedMatrix = std::vector<std::vector<void*, std::allocator<void*> >, std::allocator<std::vector<void*, std::allocator<void*> > > >; GetAdjacentVertices = boost::hawick_circuits_detail::get_all_adjacent_vertices; boost::hawick_circuits_detail::hawick_circuits_from<Graph, Visitor, VertexIndexMap, Stack, ClosedMatrix, GetAdjacentVertices>::Vertex = void*]’:
.../hawick_circuits-master/boost/graph/hawick_circuits.hpp:271:9:   required from ‘void boost::hawick_circuits_detail::hawick_circuits_from<Graph, Visitor, VertexIndexMap, Stack, ClosedMatrix, GetAdjacentVertices>::operator()(boost::hawick_circuits_detail::hawick_circuits_from<Graph, Visitor, VertexIndexMap, Stack, ClosedMatrix, GetAdjacentVertices>::Vertex) [with Graph = boost::directed_graph<>; Visitor = std::reference_wrapper<cycle_printer<std::basic_ostream<char> > >; VertexIndexMap = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, boost::property<boost::vertex_index_t, unsigned int, boost::no_property>, boost::property<boost::edge_index_t, unsigned int, boost::no_property>, boost::no_property, boost::listS>, unsigned int, const unsigned int&, boost::vertex_index_t>; Stack = std::vector<void*, std::allocator<void*> >; ClosedMatrix = std::vector<std::vector<void*, std::allocator<void*> >, std::allocator<std::vector<void*, std::allocator<void*> > > >; GetAdjacentVertices = boost::hawick_circuits_detail::get_all_adjacent_vertices; boost::hawick_circuits_detail::hawick_circuits_from<Graph, Visitor, VertexIndexMap, Stack, ClosedMatrix, GetAdjacentVertices>::Vertex = void*]’
.../hawick_circuits-master/boost/graph/hawick_circuits.hpp:317:17:   required from ‘void boost::hawick_circuits_detail::call_hawick_circuits(const Graph&, Visitor, const VertexIndexMap&) [with GetAdjacentVertices = boost::hawick_circuits_detail::get_all_adjacent_vertices; Graph = boost::directed_graph<>; Visitor = std::reference_wrapper<cycle_printer<std::basic_ostream<char> > >; VertexIndexMap = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, boost::property<boost::vertex_index_t, unsigned int, boost::no_property>, boost::property<boost::edge_index_t, unsigned int, boost::no_property>, boost::no_property, boost::listS>, unsigned int, const unsigned int&, boost::vertex_index_t>]’
.../hawick_circuits-master/boost/graph/hawick_circuits.hpp:327:46:   required from ‘void boost::hawick_circuits_detail::call_hawick_circuits(const Graph&, Visitor&&) [with GetAdjacentVertices = boost::hawick_circuits_detail::get_all_adjacent_vertices; Graph = boost::directed_graph<>; Visitor = std::reference_wrapper<cycle_printer<std::basic_ostream<char> > >]’
.../hawick_circuits-master/boost/graph/hawick_circuits.hpp:352:6:   required from ‘void boost::hawick_circuits(Graph&&, Visitor&&) [with Graph = boost::directed_graph<>&; Visitor = std::reference_wrapper<cycle_printer<std::basic_ostream<char> > >]’
hawick_circuits.cpp:93:52:   required from here
.../hawick_circuits-master/boost/graph/hawick_circuits.hpp:236:26: error: ‘class std::reference_wrapper<cycle_printer<std::basic_ostream<char> > >’ has no member named ‘cycle’
  236 |                 visitor_.cycle(const_cast<Stack const&>(stack_), graph_);
      |                 ~~~~~~~~~^~~~~
make: *** [Makefile:12: external_test_suite] Error 1

Anyway, I'll stick to my patched code version although this is not ideal. Thanks nonetheless!

[ldionne]

This causes a compiler error (tested with your example hawick_circuits.cpp):

That's not intentional, this should be fixed by boostorg/graph#249.

[CodeFinder2]

Ah ok, nice to know about that fix. I was using default Ubuntu (20.04) Boost packages. ;-)

[ldionne]

I literally just made that fix, so it's expected that you were not seeing it. It'll take some time to hit your distro.