-
Notifications
You must be signed in to change notification settings - Fork 1
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
ENH: Update KDA partial and directional diagram generation algorithm #22
Comments
Here are some links where people have discussed algorithms for collecting all spanning trees:
|
* Changes directional diagram algorithm to use depth-first-search (i.e. `nx.dfs_tree`) to create the directional diagrams. Also uses the `nx.DiGraph.reverse` method to build the directional diagram with reversed edges and changes directional diagram return type for `return_edges=False` to a `nx.DiGraph`. * Removes private functions `diagrams._collect_sources` and `diagrams.get_directional_path_edges` * Move array-based edge flipping code into the `return_edges=True` code path * Addresses the directional diagram algo improvement portion of #22
With 61a1fcb merged I've checked off the directional diagram task. |
Upon further consideration I don't know if For example, using a maximally-connected 7-state diagram, the current algorithm generated the 16807 partial diagrams in roughly 1 second:
Comparatively, the new directional diagrams algo requires ~13 seconds to generate both the partial diagrams and directional diagrams:
So while it may be good to improve the partial diagram algorithm for other reasons, performance is probably not a main concern. If I can find any way to improve partial diagram algorithm performance I will probably close this issue. |
* Improves performance of `diagrams.generate_partial_diagrams` by efficiently filtering out invalid edges that do not span all nodes in the kinetic diagram. For small diagrams the performance benefit is small, but for more complex diagrams (e.g., the 8-state model of EmrE), there is a statistically significant performance increase. * Fixes #22
Problem
The primary limitation for graph complexity is the space complexity of functions like
kda.diagrams.generate_partial_diagrams()
andkda.diagrams.generate_directional_partial_diagrams()
. This is inherently related to issue #2, where this issue is focused on one part of that issue.This problem is 2 fold:
While 2. does contribute to the issue, the main issue is 1., especially for simpler input graphs. At the moment, the partial diagrams are generated by finding every possible combination of N-1 edges then discarding subgraphs that don't fit the definition of a partial diagram. Complete input graphs contain N(N-1)/2 unique edges, and thus have N^(N-2) partial diagrams (after doing the appropriate combinatorics). These yield approximately N! possibilities (using Stirling's approximation), so generating all possibilities is probably appropriate. But for simpler input graphs the number of partial diagrams is much less numerous so generating every possibility is likely not necessary.
Solution(s)
Before I list the possible solutions, I have to mention that in graph theory a "partial diagram" is known as a "spanning tree", so the solutions below will be using the graph theory language.
There are many solutions to this problem, many of which have formulas for calculating the space complexity of the algorithm. At the moment it isn't obvious which method is the best method, so I'm just going to dump links below.
I was going to list more, but the other articles/papers I have are all references in the above paper so for now I will leave it here.
Tasks
generate_partial_diagrams
generate_directional_diagrams
The text was updated successfully, but these errors were encountered: