Why are graphics represented using dictionaries in Python?

Question

Python does not have direct support for graphs, but many sources say that they can be represented using dictionaries, for example.

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, this seems really inconvenient. Is it really better to say graph = {'x':['y'], 'y':['x']} rather than graph = {{'x', 'y'}} ?

Answer 1

Saving them as compounds makes it easy to navigate:

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

Try this with a set of two tuples. Not very easy, right?

Answer 2

If the graph is not oriented, the set of two-element sets is more suitable for its representation:

 graph = set() 

Add rib:

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

(note: you should use the frozenset () function, which is immutable because set () cannot be hashed due to its variability)

Check if the edge is in the graph:

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

Add more ribs:

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

Get edges for 'd':

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

However, for the latter operation, the presentation using dictionaries is more efficient in terms of time.

Answer 3

An undirected graph is a specific type of directed graph, where for each edge (a, b) there also exists (b, a).

Thus, you can implement it by saving edges twice (normal and inverse), but it is better to write a class so that it is consistent:

 from collections import defaultdict class UndirectedGraph: def __init__(self): self.edge = defaultdict(set) def add_edge(self, a, b): self.edge[a].add(b) self.edge[b].add(a) def remove_edge(self, a, b): self.edge[a].remove(b) self.edge[b].remove(a) def has_edge(self, a, b): return b in self.edge[a] or a in self.edge[b] def neighbours(self, a): return set(self.edge[a]) 

It is very simple, and depending on the operations you want to do, you may remove some method, or you may need to add others.

 >>> g=UndirectedGraph() >>> g.add_edge('a','b') >>> g.add_edge('a','c') >>> g.add_edge('c','d') >>> g.add_edge('a','d') >>> g.remove_edge('a','d') >>> g.has_edge('a','d') False >>> g.has_edge('a','c') True >>> g.neighbours('c') {'a', 'd'}