Support containing any type supported by STL

[nrkramer]

The templating of the graph library is a bit wonky. It doesn't allow users to use things like pointers or other custom data types due to static casting to an integer type in some copy operations.

We should audit the code and make sure that we can support any data type, just like STL containers (similarly to how std::vector supports containing any type).

[sbaldu]

I'm encountering this issue in a project that I'm working on where I'm using this library. I need the member data of the nodes to be a user defined class, but I get conversion errors in the best_first_search method.

[ZigRazor]

Can you provide an example of the code that does not work? And the error that you have encountered?

[sbaldu]

Hi, thanks for the reply.
Each node should represent a train station, which is defined here: https://github.com/Grufoony/ComplexTrains/blob/main/src/station.hpp
I've been able to fix most of the errors by overloading the iostream operators and adding a constructor. The errors remaining are these:

/usr/include/Graph/Graph.hpp: In instantiation of ‘CXXGraph::BestFirstSearchResult<T> CXXGraph::Graph<T>::best_first_search(const CXXGraph::Node<T>&, const CXXGraph::Node<T>&) const [with T = Station; CXXGraph::BestFirstSearchResult<T> = CXXGraph::BestFirstSearchResult_struct<Station>]’:
/usr/include/Graph/Graph.hpp:1613:26:   required from here
/usr/include/Graph/Graph.hpp:1634:10: error: no matching function for call to ‘std::priority_queue<std::pair<double, const CXXGraph::Node<Station>*>, std::vector<std::pair<double, const CXXGraph::Node<Station>*>, std::allocator<std::pair<double, const CXXGraph::Node<Station>*> > >, std::greater<std::pair<double, const CXXGraph::Node<Station>*> > >::push(std::pair<Station, const CXXGraph::Node<Station>*>)’
 1634 |   pq.push(std::make_pair(static_cast<T>(0), &source));
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13.1.1/queue:66,
                 from /usr/include/Graph/Graph.hpp:40:
/usr/include/c++/13.1.1/bits/stl_queue.h:738:7: note: candidate: ‘void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::pair<double, const CXXGraph::Node<Station>*>; _Sequence = std::vector<std::pair<double, const CXXGraph::Node<Station>*>, std::allocator<std::pair<double, const CXXGraph::Node<Station>*> > >; _Compare = std::greater<std::pair<double, const CXXGraph::Node<Station>*> >; value_type = std::pair<double, const CXXGraph::Node<Station>*>]’
  738 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/13.1.1/bits/stl_queue.h:738:30: note:   no known conversion for argument 1 from ‘std::pair<Station, const CXXGraph::Node<Station>*>’ to ‘const std::priority_queue<std::pair<double, const CXXGraph::Node<Station>*>, std::vector<std::pair<double, const CXXGraph::Node<Station>*>, std::allocator<std::pair<double, const CXXGraph::Node<Station>*> > >, std::greater<std::pair<double, const CXXGraph::Node<Station>*> > >::value_type&’ {aka ‘const std::pair<double, const CXXGraph::Node<Station>*>&’}
  738 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13.1.1/bits/stl_queue.h:746:7: note: candidate: ‘void std::priority_queue<_Tp, _Sequence, _Compare>::push(value_type&&) [with _Tp = std::pair<double, const CXXGraph::Node<Station>*>; _Sequence = std::vector<std::pair<double, const CXXGraph::Node<Station>*>, std::allocator<std::pair<double, const CXXGraph::Node<Station>*> > >; _Compare = std::greater<std::pair<double, const CXXGraph::Node<Station>*> >; value_type = std::pair<double, const CXXGraph::Node<Station>*>]’
  746 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/13.1.1/bits/stl_queue.h:746:25: note:   no known conversion for argument 1 from ‘std::pair<Station, const CXXGraph::Node<Station>*>’ to ‘std::priority_queue<std::pair<double, const CXXGraph::Node<Station>*>, std::vector<std::pair<double, const CXXGraph::Node<Station>*>, std::allocator<std::pair<double, const CXXGraph::Node<Station>*> > >, std::greater<std::pair<double, const CXXGraph::Node<Station>*> > >::value_type&&’ {aka ‘std::pair<double, const CXXGraph::Node<Station>*>&&’}
  746 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~

[ZigRazor]

Ok, I find the error!
The problem is that at line 1634 of Graph.hpp file:

CXXGraph/include/Graph/Graph.hpp

Line 1634 in daf32ed

pq.push(std::make_pair(static_cast<T>(0), &source));

The error is the static cast to T Type. In fact the priority queue is define here Graph.hhp:1630 :

CXXGraph/include/Graph/Graph.hpp

Line 1630 in daf32ed

std::priority_queue<pq_type, std::vector<pq_type>, std::greater<pq_type>> pq;

where pq_type is defined at Graph.hpp:1617 :

CXXGraph/include/Graph/Graph.hpp

Line 1617 in daf32ed

using pq_type = std::pair<double, const Node<T> *>;

So the queue accept for first parameter of pair a double and not a T type.
I think the correct line to substitute at Graph.hpp:1634 is:

pq.push(std::make_pair(0.0, &source));

Do you can correct it? And if it works, you can open PullRequest?

Thank you in advance

[sbaldu]

Sure, I'll get on it right away.

[sbaldu]

I've corrected line Graph.hpp:1634 as you said and it seems to work fine.
The tests in the test folder all pass normally and the compilation error in my project is fixed.
I'm opening the pull request.

[ZigRazor]

I merge the PR, but this issue is still available for a complete check of the initial request for issue

[nrkramer]

Thanks @sbaldu for opening the PR, and @ZigRazor for giving me the opportunity to check. It looks good, thanks!

[sbaldu]

Hi @nrkramer, I see that you've closed the issue.
I wanted to make sure that the problem was in fact solved so I checked the rest of the code and changed a few things (mainly using std::move when copying the data, because it would more efficient if the data type is not a basic type).
For what I've seen now the only restriction for the template parameter is that it should provide an overload of the equality and iostream operators.

Then I was adding a few test cases in each test file to make sure that all the algorithms work even for different data types.

I'm almost done and I should be able to open another PR in the next ours. If you think it's useful I'll continue.

[ZigRazor]

Yes I think is useful, in general increasing tests is ever good!

[ZigRazor]

I Think it's also useful work on mixed type graph (a graph that can contains different type of node or edges).
But it can be another issue.

[nrkramer]

Agreed, thanks @sbaldu .

This issue only concerns the basic functionality of using non-numeric types as the template parameter, so it's appropriate to close this.

For those cases you've mentioned, other issues can be opened.