2 ms·
> it's very unlikely that knowing how to do a topological sort will go out of fashion It is also vanishingly unlikely I’ll ever have to do a topological sort.
by Aeolun 5y ago
> it's very unlikely that knowing how to do a topological sort will go out of fashion
It is also vanishingly unlikely I’ll ever have to do a topological sort. 15 years and counting. Meanwhile, being able to read and understand a bit of kotlin has proven useful several times.
- layer8 5y agoTopological sort implicitly comes up anytime you implement a depth-first search on a graph that isn’t 100% guaranteed to be cycle-free. Checking for cycles in a depth-first search is basically the same as topological sort. Having to implement something like that comes up roughly every 3 years for me.
- aeroevan 5y agoBut how often are you actually writing an implementation vs. calling a method from a graph library? Knowing when you need a topological ordered list of vertices is (in my opinion) more useful than knowing how to implement tsort.
- layer8 5y ago> how often are you actually writing an implementation vs. calling a method from a graph library? Every time. Because of several reasons: 1. Transforming the graph (which is usually not explicitly represented, but rather the result of navigating entities using some existing API) to the representation required by the graph library is more complex than just implementing the search and the cycle check yourself (it's usually just insertion into a set and checking if the element was already contained). 2. Often there are additional actions you want to take during the traversal, and diagnostics you want to output, which is either impossible or difficult/convoluted to integrate with a graph library. 3. Dependencies incur maintenance cost and should not be added lightly. Adding a graph library just for a simple topological sort is usually not a good trade-off. Knowing how topological sort is implemented is necessary to make the right design decision here. Otherwise you end up adding a big dependency and convoluted glue code just because you didn't realize how straightforward and maintenance-friendly a custom implementation tailored to the present use-case could be. Or, in other cases, you may end up implementing a custom algorithm without realizing that it actually corresponds closely to an existing graph algorithm (which would help you double-check your implementation or replace it with an existing library).