Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
aaronzo opened this issue Jan 15, 2023 · 1 comment
Labels
enhancement New feature or request question Further information is requested

Comments

@aaronzo
Copy link

aaronzo commented Jan 15, 2023

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

  • d3graph is limiting the sizes of graphs it supports by enforcing an inefficient input type.
  • d3graph is increasing its runtime due applying inefficient operations on this dense data structure when generating a figure

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:

  • it's a trusted, respected and mature project - no doubt they have applied more thought on efficiency than we could here. It's also unlikey to find bugs
  • its API is very stable
  • users will be familiar with the API
  • NetworkX already has great conversion functions to/from other data structures, meaning less inefficient conversions and boilerplate here.
  • would make the python portion of the code much shorter and more readable (adjmat2* methods could be removed)
@erdogant erdogant added enhancement New feature or request question Further information is requested labels Jan 16, 2023
@erdogant
Copy link
Owner

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request question Further information is requested
Projects
None yet
Development

No branches or pull requests

2 participants