Efficient graph data structure

Illustrating how to implement efficient data structures for sparse graphs. When searching for graph representations or data structures for graphs one can immediately find references to the adjacency matrix and adjacency list representations - and typically their pros and cons are correctly discussed. Adjacency matrices are efficient to test whether two nodes are adjacent and to add and remove ties but they have an unacceptable memory consumption for sparse networks. Adjacency lists, in contrast, are memory-efficient but have a higher runtime to test adjacency and to remove edges. On the other hand, it seems to be not so prominently discussed that lists (as in adjacency list) can be replaced by more efficient data structures for representing sets. For instance, when maintaining sets of neighbors in hash sets one can easily implement data structures for graphs that are asymptotically optimal in memory consumption and runtime of the typical graph operations. The existence of efficient graph representations seems to be well known in some circles. In fact many free/open source software packages for graphs are efficient in memory consumption and runtime. Yet, software implementations are not the best way to illustrate the ideas behind efficient representations. Providing such an illustration is the intention of the slides efficient_network_graph_data structure.pdf. A simple, illustrating free/open source implementation of efficient graph representations in java is provided in GitHub under https://github.com/juergenlerner/netlearn (see the README file in that repository). A list of more complex, robust, and powerful packages for graphs and networks includes: - Java Universal Network/Graph Framework https://jrtom.github.io/jung/ - igraph (R, python, C) https://igraph.org/ - R packages network and networkDynamic (part of the statnet package) https://cran.r-project.org/web/packages/statne