In modern languages with builtin map/set data structures,
it's simplest to use "adjacency sets" representation.
The whole graph is a hash (or another map like a tree); its keys are nodes and values are sets of neighbour nodes for that node:
Using maps/sets allows using any comparable objects to denote nodes (not just consecutive integers), allows ~O(1) additions/removals of nodes and edges, and ~O(1) lookups for specific edge, like a matrix.
It's still space-efficient for sparse graphs.
Many operations are very natural:
nodes = set(G)
all_edges_iterator = ((src, dst) for src in G for dst in G[source])
High-level set operations, like union also come handy for many algorithms.
Undirected graphs can be modeled simply as directed with edges in both directed.
This allows code expecting a directed graph to simply work.
With directed graph, there is one expensive awkward operation: finding incoming edges to specific node. If important could keep 2 sets per node.
If you want labeled edges, just replace the inner sets with {dest: info, ...} maps. (If you want labeled nodes, having separate {node: info} map is probably easiest.)
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
In modern languages with builtin map/set data structures,
it's simplest to use "adjacency sets" representation.
The whole graph is a hash (or another map like a tree); its keys are nodes and values are sets of neighbour nodes for that node:
Last directed graph diagram. Python syntax.
G = {
0: {1},
1: {2},
2: {},
3: {0, 1, 2, 5},
4: {1},
5: {},
}
Using maps/sets allows using any comparable objects to denote nodes (not just consecutive integers), allows ~O(1) additions/removals of nodes and edges, and ~O(1) lookups for specific edge, like a matrix.
It's still space-efficient for sparse graphs.
Many operations are very natural:
nodes = set(G)
all_edges_iterator = ((src, dst) for src in G for dst in G[source])
High-level set operations, like union also come handy for many algorithms.
Undirected graphs can be modeled simply as directed with edges in both directed.
This allows code expecting a directed graph to simply work.
With directed graph, there is one expensive awkward operation: finding incoming edges to specific node. If important could keep 2 sets per node.
If you want labeled edges, just replace the inner sets with {dest: info, ...} maps. (If you want labeled nodes, having separate {node: info} map is probably easiest.)