Disjoint set / union find data structure
In many projects I find myself needing a disjoint set data structure https://en.wikipedia.org/wiki/Disjoint-set_data_structure. It would be very convenient if we had an implementation in SciPy. The codebase already contains two implementations, albeit not publicly accessible ones: https://github.com/scipy/scipy/blob/1d8b34b47d2b881ea904f4c9bf4c49b3fa36b29a... https://github.com/scipy/scipy/blob/8dba340293fe20e62e173bdf2c10ae208286692f... If there are no objections to its inclusion in SciPy I will write a PR. I tentatively propose to put it in scipy.cluster but other suggestions are welcome. Cheers, Peter
On Mon, Jul 20, 2020 at 2:37 PM Peter Larsen <peter.mahler.larsen@gmail.com> wrote:
In many projects I find myself needing a disjoint set data structure https://en.wikipedia.org/wiki/Disjoint-set_data_structure. It would be very convenient if we had an implementation in SciPy.
That seems like a reasonable and useful thing to add.
The codebase already contains two implementations, albeit not publicly accessible ones:
https://github.com/scipy/scipy/blob/1d8b34b47d2b881ea904f4c9bf4c49b3fa36b29a...
https://github.com/scipy/scipy/blob/8dba340293fe20e62e173bdf2c10ae208286692f...
If there are no objections to its inclusion in SciPy I will write a PR. I tentatively propose to put it in scipy.cluster but other suggestions are welcome.
Cluster, spatial and sparse all could make sense. If we foresee using this internally in all those modules, I think we'd have to put it in `sparse` or in `_lib`. The reason: no further dependencies between modules. cluster already depends on spatial, and spatial depends on sparse. Cheers, Ralf
On Mon, Jul 20, 2020 at 6:37 AM Peter Larsen <peter.mahler.larsen@gmail.com> wrote:
In many projects I find myself needing a disjoint set data structure https://en.wikipedia.org/wiki/Disjoint-set_data_structure. It would be very convenient if we had an implementation in SciPy.
The codebase already contains two implementations, albeit not publicly accessible ones:
https://github.com/scipy/scipy/blob/1d8b34b47d2b881ea904f4c9bf4c49b3fa36b29a...
https://github.com/scipy/scipy/blob/8dba340293fe20e62e173bdf2c10ae208286692f...
If there are no objections to its inclusion in SciPy I will write a PR. I tentatively propose to put it in scipy.cluster but other suggestions are welcome.
A union-find algorithm would be useful and has been proposed before, just never happened. In my implementations I also add a link in the set elements so that the disjoint sets can be iterated over, which was useful for my work but is not part of the usual implementations. IIRC, an implementation was shown in the discussion that took place when the graph algorithms were added to scipy. Chuck
participants (3)
-
Charles R Harris
-
Peter Larsen
-
Ralf Gommers