Broken support for unordered sets and multisets in adjacency_list graphs

[Thomas Claveirole <thomas@…>]

Hello,

The support for adjacency_list graphs using unordered sets and multisets is currently broken. I will attach a patch that solves this issues in this report.

Basically, several compounds are missing and there is a bug in edge_range(). Here is a detailed description of the issue:

• Container traits

container_traits, container_category, and iterator_stability specializations and overrides are missing for unordered_multiset and unordered_multimap, in pending/container_traits.hpp.

• parallel_edge_traits

parallel_edge_traits specializations are missing for hash_multisetS and hash_multimapS, in graph/adjacency_list.hpp.

• edge_range

edge_range() uses std::equal_range() on the node's out edge list. std::equal_range() expects its input to be ordered in ascending order. This precondition fails when using an unordered set or multiset for storing the edges.

As a solution, the proposed patch uses std::equal_range() by default, except on associative containers, for which it uses the container's equal_range() method (the equal_range() method is a requirement of associative containers).

Regards, Thomas Claveirole

[Thomas Claveirole <thomas@…>]

Patch that solves the described issue.

[Thomas Claveirole <thomas@…>]

Sorry, the previous patch has a minor bug. This one is correct.

[Jeremiah Willcock]

I agree with your bug. Could you please change the copyright message to you, though, since your patch adds so much code? With that I think I can apply it soon.

[Thomas Claveirole <thomas@…>]

Same as unordered-adjacency_list.2.patch with updated copyright notices.

[Thomas Claveirole <thomas@…>]

Replying to jewillco:

Could you please change the copyright message to you, though, since your patch adds so much code?

Sure. Here is a new patch. It adds a copyright line with my name and current year. Is this OK, or should I rather modify the existing lines?

[Jeremiah Willcock]

(In [60198]) Added in container_traits and adjacency_list patches to fix unordered container issues (patch from #3972); fixes #3972

[Jeremiah Willcock]

This should be fixed now -- I moved the equal_range stuff to container_traits, and it turns out that the iterators are actually unstable, not stable as was in the patch.

[Ignacy Gawedzki <i@…>]

Fix equal_range dispatch and container categories

[Ignacy Gawedzki <i@…>]

The actual dispatch functions for equal_range, as per r60698, don't work as expected. As a result std::equal_range is always used. The default dispatch function should take a container_tag as argument and not a template parameter, since the latter always takes precedence.

Besides, unordered_{set,multiset,map,multimap} should have their own tags which aren't subclasses of sorter_associative_container_tag.

The attached patch corrects those two issues.

[Jeremiah Willcock]

Could you please add a copyright notice with your name at the top of the file (i.e., rebuild your patch with that change) rather than updating the year on the existing notice? I should be able to apply your patch after that. Thank you.

[i@…]

Corrected copyright lines.

[Jeremiah Willcock]

(In [60999]) Applied another patch (unordered_equal_range_dispatch.2.patch) from #3972; fixes #3972