ENH: Optimize partial diagram generation

[nawtrey]

• Leverage partial diagram enumeration to preallocate arrays for partial diagrams/edge lists

• Update enumerate_partial_diagrams() to retrieve adjacency matrix using built-in NetworkX utilities

• Correct calls to enumerate_partial_diagrams()

• Add test test_partial_diagram_comparison to verify partial diagrams match the edge lists generated by running with return_edges=False

[codecov[bot]]

Codecov Report

Merging #40 (e6c8c98) into master (1642dcc) will decrease coverage by 0.00%. The diff coverage is 100.00%.

@@            Coverage Diff             @@
##           master      #40      +/-   ##
==========================================
- Coverage   98.02%   98.01%   -0.01%     
==========================================
  Files           9        9              
  Lines         759      757       -2     
==========================================
- Hits          744      742       -2     
  Misses         15       15              

Impacted Files	Coverage Δ
kda/diagrams.py	100.00% <100.00%> (ø)

[nawtrey]

I don't have proper benchmarking setup, but for a maximally connected 8-state diagram the updated code generates the 262144 partial diagrams in 29.9 seconds, down from 96.2 seconds (on master). So this is roughly 3x faster.

Here is the code I used to compare the performance:

import time
import numpy as np
import networkx as nx

from kda import graph_utils, diagrams

def get_K():
    N = 8
    K = np.ones((N, N), dtype=np.int32)
    np.fill_diagonal(K, 0)
    return K

def main(G):
    return diagrams.generate_partial_diagrams(G, return_edges=True)

if __name__ == "__main__":
    K = get_K()
    G = nx.MultiDiGraph()
    graph_utils.generate_edges(G, K)

    start_time = time.perf_counter()
    pars = main(G=G)
    end_time = time.perf_counter()

    elapsed = end_time - start_time
    print(f"Partial diagrams generated: {pars.shape[0]}")
    print(f"Elapsed time: {elapsed} s")

[nawtrey]

Tests passed and CI was green, merged.