williamfiset / Algorithms

A collection of algorithms and data structures
MIT License
16.84k stars 4.29k forks source link

Refactor Graph Code #392

Open syoon2 opened 11 months ago

syoon2 commented 11 months ago

This PR:

williamfiset commented 11 months ago

The reason you see duplicate implementations throughout the repo is because it was done intentionally. Imo this makes it easier to understand and follow along rather than having to jump between multiple files. Additionally, it simplifies the process of 'copy/pasting' an algorithm into one's own project. I've personally relied on many of these algorithms in competitive programming, frequently resorting to copying and pasting them. The drawback of course is a bunch of duplicate code that begs to be cleaned up.

syoon2 commented 11 months ago

I agree that not having to jump between files makes understanding and following along easier. In this PR, however, I think that not much information is lost here - edge classes are simple data containers with the information of starting & ending vertices (and sometimes a weight). Because they are named in straightforward ways, I think even with this PR it would not be hard to follow along and understand. Plus, the data structure classes removed by this PR, IMO, are either conceptually trivial (in the case of IntStack) or requires spending dedicated time to understand (in the case of MinIndexedDHeap). Don't get me wrong - I am trying to say that they are strong, helpful data structures, but at the same time, the graph package might not be the right place for the user/reader to understand what they are doing.

There are other aspects to consider - because there are duplicate implementations, if one wants to mix uses of multiple algorithms, it requires setting up the data in the compatible format repeatedly (e.g., once for Dijkstra's then again for Bellman-Ford). This is tedious and (run)time-consuming, not to mention the issues with naming collision (especially in environments outside competitive programming).

Moreover, this repository's goal (as described in README) is "to demonstrate how to correctly implement common data structures and algorithms in the simplest and most elegant ways." I think performing this cleanup (as proposed by this PR) is more consistent with having a good software design and thus makes the code "more elegant," despite the drawbacks of this PR that you have brought up.