Graph Implementation

Now we will consider 3 types of graph implementation in Python.

Implementation using graphviz library

Graphviz is a powerful library for creating and visualizing graphs. It provides a simple and intuitive interface for generating graph visualizations, making it ideal for displaying complex graph structures.

python
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import graphviz

class Graph:
    def __init__(self):
        self.graph = graphviz.Graph()

    def add_vertex(self, vertex):
        self.graph.node(str(vertex))

    def add_edge(self, from_vertex, to_vertex):
        self.graph.edge(str(from_vertex), str(to_vertex))

    def get_neighbors(self, vertex):
        neighbors = []
        for edge in self.graph.body:
            if edge.startswith(f'{vertex}" ->'):
                neighbor = edge.split('-> ')[1].split(' [')[0]
                neighbors.append(neighbor)
        return neighbors

Implementation using adjacency matrix

An adjacency matrix is a square matrix used to represent a graph. In this matrix, rows and columns correspond to vertices (or nodes) in the graph, and the presence or absence of edges between vertices is represented by the values of the matrix elements.
This implementation provides a compact and efficient representation of graph data, especially for dense graphs with many connections.

Note

In a weighted graph, the values in the adjacency matrix can represent the weights of the edges. The matrix value may be either zero or infinity when there is no edge between vertices.

python
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Graph:
    def __init__(self, size):
        self.size = size
        self.matrix = np.zeros((size, size), dtype=int)

    def add_edge(self, from_vertex, to_vertex):
        self.matrix[from_vertex][to_vertex] = 1
        self.matrix[to_vertex][from_vertex] = 1

    def add_vertex(self):
        self.size += 1
        new_matrix = np.zeros((self.size, self.size), dtype=int)
        new_matrix[:self.size-1, :self.size-1] = self.matrix
        self.matrix = new_matrix

    def find_neighbors(self, vertex):
        neighbors = []
        for i in range(self.size):
            if self.matrix[vertex][i] == 1:
                neighbors.append(i)
        return neighbors

Implementation using Python dictionary

Graph implementation using a dictionary is a popular approach in Python. In this implementation, the dictionary's keys represent the graph's vertices (or nodes), and the values represent each vertex's neighbors (or adjacent vertices). This allows for efficient access to the neighbors of a given vertex.

python
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Graph:
    def __init__(self):
        self.graph = {}

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, from_vertex, to_vertex):
        if from_vertex in self.graph and to_vertex in self.graph:
            self.graph[from_vertex].append(to_vertex)
            self.graph[to_vertex].append(from_vertex)  # For undirected graph

    def get_neighbors(self, vertex):
        if vertex in self.graph:
            return self.graph[vertex]
        else:
            return []