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

Your understanding is correct up until the last paragraph. `add` already adds edges, along with nodes if they don't already exist. If you want a digraph (directed graph), remove line 7. — ggorlen, Apr 23 '21 at 22:29

score 1 · Accepted Answer · answered Apr 23 '21 at 22:30

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.

answered Apr 23 '21 at 22:30

ggorlen

44,755
7
76
106

Thank you, your explanation clears a lot up. I'm referring to this example for a project I'm working on and the data is unordered so I think this will work. – henee Apr 23 '21 at 22:52
Will do thanks! Additionally, would you say that using an adjacency matrix would be a better approach for a directed graph? The wiki page you referenced mentions it as an alternative to adjacency lists. – henee Apr 23 '21 at 23:05
There are many ways to represent graphs, and it's application-dependent so neither is objectively better for a directed graph on all use cases. See [1](https://stackoverflow.com/questions/2218322/what-is-better-adjacency-lists-or-adjacency-matrices-for-graph-problems-in-c) [2](https://cs.stackexchange.com/questions/79322/when-are-adjacency-lists-or-matrices-the-better-choice) [3](https://stackoverflow.com/questions/6625618/graphs-representation-adjacency-list-vs-matrix) [4](https://stackoverflow.com/questions/36725723/adjacency-matrix-vs-adjacency-list-for-directed-weighted-graph) – ggorlen Apr 23 '21 at 23:07

Implementing a graph without a library in Python

1 Answers1