Implemented Disjoint Set (Union-Find) Data Structure

Ramy-Badr-Ahmed commented 3 months ago

Contents:

DisjointSetNode Class: Represents individual nodes with data, rank, and parent attributes.
DisjointSet Class: Implements core methods:

findSet: Utilises path compression for representative lookup. unionSet: Applies union by rank to manage the merging of sets.
Unit Tests: Tests using PHPUnit to validate the correct behavior of the Disjoint Set structure. The tests cover different numbers of nodes and sets.

Compatibility: The implementation supports PHP 7.4 and above by omitting the mixed type hint, otherwise replace with mixed type hint as of PHP 8.0^.

Reference

Data Structures and Algorithms in C++, 2nd Edition

Ramy-Badr-Ahmed commented 2 months ago

Hi @darwinz Looking forward to your review 🙂

Md-Kasali commented 2 months ago

Move your DisjointSetTest.php file under the DataStructures/DisjointSets/ directory into the tests/DataStructures directory. The test files are organized under the tests/ directory.

darwinz commented 2 months ago

PHPUnit is also failing, so you'll want to fix that error as well.

1) DataStructures\DisjointSetTest::testFindSet
Error: Class 'DisjointSet' not found

/home/runner/work/PHP/PHP/tests/DataStructures/DisjointSetTest.php:16
phpvfscomposer:///home/runner/work/PHP/PHP/vendor/phpunit/phpunit/phpunit:106

Ramy-Badr-Ahmed commented 2 months ago

This is great, thanks for the contribution!

There are a few small linting issues, found by the GitHub Actions linter we use in this repo. You can also run PHPCBF to automatically fix these types of issues in the future.

Thanks! I have committed your linting changes and considered the rest of the PHPCP remarks.

Ramy-Badr-Ahmed commented 2 months ago

PHPUnit is also failing, so you'll want to fix that error as well.

1) DataStructures\DisjointSetTest::testFindSet
Error: Class 'DisjointSet' not found

/home/runner/work/PHP/PHP/tests/DataStructures/DisjointSetTest.php:16
phpvfscomposer:///home/runner/work/PHP/PHP/vendor/phpunit/phpunit/phpunit:106

Resolved following the exisitng pattern in tests/DataStructures.

Testing started at 13:48 ...
PHPUnit 9.6.20 by Sebastian Bergmann and contributors.

Time: 00:00.004, Memory: 4.00 MB

OK (1 test, 36 assertions)

Process finished with exit code 0

darwinz commented 2 months ago

The test is still failing. Please run your test locally and make sure it's passing.

Ramy-Badr-Ahmed commented 2 months ago

The test is still failing. Please run your test locally and make sure it's passing.

Thanks, @darwinz

It had to do with the mixed data type. Changed it to type annotations for PHP 7.4.

Here's the successful local output of composer test or vendor/bin/phpunit tests:

> vendor/bin/phpunit tests
0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,1.2200160415122E+19,1.9740274219868E+19,3.194043463499E+19,5.1680708854858E+19,8.3621143489848E+19,1.3530185234471E+20,2.1892299583456E+20,956722026041PHPUnit 9.6.20 by Sebastian Bergmann and contributors.

...............................................................  63 / 151 ( 41%)
............................................................... 126 / 151 ( 83%)
.........................                                       151 / 151 (100%)

Time: 00:00.959, Memory: 60.00 MB

OK (151 tests, 342 assertions)

Successful output of vendor/bin/phpunit tests/DataStructures/DisjointSetTest.php

vendor/bin/phpunit tests/DataStructures/DisjointSetTest.php
PHPUnit 9.6.20 by Sebastian Bergmann and contributors.

.                                                                   1 / 1 (100%)

Time: 00:00.009, Memory: 4.00 MB

OK (1 test, 36 assertions)

Should be ok for the build now.

GitHub Actions

PHPCS

DIRECTORY.md

build

All tests and workflows (in my forked repository) have passed.

Can you please rerun it here? 🙂

darwinz commented 2 months ago

Thank you!

TheAlgorithms / PHP

Implemented Disjoint Set (Union-Find) Data Structure #160