Becksteinlab / kda

Python package used for the analysis of biochemical kinetic diagrams.
GNU General Public License v3.0
3 stars 1 forks source link

Potential performance improvement for `kda.diagrams.generate_flux_diagrams()` #27

Closed nawtrey closed 2 months ago

nawtrey commented 3 years ago

When working on PR #25 I wrote a variant of generate_flux_diagrams() that used a while-loop to count how many cycles were in each diagram, and when it detected more than 1, it broke the loop. This seemed to be faster, but I didn't have a chance to test it thoroughly so I decided to go with a more straight-forward approach.

The code:

# count how many cycles are in the flux diagram
n_cycles = 0
contains_only_1_cycle = True
for cycle in nx.simple_cycles(diag):
    # don't count loops between pairs of nodes
    if len(cycle) > 2:
        n_cycles += 1
        # `nx.simple_cycles()` returns the forward and reverse cycles
        # so for a single-cycle diagram, there will be 2 cycles returned
        if n_cycles > 2:
            contains_only_1_cycle = False
            break
# if there is exactly 1 unique cycle in the
# generated diagram, it is valid
if contains_only_1_cycle:
    # add valid diagram to flux diagram list
    flux_diagrams.append(diag)

This works well enough, but the performance improvement depends on the order of the cycles returned by nx.simple_cycles(). So for some cases it could be substantially faster, but others could be the same. I would need to see solid evidence that it improves performance before switching to this, so for now I'm just going to dump it here.

nawtrey commented 2 months ago

I'm going to close this. While this may lead to a performance improvement, I think the performance improvement would be somewhat random. Moreover, changes in b932af65a587497203c9e6ce29bad5ae6d83550e and 13f0dd3701496094e68281efe8888bac60e51868 and ad83127a03acf826f350c2381ded1896082030c7 and da4cd1c8262fe6106305eaa4834f0e0daf43ec4e may have made this moot.