Zettelkasten-Method / zkviz

Zettel Network Visualizer
MIT License
109 stars 19 forks source link

Drawing a large network is very slow #7

Closed achabotl closed 5 years ago

achabotl commented 5 years ago

It looks like drawing the layout with the Kamada is an O(N^2) algorithm. With just 2000 notes, it already takes 6 seconds to draw. I'll set an arbitrary threshold of 1000 notes for the Kamada algorithm and fall back to random layout otherwise.

2000

```python from uuid import uuid4 from time import perf_counter_ns import networkx as nx import numpy as np import matplotlib.pyplot as plt ns = np.geomspace(1, 2000) kamada = [] random = [] spring = [] for n in ns: g = nx.Graph() for node in range(int(n)): g.add_node(uuid4().int) start = perf_counter_ns() pos = nx.layout.kamada_kawai_layout(g) stop = perf_counter_ns() kamada.append((stop-start)/1e9) start = perf_counter_ns() pos = nx.layout.random_layout(g) stop = perf_counter_ns() random.append((stop-start)/1e9) # start = perf_counter_ns() # pos = nx.layout.spring_layout(g) # stop = perf_counter_ns() # spring.append((stop-start)/1e9) plt.plot(ns, kamada, label='kamada') plt.plot(ns, random, label='random') plt.xlabel('Network size') plt.ylabel('Seconds') plt.title('Duration to layout a network given different algorithms') plt.legend() plt.show() ```