Closed
Description
Currently the parser uses the toposort_flatten from the toposort library
Line 367 in 19b3fe3
However, I noticed that this really slows down the parsing of files with many gates, e.g. this file.
After some investigation, I noticed that the implementation of topsort in the toposort library is very inefficient, as it is O(n^2) instead of O(n+m).
https://gitlab.com/ericvsmith/toposort/-/blob/master/src/toposort.py#L47
I suggest using the graphlib library, it should be enough to replace the above line with:
for lit in graphlib.TopologicalSorter(state.nodes).static_order():
What do you think?
Activity
mvcisback commentedon Dec 12, 2023
thanks for looking into this. Would you be open to creating a PR?
masinag commentedon Dec 12, 2023
I found out that graphlib is supported only since python 3.9, I'm looking for an alternative
masinag commentedon Dec 12, 2023
I can implement a simple topsort function instead of relying on an external library, what do you think?
It shouldn't be longer than 10-15 sloc