Why are graphs represented using dictionaries in Python? [closed]

Question

Python does not have direct support for graphs but a lot of sources are saying they can be represented using dictionaries eg.

graph = { "a" : ["c"],
          "b" : ["c", "e"],
          "c" : ["a", "b", "d", "e"],
          "d" : ["c"],
          "e" : ["c", "b"],
          "f" : []
        }

since this is an undirected graph and dictionaries are directional mapping, it seems really inconcise. Is it really better to say graph = {'x':['y'], 'y':['x']} rather than graph = {{'x', 'y'}} ?

Answer 1

Storing them as connections makes it very easy to walk:

vertex = 'x'
connected_to = graph[vertex]
second_degree_connections = {p for subset in graph[p] for p in connected_to}

Try doing that efficiently with a set of two-tuples. Not very easy, right?

Answer 2

If the graph is undirected, a set of 2-elements sets is more suitable to represent it:

graph = set()

Add edge:

>>> graph.add(frozenset(('a', 'b')))

(note: you have to use frozenset() which is immutable, because set() is not hashable due to its mutability)

Check if an edge is in graph:

>>> {'b', 'a'} in graph
True

Add more edges:

>>> graph.add(frozenset(('a', 'c')))
>>> graph.add(frozenset(('c', 'd')))
>>> graph.add(frozenset(('d', 'e')))
>>> graph.add(frozenset(('d', 'f')))

Get edges touching 'd':

>>> set(x for x in graph if 'd' in x)
{frozenset({'c', 'd'}), frozenset({'f', 'd'}), frozenset({'d', 'e'})}

However, for the last operation, a representation using dictionaries is more efficient in terms of time.