This is an incomplete list of areas where weighted-intervals could or should be improved.
The web version reruns the algorithm and replots the visualization whenever the user makes a change to the input “All intervals” textarea—after waiting 200 milliseconds, to maintain responsive typing.
That wait, even though it is only a fifth of a second, is less gratifying than an immediate change. At the same time, and more seriously, for problems of several hundred intervals or more, at least in some browsers on some systems, the time to update is much longer than 200 ms. Then characters entered into the textarea appear slowly, which is frustrating.
It seems the slowest step is plotting the intervals. As a stopgap measure, there could be a checkbox to disable that (or to disable doing it automatically). It would be nice to figure out a way to make the plotting significantly faster.
But the real, most important solution here is to allow the user keep entering input even once the computation has started, and for this to cancel the computation automatically—either if the input describes a different problem instance, or always. (The latter should be easier and also sufficient.)
The text-based output shows solution intervals’ start times, finish times, and weights. But the weights do not appear in the visualization.
Users might not always want the intervals to have weight labels in the plot, because of the increased visual noise when there are many intervals. But I think this should at least be an option.
Having to do with the way rounding is done, one often sees things like this:
OK. Total cost is 24.299999999999997, using 6 intervals.
That happens, in part, because floating point computations are performed, and the results stored, in binary, but results are reported in decimal.
When all the inputs have much lower precision, fewer figures should be retained.
As detailed in README.md, currently all
the Python code is in a single module. The reason is that, in the web version,
the way I’m loading the Python code into the WebAssembly CPython
interpreter provided by Pyodide runs it in the calling module. With multiple
modules, this situation would be confusing, even if there were no name clashes.
This can be fixed, though I’m hoping there’s an alternative to making a wheel and shipping it in the repository (and making sure to recreate it every time there is a change). I’m willing to do that if necessary.
It’s not that the single .py file is excessively long at this time.
Rather, having it all in one module may make it harder to find and read the
code for the algorithm.
The user should be able to specify the algorithm used for the topological sort. This can affect which solution is found, when there is more than one optimal subset.
Currently, I’m using Kahn’s algorithm with a queue (FIFO). It would be nice also to support recursive DFS with a reliable error message on stack overflow (which should be possible in the web version as it is running in a separate interpreter), DFS implemented iteratively with a state machine (which emits vertices in the same order as recursive DFS), Kahn’s algorithm with a stack (LIFO), and Kahn’s algorithm implemented recursively (this is an unusual way to implement Kahn’s algorithm but it can be done—it recurses from each of the DAG’s original roots).
In addition to supporting my O(n2) algorithm with a choice of topological sort algorithm as detailed above, it would be nice also to support the faster dynamic programming algorithm. The main reason to do so would be to showcase, and better elucidate the connection to, their algorithm. It would also allow users to compare results between algorithms, which can be different when there is more than one correct solution.
If visualization were also made much faster, than it is possible that runs would be noticeably faster with that algorithm.
At least the plot’s color scheme should be customizable. It might be worth having the size and spacing customizable too.
It would be nice if the plot were interactive, with numerical information about an interval appearing somewhere when the user hovers their mouse over an interval. (It would be good to facilitate keyboard interactivity too, for greater accessibility than with a mouse alone.)
Likewise, it would be nice if the user could resize the plot, zoom, scroll, and so forth.
But making the plot interactive might not be worth doing in the current design. Iodide, of which Pyodide originated as a part, does this, at least to some degree.
I’m not sure how to make the plot faster, other than by marshaling the information to create it from Python to JavaScript and using a JavaScript library. But it would be nice.
If successful, doing it that way would also likely improve responsiveness and facilitate plot interaction.
The DAG should also be visualized.
I tried drawing the DAG using NetworkX (which Pyodide conveniently supplies, as it does Matplotlib), but this was too slow. I also did not figure out a way to draw it with NetworkX that visualized it intuitively, though I think that is probably possible. It should appear roughly linearized in order to make sense to the user; roots should not be in the center.
This is another feature that might require more work to be done outside the WASM-ported CPython interpreter in order to perform well.
(If Kleinberg & Tardos’s algorithm is supported in the future, as suggested above, there would be no corresponding DAG shown for that.)