dijkstra-runtime-analysis/codes/experiments/synthetic_data/analysis/processing_time_analysis.py

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import os
from sklearn.linear_model import LinearRegression
from sklearn.metrics import r2_score
from scipy.optimize import curve_fit

# Heap: Binary
#
# Runtime = Add + Extract-min + Relax-attempts + Relax-success
#         = VlogV * k1 + VlogV * k2 + E * k3 + \alpha * logV * k4
# (\alpha = relax_success)
#
# V increases -> Add, Extract-min, Relax-attempts, Relax-success all increases.
# Therfore, critical multicollinearlity occurs.
#
# To solve this problem, run regression per each V.
# Then V becomes constant.
#
# Runtime_V = (V) * (logV(k1 + k2)) + (E) * k3 + (\alpha) * (logV * k4)
#
# left part: call number, right part: cost per call
# call number is not concern in operation cost analysis.
# Important thing is that logV in right sides become constant.
#
# Final equation
# Runtime of specific V = V * l + E * k3 + \alpha * m
# 
# Using this equation, we can get l, k3, and m from each regression.
# l, m are defined like this.
# l = logV * (k1 + k2)
# m = logV * k4
# 
# 
# Final result
# l: cost per each add and extract-min (should scale with log2N)
# k3: cost per relax_attempt (should be equal across heaps)
# m: cost per decrease-key (should scale with log2N)
#
# (All base of log in this context is 2 due to binary heap.)


# contribution diagram
def contribution():
    contribution_records = []

    for n in nodes:
        g = df[df['nodes'] == n]
        g = g[g['relax_success'] > 0]
        
        if len(g) < 3:
            continue
        
        # 해당 N의 l, k3, m 가져오기
        row = results[results['N'] == n].iloc[0]
        l_val = row['l']
        k3_val = row['k3']  # k3_fixed
        m_val = row['m']
        
        # 각 항의 평균값 계산
        E_mean     = g['relax_attempts'].mean()
        alpha_mean = g['relax_success'].mean()
        
        Vl   = n * l_val           # V·l
        Ek3  = E_mean * k3_val     # E·k3
        am   = alpha_mean * m_val  # α·m
        
        total = Vl + Ek3 + am
        
        contribution_records.append({
            'N'       : n,
            'V·l'     : Vl,
            'E·k3'    : Ek3,
            'α·m'     : am,
            'total'   : total,
            'V·l %'   : Vl   / total * 100,
            'E·k3 %'  : Ek3  / total * 100,
            'α·m %'   : am   / total * 100,
        })

    contrib = pd.DataFrame(contribution_records)
    print("\n=== Contribution of each operations ===")
    print(contrib[['N','V·l %','E·k3 %','α·m %']].to_string(index=False))

    # 시각화
    fig, ax = plt.subplots(figsize=(9, 5))

    x = np.arange(len(contrib))
    w = 0.25

    ax.bar(x - w, contrib['V·l %'],  width=w, label='V·l  (add+extract)')
    ax.bar(x,     contrib['E·k3 %'], width=w, label='E·k3 (relax-attempt)')
    ax.bar(x + w, contrib['α·m %'],  width=w, label='α·m  (decrease-key)')

    ax.set_xticks(x)
    ax.set_xticklabels(contrib['N'].astype(int))
    ax.set_xlabel('N (nodes)')
    ax.set_ylabel('Contribution (%)')
    ax.set_title('Runtime contribution by operation')
    ax.legend()
    ax.grid(True, alpha=0.4)
    fig.tight_layout()
    fig.savefig(f"{save_folder}/contribution_vs_N.png", dpi=300)
    plt.close(fig)
    print(f"Saved: contribution_vs_N.png")


# l
def mean_l():
    return results["l"].mean()

def plot_l():
    fig, ax = plt.subplots(figsize=(7, 5))
    ax.plot(nodes, l_bin, marker="o", color="steelblue", label="l")
    ax.set_xlabel("N (nodes)")
    ax.set_ylabel("l — add + extract-min unit cost [s]")
    ax.set_title("l (add + extract-min unit cost) vs N")
    ax.legend(fontsize=8)
    ax.grid(True, alpha=0.4)
    fig.tight_layout()
    fig.savefig(f"{save_folder}/l_vs_N.png", dpi=300)
    plt.close(fig)
    print(f"Saved: {save_folder}/l_vs_N.png")

# k3
def regression_k3():
    n_arr = np.array(nodes, dtype=float)

    def exp_conv(n, a, b, c):
        return a * np.exp(-b * n) + c

    k3_arr = np.array(k3_bin, dtype=float)
    popt_ec, _ = curve_fit(exp_conv, n_arr, k3_arr,
                            p0=[float(k3_arr.max() - k3_arr.min()), 1/float(n_arr.mean()), float(k3_arr.min())],
                            maxfev=20000)
    
    return popt_ec

def plot_k3():
    n_arr = np.array(nodes, dtype=float)
    n_line = np.linspace(min(nodes), max(nodes), 300)

    def exp_conv(n, a, b, c):
        return a * np.exp(-b * n) + c

    k3_arr = np.array(k3_bin, dtype=float)
    popt_ec, _ = curve_fit(exp_conv, n_arr, k3_arr,
                            p0=[float(k3_arr.max() - k3_arr.min()), 1/float(n_arr.mean()), float(k3_arr.min())],
                            maxfev=20000)
    pred_ec = exp_conv(n_line, *popt_ec)
    r2_ec = r2_score(k3_bin, exp_conv(n_arr, *popt_ec))

    print("\n=== k3 exp_conv regression ===")
    print("a * exp(-b*N) + c")
    print(popt_ec)

    fig, ax = plt.subplots(figsize=(9, 5))
    ax.plot(nodes, k3_bin, marker="o", color="black", zorder=5, label="k3 (data)")
    ax.plot(n_line, pred_ec,  linestyle="--", linewidth=1.5, label=f"exp conv      R²={r2_ec:.4f}")
    ax.set_xlabel("N (nodes)")
    ax.set_ylabel("k3 — iteration cost per call [s]")
    ax.set_title("k3 (iteration unit cost) vs N — model comparison")
    ax.legend(fontsize=8)
    ax.grid(True, alpha=0.4)
    fig.tight_layout()
    fig.savefig(f"{save_folder}/k3_vs_N.png", dpi=300)
    plt.close(fig)
    print(f"Saved: {save_folder}/k3_vs_N.png")


# m
def regression_m():
    log_n = np.log2(np.array(nodes)).reshape(-1, 1)
    reg = LinearRegression().fit(log_n, m_bin)
    return (reg.coef_[0], reg.intercept_)

def plot_m():
    log_n = np.log2(np.array(nodes)).reshape(-1, 1)
    reg = LinearRegression().fit(log_n, m_bin)
    r2_bin = r2_score(m_bin, reg.predict(log_n))

    n_line = np.linspace(min(nodes), max(nodes), 300)
    log_n_line = np.log2(n_line).reshape(-1, 1)

    print("\n=== m log regression ===")
    print("m = a * log_2(N) + b")
    print(reg.coef_[0], reg.intercept_)

    fig, ax = plt.subplots(figsize=(7, 5))
    ax.plot(nodes, m_bin, marker="o", color="steelblue", label="binary k4")
    ax.plot(n_line, reg.predict(log_n_line), color="steelblue", linestyle="--", linewidth=1.5,
            label=f"fit (∝ log₂N)  R²={r2_bin:.3f}")
    ax.set_xlabel("N (nodes)")
    ax.set_ylabel("m — decrease-key cost per call [s]")
    ax.set_title("m (decrease-key unit cost) vs N")
    ax.legend(fontsize=8)
    ax.grid(True, alpha=0.4)
    fig.tight_layout()
    fig.savefig(f"{save_folder}/m_vs_N.png", dpi=300)
    plt.close(fig)
    print(f"Saved: {save_folder}/m_vs_N.png")


# Initial process
csv_file = "results/synthetic_data/raw/20260421_031740.csv"
save_folder = f"results/synthetic_data/derived/{os.path.splitext(os.path.basename(csv_file))[0]}/processing_time_analysis"
os.makedirs(save_folder, exist_ok=True)

df = pd.read_csv(csv_file)
nodes = sorted(df["nodes"].unique())
df = df[df["algorithm"] == "binary"]

records = []

for n in nodes:
    g = df[df["nodes"] == n]

    X = g[["relax_attempts", "relax_success"]].to_numpy()
    y = g["time"].to_numpy()

    model = LinearRegression().fit(X, y)
    r2 = r2_score(y, model.predict(X))

    l = model.intercept_ / n
    k3 = model.coef_[0]
    m = model.coef_[1]

    records.append({
        "N": n,
        "log2N": round(np.log2(n), 4),
        "l": l,
        "k3": k3,
        "m": m,
        "r2": r2,
        "data": len(g),
    })

results = pd.DataFrame(records)
grouped = results.set_index(["N"])
l_bin = grouped.loc[nodes, "l"].values
k3_bin = grouped.loc[nodes, "k3"].values
m_bin = grouped.loc[nodes, "m"].values

# Directly run
if __name__ == "__main__":
    r = results[["N","log2N","l","k3","m","r2","data"]]
    print("=== Regression Result ===")
    print(r.to_string(index=False))
    print("\n=== l representative value ===\n", results["l"].describe(), sep="")

    contribution()
    plot_l()
    plot_k3()
    plot_m()