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
– ggorlen, Commented Apr 23, 2021 at 22:29

ggorlen · Accepted Answer · 2021-04-23 22:30:51Z

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, 2021 at 22:30

ggorlen

59.4k8 gold badges119 silver badges173 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

henee Over a year ago

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 Over a year ago

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.

ggorlen Over a year ago

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 2 3 4

Collectives™ on Stack Overflow

Implementing a graph without a library in Python

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related