Return type of Kosaraju

[dvd2000]

I'm writing some tests for Kosaraju's algorithm (these can potentially close #221), and this made me wonder about kosaraju() return type. Specifically, why does it return a std::vector<std::vector<Node<T>>>?

Wouldn't it be more appropriate to use std::unordered_set's or something similar?
While this could maybe slightly lower the performance, I think it would have much more sense:

• Kosaraju's algorithm returns the set of strongly connected components, that is, a partition of the vertices of the graph. These are just sets of vertices. And neither the sets in the partition or the vertices in each partition have some special ordering
• It would be consistent with the T_EdgeSet type (maybe we can even introduce a typedef for a set of vertices)
• It would allow for easier comparisons between vertex partitions and between individual components

What do you think about that?

[ZigRazor]

I think is correct, the return type should be an unorderer_set with a specific typedef.

[dvd2000]

Okay. I'd like to work on that, could you assign it to me?
And just to be sure, we should introduce a typedef for std::unordered_set<Node<T>> as T_NodeSet<T> and then the algorithm would return std::unordered_set<T_NodeSet<T>>?

[ZigRazor]

Sure! @dvd2000 I assigned it to you.

And just to be sure, we should introduce a typedef for std::unordered_set<Node> as T_NodeSet and then the algorithm would return std::unordered_set<T_NodeSet>?

yes, it's correct

[dvd2000]

I finally found some time to work on this and I have a few doubts about how to proceed:

• Working with unordered_set of unordered_set's is a bit tricky: one needs to provide some hash function for unordered_set's (as it has already been done for std::pair for Ford-Fulkerson) but it is in general not easy to come up with some good hashing for unordered containers (see here)
• Even for std::set of unordered_set's, one needs to provide the comparison operator, and I don't see any logical way of doing that in our case
• In every other part of the library, collections/sets of nodes are always stored as vector<Node<T>>. Should we maybe keep it like this also here? Or do you think it is really important to make this change? (I initially thought that it could be meaningful but I now see that there are some implementation issues)

I took a look at the approach used in the Boost graph library and they are using a map with vertices as keys and distinct labels for every strongly connected component as values. We can maybe do something similar here? But I think it would be important to keep consistency with the rest of the library.

If you want I can open a PR for the Kosaraju's tests in the meantime (keeping the function itself as it is for the moment)

[ZigRazor]

Yes, in the meantime you can open a PR for Kosaraju's Tests.
While regarding the return type, we can use also a simple typedef of vector of vector of node, just for simplicity.
I think we are trying to do something too much artificial for a return type that is a simple 2D vector.
In the typedef of the result of Kosaraju, we could manage the error for the undirected graph, with an error message, as done for other algorithm.