3 Ways To Represent Graphs in Python | Graph Theory With Python #2

In this video, you'll learn three ways to represent graphs in Python: as a tuple, as an adjacency list, and as an adjacency matrix. You'll see how Python's built-in data structures, such as lists and dictionaries, can help you represent graphs in a natural and Pythonic way.
CODE REPOSITORY
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
bit.ly/3vbITza
GRAPH THEORY WITH PYTHON SERIES
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
➢ Part 0: bit.ly/3qyGXNF
➢ Part 1: bit.ly/38pNioo
➢ Part 2: YOU ARE HERE
➢ Part 3: bit.ly/30QgTmJ
➢ Part 4: bit.ly/2TKNN7L
➢ Part 4.5: bit.ly/2THgseE
HELPFUL LINKS
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
➢ Python 3 Installation & Setup Guide: bit.ly/3bsYBxY
➢ The Amazing Mutable, Immutable Tuple by Al Sweigert: bit.ly/2OIavLC
SUPPORT ME
¯¯¯¯¯¯¯¯¯¯¯¯¯
My content is, and always will be, completely free. But your support goes a long way to motivate me to continue to produce top-notch math and programming content. You can tip me using any of the following links:
➢ Ko-Fi: ko-fi.com/davidamos
➢ PayPal: www.paypal.com/paypalme/somac...
OTHER LINKS
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
➢ My book "Python Basics: A Practical Introduction to Python 3" bit.ly/2OEnkD0
➢ My website: bit.ly/3q6BgI6
➢ My newsletter: bit.ly/35Bdgn3
➢ My Twitter: bit.ly/3t1gcTF
#graphdatastructures #pythonprogramming #discretemath #discretemathematics #adjacencymatrix #adjacencylist #adjacencymatric #mathematics #graphtheory

[@mahbuburrahmanturzo8712]

Clear voice, good & detailed explanation! This tutorial is a gem!

[@emmanuelonah4596]

The best video I have seen so far on graph representation in Python. Thank you!

[@DavidAmos]

Glad you enjoyed it!

[@kelechiegbosi6531]

Educative Video. Thanks for sharing.

[@cybercor3]

Very clear and detailed explanation. Thank you!!

[@pouyapargam5275]

Thank you for your smooth explanations. 👌👌

[@oanafocsa148]

This is great! Thank you very much!

[@soumya0307]

You are the reason I just started fascinating about graph theory ❤

[@hericklenin]

This is a very good presentation, thanks so much.

[@watcherofvideoswasteroftim5788]

Super helpful, thanks!

[@ScandGeek]

Great video! Regarding the adjacency matrix: for undirected graphs there is a problem that loops will be recorded twice. For this you should add a condition which checks if node1 == node2.

[@DavidAmos]

Absolutely true. I will address this in a future video when I deal with more graphs with loops. I'm also going to revisit the adjacency matrix when I talk about graphs with weighted edges. Thanks for watching, and I'm glad you liked it!

[@joaovaleriodesouzaneto8038]

Thanks, very very very goood!

[@hamzashariq9057]

for adjacency list,if we want to add the weight of nodes how can we do that?

[@soorajparakkattil2039]

Great video.

[@DavidAmos]

Thanks!

[@amirsharapov5556]

Amazing video!

[@DavidAmos]

Thanks! Glad you liked it 🙂

[@speakbaskar9620]

Thank you for helping your video sir. Can you send me radio labeling algorithm using python ?

[@mmokhtabad]

Nice, only if it was louder 😊

[@worldentropy]

Great work. How would you extend this concept to graphs in the 3D plain (e.g. a cuboid or 3D Torus) ? Thanks again.

[@InfiniteQuest86]

This is nice. It's been a while since I've seen graph theory, but I could have sworn the adjacency matrix of a directed graph had negative entries for edges going away from the vertex. Is that just for specific use cases?

[@DavidAmos]

Glad you liked it! There are indeed several different ways to define the adjacency matrix, and many are application dependent. I went with what I think is the most common. As far as -1s in the matrix, you might be thinking instead of Laplacian (en.m.wikipedia.org/wiki/Laplacian_matrix) or some weighted version of the adjacency matrix.

[@InfiniteQuest86]

@@DavidAmos I figured it out! It's called the incidence matrix: en.m.wikipedia.org/wiki/File:Incidence_matrix_-_directed_graph.svg . Which interestingly can calculate the Laplacian L = I(G)*I(G)^t.

[@andrejznamenacek8763]

What a shame there si not a way how to determine, whether we can get somehow through the edges from node x to node y.

[@sinnvollerkommentar263]

Cant wait for the next one. Guess I do a sleep() Typical mathematican. Keeping track of every click using bitly to analyse later. 😃

[@DavidAmos]

I haven't looked at the bitly stats for any of these links, haha! I just used it to shorten the links for the description.

[@miv_cleric]

+1 for namedtuple

[@DavidAmos]

One of my favorites in the standard library.

[@jamshaidmushtaq1811]

What if nodes are alphabets like 'A' or 'B'?

[@DavidAmos]

In that case you could map nodes to integers using something like dict(enumerate(nodes)) if you want the keys to be the numbers or dict(zip(nodes, range(len(nodes)))) to get the nodes as keys. That way you can build an adjacency matrix using the integers and then map them back to the node names as needed.

[@ViraLok]

🇫🇷️👍️

[@speakbaskar9620]

def radio_labeling(order, diameter): labels = [0] * order # Assign label 1 to vertex 0 labels[0] = 1 # Assign label 2 to the neighbors of vertex 0 for i in range(1, min(diameter + 1, order)): labels[i] = 2 # Assign labels to the remaining vertices for i in range(diameter + 1, order): # Check the labels of neighbors used_labels = set() for neighbor in range(i - diameter, i): used_labels.add(labels[neighbor]) # Find the smallest unused label j = 1 while j in used_labels: j += 1 # Assign the label to the current vertex labels[i] = j return labels # Example usage order = 10 # Number of vertices in the graph diameter = 3 # Diameter of the graph labels = radio_labeling(order, diameter) print(labels)

[@arnantaroy7468]

for me it says indices must be integers or slice, not list

[@DavidAmos]

Hey there! Could you share which line of code you're seeing this error on? I'm happy to help sort it out 🙂

[@arnantaroy7468]

@@DavidAmos hi thanks for replying, My code takes input of Edges and puts it in a list like this edges = [ [5,6], [2,3], [3,6] ] where the first value is the parent node and second value is the child. When I put this in graph adjacent list it works but because I need to perform operations I need to use adjacent matrix and when I try to do it it says indices just be integers or slice, not list

[@DavidAmos]

Hey @Arnanta Roy. Hmmmm... that's frustrating. Are you using the code for the adjacency matrix from this video? Just some thoughts: the input for the adjacency_matrix() function in the video needs to be the Graph data structure that I also defined in this video. I'm not sure of the best way to post code in KZbin comments. If you'd like, you can open an issue on the GitHub repository for the video series with all of your code (link here 👉github.com/somacdivad/graph-theory-with-python). That way I can take a look at your code and see if I can help you out!

[@arnantaroy7468]

@@DavidAmos #!/bin/python3 import math import os import random import re import sys from collections import namedtuple # # Complete the 'similarPair' function below. # # The function is expected to return an INTEGER. # The function accepts following parameters: # 1. INTEGER n # 2. INTEGER k # 3. 2D_INTEGER_ARRAY edges # nodes = [] straightlist = [] Graph = namedtuple("Graph", ["nodes", "edges"]) def similarPair(n, k, edges): for elem in edges: straightlist.extend(elem) node = straightlist[0] dfs(nodes, straightlist, node) print(nodes) def dfs(visited, edges, node): if node not in visited: nodes.append(node) for i in edges: dfs(nodes, edges, i) def adjacency_matrix(graph): """ Returns the adjacency matrix of the graph. Assumes that graph.node is equivalent to range(len(graph.nodes)) """ adj = [[0 for node in graph.nodes] for node in graph.nodes] array_length = len(edges) for edge in range(array_length): node1, node2 = edges[0], edges[1] adj[node1][node2] += 1 adj[node2][node1] += 1 return adj first_multiple_input = input().rstrip().split() n = int(first_multiple_input[0]) k = int(first_multiple_input[1]) edges = [] for _ in range(n - 1): edges.append(list(map(int, input().rstrip().split()))) similarPair(n, k, edges) G = Graph(nodes, edges) copy and paste

[@DavidAmos]

​@@arnantaroy7468 Thanks for providing your code. So, there are two issues that I see. First, in the for loop in the adjacency_matrix() function you are looping over range(array_length) which is basically a list from 0 to array_length - 1. In my original adjacency_matrix() function, I loop over the edges in the graph, not a list of numbers. So the for loop should start like this: for edge in edges: Next, you are using edges[0] and edges[1] to get the two nodes in each edge. But edges is a list of lists, so edges[0] return [5, 6] and edges[1] returns [2, 3]. Instead, you should use: node1, node2 = edge[0], edge[1] # Note there is so s at the end of edge That will use the edge from the current step in the loop (such as the edge [5, 6] on the first step) and assign 5 to node1 and 6 to node2. That will get rid of the TypeError you saw. However, you'll then get an IndexError. That's because after you input your edges to your program, the list of your nodes is [5, 6, 2, 3]. But my adjacency_matrix() function assumes that the nodes list is [0, 1, 2, 3] for a graph with four nodes (It's in the docstring: "Assumes that graph.nodes is equivalent to range(len(graph.nodes))"). I'm not sure if your graph is supposed to have four nodes or not, or if the node labels you input to your program are weights for each node or what. The adjacency matrix function from my video won't work with weighted graphs as-is. It'll need to be modified, if that is what you are working with here. Anyway, hope that helps at least a little bit!

[@yogeshbhatt4702]

Lord please give me strength so that I can bear this 36 minutes of mental pain

[@gradsys5482]

If nodes =[1,2,3,4] we will get an index error. You need to modify the adjacency _matrix function as follow: adj[graph.nodes.index(node1)][graph.nodes.index(node2)] To work with node 's index