The Hunt for the Missing Data Type (Hacker News)
- Directed/undirected
- Simple/multi-edge
- Hypergraphs, where an edge can connect three or more nodes
- Ubergraphs, where edges can point to other edges
Category:Extensions and generalizations of graphs - Wikipedia
- Adjacency matrix:
[0 1 0; 0 0 1; 1 1 0]- Suitable for dense graphs
- Adjacency list:
[[b], [c], [a, b]] - Edge list:
[[a, b], [b, c], [c, a], [c, b]] - Adjacency array
- Doubly connected edge list (DCEL)
- Pointer-and-struct
- A set of these structs with references to each other
What about implementing node data? Edge data? Different types of nodes and edges? Most third party libraries roughly fall in one of two categories:
- Offer a single rich datatype that covers all use-cases at the cost of efficiency.
- NetworkX stores graph as a dict of dicts of dicts, so that both nodes and edges can have arbitrary data.
- Offer separate graph types for each representation, and rely on the user to store node and edge data separately from the graph type.
- petgraph
-
gryf: Graph data structure library aspiring to be convenient, versatile, correct and performant.
-
gamma: A graph library for Rust. (discontinued)
-
fast-graph: A fast, lightweight and extensible implementation of a graph data structure. (discontinued)
fast-graph: A fast, lightweight and extensible implementation of a graph data structure. : r/rust
- graphlib: Functionality to operate with graph-like structures
- NetworkX: Network Analysis in Python
- python-igraph: Python interface for igraph
- graph-tool: Efficent network analysis with python
- EasyGraph: An open source graph processing library, which covers advanced graph processing methods in structural hole spanners detection, graph embedding and several classic methods.
Python Graph Libraries - Python Wiki
Representations:
- A dict of dicts of dicts, so that both nodes and edges can have arbitrary data
adjacency_matrix()
MultiGraph:
add_edge()can specify the keys used to distinguish multiedges between a pair of nodes.