Introduction to Graph theory:

Introduction

Graphs are an important data structure extensively used in computer science and mathematics, usually to model connected objects.

A graph is composed of nodes and the edges connecting them.

Definitions:

We can define a graph mathematically as such: A graph $G=(V,E)$ is defined by a list of nodes (vertices) : $(v_{i})$ and a list of edges: $(e_{j})$. An edge is defined as a pair of ordered or unordered nodes which are then described as adjacent to each other.

When the edges of a graph are composed of ordered nodes, the graph is then called directed, otherwise it's undirected.

The order of a graph is the number of it's vertices, and it's size is the number of it's edges. The degree of a vertice is the number of it's adjacent vertices and the degree of a graph is the maximum degree of it's vertices.

Example of graphs:

Practical representations of graphs:

Graphs are usually represented in code by one of these two means, we'll use this following graph as our example:

Adjacence List:

Each vertices has a list of it's own adjacent vertices and therefore a graph can be fully described by a list of the adjacent vertices of every vertices.

graphList = [
        [2,3,5],
        [1,4],
        [2],
        [1,2],
        [4]
        ]
print("Adjacence list of our graph is:", graphList)

Adjacence list of our graph is: [[2, 3, 5], [1, 4], [2], [1, 2], [4]]

However if we want to identify the nodes differently from using the list indexes we can use a hashMap:

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
        }
print("Adjacence list of our graph is:", graph)

Adjacence list of our graph is: {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']}

Adjacence matrix:

Adjacence matrix: For a graph whose vertices can be indexed with integers, if it's order is noted as $n$, it can be fully represented with a (nxn) matrix such as that the coefficient at $(i,j)$ equals 1 if $(i,j)$ is an edge of the graph and 0 otherwise. Mathematically we write : $(M_{i,j})_{1\leq i,j \leq n}$ is the adjacence matrix of the graph $G=(V,E)$ if and only if $\forall i,j \in [|1,n|], M(i,j)=1$ if $(i,j) \in E$, else $M(i,j) = 0$

We can represent that in Python either by using a bi-dimensional array or a numpy array:

graphMat=[
       [0,1,1,0,1],
       [1,0,0,1,0],
       [0,1,0,0,0],
       [1,1,0,0,0],
       [0,0,0,1,0],
      ]
print("Adjacence Matrix of our graph is:",  graphMat)

Adjacence Matrix of our graph is: [[0, 1, 1, 0, 1], [1, 0, 0, 1, 0], [0, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 0]]

import numpy as np 

graphMatnp = np.array([
                    [0,1,1,0,1],
                    [1,0,0,1,0],
                    [0,1,0,0,0],
                    [1,1,0,0,0],
                    [0,0,0,1,0],
                ])
print("Adjacence Matrix of our graph is:",  graphMatnp)

Adjacence Matrix of our graph is: [[0 1 1 0 1]
 [1 0 0 1 0]
 [0 1 0 0 0]
 [1 1 0 0 0]
 [0 0 0 1 0]]

The adjacency matrix in an undirected graph is forcibly symmetrical since an edge existing between two nodes goes both way and therefore a pair (a,b) is unordered (there is no difference between (a,b) and (b,a)), however in a directed graph an edge (a,b) only goes one way and so the matrix isn't symmetrical as is the case of our example

Navigating from one representation to another:

We can always go from one representation to another depending on our needs at the time.

Let us try to implement them in Python!

From List to Matrix:

def fromLstToMat(adjacenceList):
    mat=[]
    for i in range(len(adjacenceList)):
        lstToAppend=[0]*len(adjacenceList)
        for j in adjacenceList[i]:
            lstToAppend[j-1]=1
        mat.append(lstToAppend)
    return mat

print("The Adjacence matrix of our graph is :",fromLstToMat(graphList))

The Adjacence matrix of our graph is : [[0, 1, 1, 0, 1], [1, 0, 0, 1, 0], [0, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 0]]

We can also implement this algorithm using numpy:

def fromLstToMatNP(adjacenceList):
    mat=np.zeros((len(adjacenceList),len(adjacenceList)))
    for i in range(len(adjacenceList)):
        for j in adjacenceList[i]:
            mat[i][j-1]=1
    return mat

print("The Adjacence matrix of our graph is :",fromLstToMatNP(graphList))

The Adjacence matrix of our graph is : [[0. 1. 1. 0. 1.]
 [1. 0. 0. 1. 0.]
 [0. 1. 0. 0. 0.]
 [1. 1. 0. 0. 0.]
 [0. 0. 0. 1. 0.]]

From Matrix to List:

def fromMatToList(adjacenceMatrix):
    list=[]
    for i in range(len(adjacenceMatrix)):
        lstToAppend=[]
        for j in range(len(adjacenceMatrix)):
            if adjacenceMatrix[i][j]==1:
                lstToAppend.append(j+1)
        list.append(lstToAppend)
    return list

print("The Adjacence list of our graph is :",fromMatToList(graphMat))
print("The Adjacence list of our graph is :",fromMatToList(graphMatnp))

The Adjacence list of our graph is : [[2, 3, 5], [1, 4], [2], [1, 2], [4]]
The Adjacence list of our graph is : [[2, 3, 5], [1, 4], [2], [1, 2], [4]]

Thank you for reading!

Next article: Graph search