erdogant / d3graph

Creation of interactive networks using d3 Javascript
https://erdogant.github.io/d3graph
Other
173 stars 25 forks source link

Support sparse data types / make this the internal data structure for the graph #21

Open aaronzo opened 1 year ago

aaronzo commented 1 year ago

Summary

When loading a graph into d3graph users must provide a dense adjacency matrix. This is inconvenient because most real-world graphs are sparse, and the dense representation is memory-ineffiecient.

Furthermore, the d3graph class saves a copy of the adjacency matrix for its internal representation of the data when the .graph() method is called - but everytime this self.adjmat is used, it seems to have been more natural to have stored it in a different structure. E.g set_edge_properties first converts the matrix into a dict (which is a sparse representation) and get_cluste_color effectively converts to an edgelist as far as I can tell (also sparse). Both of these operations are fairly inefficient and could have been avoided had a different structure been used to begin with. Adjacency matrices of graphs tend to be most useful when the algorithm we want to apply can be expressed as linear algebra, e.g. shortest paths, pagerank or traversals. Even in most of these situations, sparse matrices are usually the go-to for scalable solutions.

Impact

Possible Solutions

My preferred suggestion: since we already have networkx as a dependency, it would be wise to delegate the responsibility of storing the graph structure to that package, since:

erdogant commented 1 year ago

Great suggestions! I could use a little bit of help doing this ;-)