Implementing a graph without a library in Python

Question

I'm new to Python and trying to build a directed graph without the use of a library. Can someone please confirm if I'm understanding this example correctly?

from collections import defaultdict 
class Graph:
    def __init__(graph):
        graph.dict = defaultdict(list)
    def add(graph,node,adjacent_node): 
        graph.dict[node].append(adjacent_node)    #line 6
        graph.dict[adjacent_node].append(node)    #line 7

graph = Graph()
graph.add('1','2') 
graph.add('2','5') 
graph.add('2','3') 
graph.add('4','5') 
graph.add('4','3') 
graph.add('6','4') 
graph.add('6','5')
print('Dictionary:',graph.dict)

_____
Output:
Dictionary: defaultdict(<class 'list'>, {'1': ['2'], '2': ['1', '5', '3'], '5': ['2', '4', '6'], '3': ['2', '4'], '4': ['5', '3', '6'], '6': ['4', '5']})

From my understanding, this example is building an undirected graph

• on line 6, they're adding the path from the original node to the adjacent node
• on line 7, they're adding the path from the adjacent node BACK to the original node

Is this correct?

Also I'm a little confused if these are the nodes, why do they need the path to the next node? Wouldn't the edges take care of that once I create an addEdges function, or does this function suffice for both adding nodes and edges?

example source

Answer 1

You're using an adjacency list representation of a graph here.

In your current implementation, add creates an undirected edge from node to adjacent_node. "Undirected edge" means if you're at node, you can transition to adjacent_node, and if you're at adjacent_node, you can transition to node. That's a bidirectional relationship.

add also creates these nodes if they don't already exist thanks to the defaultdict. Think of nodes as keys in your dict, and edges as an element inside a list associated with a node.

If you want a directed graph, that means add should only create one edge from the source to the destination:

def add(graph,node,adjacent_node): 
    graph.dict[node].append(adjacent_node)
    # graph.dict[adjacent_node].append(node)  # <- skip if you want a directed graph

No more functions are necessary to add here to represent a graph.