#!/usr/bin/env python3 """CPU benchmark: NetworkX vs python-igraph on the same synthetic graph. Run: python3 replay.txt --output-dir NEW_DIRECTORY Requires CPython 3.14 on macOS arm64 with networkx already installed (measured: 3.6.1). python-igraph is imported if present; otherwise it is installed with pip into a temporary directory (needs access to PyPI; removed at exit). No key, no login, no paid API. The graph is generated in memory by deterministic integer arithmetic (LCG, no random module, no external files). Nothing is written except NEW_DIRECTORY. CPU only, no GPU. """ import argparse from datetime import datetime, timezone import gc import hashlib import json import os from pathlib import Path import platform import statistics import subprocess import sys import tempfile import time TRIALS = 5 N_NODES = 20000 N_RANDOM_EDGES = 80000 N_SOURCES = 10 TOOLS = ['networkx', 'igraph'] LOG = [] def log(msg): LOG.append(msg) print(msg, flush=True) def sha(data): return hashlib.sha256(data).hexdigest() def dump(path, value): with Path(path).open('x', encoding='utf-8') as f: json.dump(value, f, ensure_ascii=False, indent=2, allow_nan=False) class Lcg: def __init__(self, seed): self.s = seed def next(self, mod): self.s = (self.s * 6364136223846793005 + 1442695040888963407) % (1 << 64) return (self.s >> 33) % mod def make_graph(): rng = Lcg(12345) seen = set() edges = [] def add(a, b): if a == b: return key = (a, b) if a < b else (b, a) if key in seen: return seen.add(key) edges.append((key[0], key[1], 1 + rng.next(100))) for i in range(N_NODES): # ring keeps the graph connected add(i, (i + 1) % N_NODES) for _ in range(N_RANDOM_EDGES): add(rng.next(N_NODES), rng.next(N_NODES)) srng = Lcg(777) sources = [srng.next(N_NODES) for _ in range(N_SOURCES)] targets = [srng.next(N_NODES) for _ in range(N_SOURCES)] return edges, sources, targets def cpu_name(): try: return subprocess.run(['sysctl', '-n', 'machdep.cpu.brand_string'], capture_output=True, text=True, timeout=10, check=True).stdout.strip() or 'unavailable' except Exception as exc: return 'unavailable (%s)' % type(exc).__name__ def main(): ap = argparse.ArgumentParser() ap.add_argument('--output-dir', required=True) args = ap.parse_args() out = Path(args.output_dir) out.mkdir(parents=True, exist_ok=False) with tempfile.TemporaryDirectory() as tmp: try: import igraph # noqa: F401 igraph_source = 'already installed' except ImportError: r = subprocess.run([sys.executable, '-m', 'pip', 'install', '--quiet', '--target', tmp, 'igraph'], capture_output=True, text=True, timeout=600) log('pip install igraph rc=%d' % r.returncode) if r.returncode != 0: raise SystemExit('igraph install failed: ' + r.stderr[-500:]) sys.path.insert(0, tmp) igraph_source = 'pip install --target temporary directory (removed at exit)' run(out, igraph_source) def run(out, igraph_source): import igraph import networkx as nx started = datetime.now(timezone.utc).isoformat() edges, sources, targets = make_graph() edge_sha = sha(json.dumps(edges).encode()) environment = { 'platform': platform.platform(), 'machine': platform.machine(), 'python': sys.version, 'cpu': cpu_name(), 'logical_cpus': os.cpu_count(), 'versions': {'networkx': nx.__version__, 'igraph': igraph.__version__}, 'igraph_c_core': getattr(igraph, '__igraph_version__', None) and igraph.__igraph_version__, 'igraph_source': igraph_source, 'backend': 'native CPU only; pure-Python NetworkX vs C-core python-igraph; single thread; no GPU', } log('environment: %s' % json.dumps(environment, ensure_ascii=False)) def build_nx(): G = nx.Graph() G.add_weighted_edges_from(edges) return G def build_ig(): g = igraph.Graph(n=N_NODES, edges=[(a, b) for a, b, _ in edges]) g.es['weight'] = [w for _, _, w in edges] return g G = build_nx() g = build_ig() log('graph: nodes=%d edges nx=%d igraph=%d' % (G.number_of_nodes(), G.number_of_edges(), g.ecount())) # ---- operations (each returns something so work is not optimized away) def nx_bfs(): return [nx.single_source_shortest_path_length(G, s) for s in sources] def ig_bfs(): return [g.distances(source=s)[0] for s in sources] def nx_dij(): return [nx.single_source_dijkstra_path_length(G, s, weight='weight') for s in sources] def ig_dij(): return [g.distances(source=s, weights='weight')[0] for s in sources] def nx_path(): return [nx.dijkstra_path(G, s, t, weight='weight') for s, t in zip(sources, targets)] def ig_path(): return [g.get_shortest_paths(s, to=t, weights='weight', output='vpath')[0] for s, t in zip(sources, targets)] OPS = [ # id, loops per batch, nx fn, igraph fn, description ('bfs-distances', 1, nx_bfs, ig_bfs, '%d sources, unweighted single-source distances to all nodes' % N_SOURCES), ('dijkstra-distances', 1, nx_dij, ig_dij, '%d sources, weighted single-source distances to all nodes' % N_SOURCES), ('dijkstra-pair-path', 5, nx_path, ig_path, '%d source-target pairs, weighted shortest path (vertex list)' % N_SOURCES), ('build-graph', 3, build_nx, build_ig, 'construct graph from the same 100k-edge weighted list'), ] def path_weight(p): return sum(G[a][b]['weight'] for a, b in zip(p, p[1:])) # ---- validation (outside timing) cases = [] nxb, igb = nx_bfs(), ig_bfs() ok_bfs = all([d[i] for i in range(N_NODES)] == ig for d, ig in zip(nxb, igb)) nxd, igd = nx_dij(), ig_dij() ok_dij = all([d[i] for i in range(N_NODES)] == [int(x) for x in ig] for d, ig in zip(nxd, igd)) nxp, igp = nx_path(), ig_path() pw_nx = [path_weight(p) for p in nxp] pw_ig = [path_weight(p) for p in igp] ends_ok = all(p[0] == s and p[-1] == t for p, s, t in zip(nxp + igp, sources + sources, targets + targets)) gn, gi = build_nx(), build_ig() ok_build = (gn.number_of_edges() == gi.ecount() and gn.number_of_nodes() == gi.vcount() and sum(d['weight'] for _, _, d in gn.edges(data=True)) == sum(gi.es['weight'])) cases.append({'op': 'bfs-distances', 'distances_identical': bool(ok_bfs), 'sum_of_distances_sample': [sum(d.values()) for d in nxb]}) cases.append({'op': 'dijkstra-distances', 'distances_identical': bool(ok_dij), 'sum_of_distances_sample': [sum(d.values()) for d in nxd]}) cases.append({'op': 'dijkstra-pair-path', 'path_total_weights_networkx': pw_nx, 'path_total_weights_igraph': pw_ig, 'total_weights_identical': pw_nx == pw_ig, 'path_endpoints_correct': bool(ends_ok), 'paths_identical': [a == b for a, b in zip(nxp, igp)], 'path_lengths_networkx': [len(p) for p in nxp], 'path_lengths_igraph': [len(p) for p in igp]}) cases.append({'op': 'build-graph', 'node_edge_count_and_weight_sum_identical': bool(ok_build), 'nodes': gi.vcount(), 'edges': gi.ecount()}) for c in cases: log('validate %s' % json.dumps(c)) def batch(tool, op_row): _op, loops, fnx, fig, _desc = op_row fn = fnx if tool == 'networkx' else fig gc.collect() gc.disable() try: t0 = time.perf_counter_ns() for _ in range(loops): r = fn() del r return time.perf_counter_ns() - t0 finally: gc.enable() warmups, trials = [], [] for row in OPS: op, loops = row[0], row[1] for tool in TOOLS: warmups.append({'op': op, 'tool': tool, 'loops': loops, 'elapsed_ns': batch(tool, row)}) for trial in range(1, TRIALS + 1): order = TOOLS if trial % 2 == 1 else TOOLS[::-1] for pos, tool in enumerate(order, 1): ns = batch(tool, row) trials.append({'id': '%s-%s-r%d' % (op, tool, trial), 'op': op, 'tool': tool, 'trial': trial, 'order_position': pos, 'loops': loops, 'elapsed_ns': ns}) log('done %s' % op) summaries = [] for row in OPS: for tool in TOOLS: v = [t['elapsed_ns'] for t in trials if t['op'] == row[0] and t['tool'] == tool] summaries.append({'op': row[0], 'tool': tool, 'loops': row[1], 'median_batch_ns': statistics.median(v), 'min_batch_ns': min(v), 'max_batch_ns': max(v)}) raw = { 'topic_id': 'networkx-igraph-local-hikaku', 'request_id': 'req-20261022-065', 'started_at_utc': started, 'environment': environment, 'conditions': { 'trials': TRIALS, 'warmup_batches': 1, 'tool_order': 'alternating per trial', 'gc': 'cyclic GC disabled during timed loop', 'input': 'undirected weighted graph, %d nodes, ring + %d LCG random edges (deduplicated, no self loops), ' 'integer weights 1..100, edge list sha256 %s' % (N_NODES, N_RANDOM_EDGES, edge_sha), 'sources': sources, 'targets': targets, 'timed': 'loops calls per batch; each call runs the whole operation, results discarded', 'not_timed': 'graph generation, graph construction used for the query ops, import, validation, hashing', 'note': 'build-graph op times construction itself; query ops use prebuilt graphs', }, 'unit_map': {'trials[].elapsed_ns': 'ns'}, 'input': {'nodes': N_NODES, 'edges': len(edges), 'edge_list_sha256': edge_sha}, 'ops': [{'op': r[0], 'loops_per_batch': r[1], 'description': r[4]} for r in OPS], 'cases': cases, 'warmups': warmups, 'trials': trials, 'summaries': summaries, 'finished_at_utc': datetime.now(timezone.utc).isoformat(), } dump(out / 'raw.json', raw) dump(out / 'dependencies.json', {'versions': environment['versions'], 'python': sys.version, 'igraph_source': igraph_source}) with (out / 'run-log.txt').open('x', encoding='utf-8') as f: f.write('\n'.join(LOG) + '\n') log('wrote %s' % out) if __name__ == '__main__': main()