Algorithms
Algorithms copied to clipboard
Refactor Graph Code
This PR:
- Removes duplicate data structure code
- Removes
com.williamfiset.algorithms.graphtheory.IntStack
(in favor ofcom.williamfiset.algorithms.datastructures.stack.IntStack
) - Removes various copies of
MinIndexedDHeap
classes (in favor ofcom.williamfiset.algorithms.datastructures.priorityqueue.MinIndexedDHeap
)
- Removes
- Refactors various edge implementations defined in several graph algorithm classes
Many graph algorithm classes had their own versions of edge implementations that were not compatible with each other. It also introduces a significant amount of code duplication. To resolve these issues,Edge
,WeightedEdge
, andCostComparingEdge
classes are added and the graph algorithm implementations are updated accordingly.
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.
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.