Graph Implementation In Python [PART 1] By albro

Graphs are a very important data structure in computer science. These data structures are used to represent all kinds of networks - from social networks to road maps. In Python, there are several different ways to implement and display graphs. For example, we can refer to "Adjacency Matrices", "Adjacency Lists" and the object-oriented representation method. Another most common way to display a graph in Python is to use dictionaries to display its vertices and edges. Using a dictionary in Python is a simple, efficient and appropriate way to draw small and medium-sized graphs. Another popular method is to use the powerful NetworkX library in Python, which is used to create, use and display graphs.

The NetworkX library provides a large number of "built-in" functions and algorithms for analyzing and illustrating graphs. With the help of this library, large and complex graphs can be managed effectively. Overall, using graphs in Python provides a very efficient and flexible way to display and analyze any type of network. For this reason, in this post, I have explained several different methods of implementing and displaying graphs in simple language. These methods include "adjacency matrices", "adjacency lists", "object-oriented" representation methods, etc.

What is a graph in Python?

Graphs are one of the fundamental data structures in computer science and are used to model complex relationships between entities. Graph applications include a wide range of applications such as social networks, goods transportation systems, and bioinformatics. On the other hand, the Python programming language, as a very popular and versatile language, has provided several different methods for implementing graphs.

In this post, I reviewed several different methods of graph implementation in Python. I have also used the NetworkX library. This library provides a very convenient tool for working with graphs.

Python programming language has high flexibility to solve problems related to different fields. For this reason, it is chosen to work on various projects. For example, it can be considered from the ability to work on the design of web applications to common issues in the world of artificial intelligence and mathematical calculations, etc. Graphs have also proved their presence as one of the most widely used tools in the world of computer science, from solving mathematical problems to network management. Python developers need to have specific skills related to that field to enter each of the work areas.

Graph implementation in Python

There are several different methods for implementing graphs in Python, each of which has its own advantages and disadvantages.

• Adjacency Matrices
• Adjacency Lists
• Object-Oriented Representations
• Using a dictionary to display graph vertices and edges

The adjacency matrix is ​​a type of square matrix that is used to display graphs. In this matrix, rows and columns are used to represent graph vertices and matrix elements are used to represent edges. If there is an edge between two different vertices, the element corresponding to these two vertices in the matrix is ​​set to 1. But if there is no edge between two vertices, the element located at the intersection of these two vertices is set to 0.

I have shown the code for creating the adjacency matrix. Of course, the elements in this matrix are hypothetically valued.

# Create a graph with 4 vertices and 5 edges
graph = [[0, 1, 1, 0],
         [1, 0, 1, 1],
         [1, 1, 0, 1],
         [0, 1, 1, 0]]
# Print the graph
for row in graph:
    print(row)

After executing the above code, the following two-dimensional matrix will be displayed to the user in the output.

[0, 1, 1, 0]
[1, 0, 1, 1]
[1, 1, 0, 1]
[0, 1, 1, 0]

Now consider the example of a simple, undirected graph consisting of four vertices and four edges.

      0
      / \
     1---2
      \ /
       3

For the simple graph above, the adjacency matrix is ​​similar to the matrix drawn in the box below.

   0  1  2  3
0  0  1  1  0
1  1  0  1  1
2  1  1  0  1
3  0  1  1  0

To display the above matrix in Python, you can use the two-dimensional list as shown below.

adjacency_matrix = [
    [0, 1, 1, 0],
    [1, 0, 1, 1],
    [1, 1, 0, 1],
    [0, 1, 1, 0]
]

Although adjacency matrices are very simple and easy to understand, they can be very memory consuming when working with large graphs. It means that they have high memory consumption. Because these matrices store the information of all possible edges. Therefore, using the adjacency matrix is ​​not suitable for sparse and sparse graphs.

An adjacency list is a set of Python lists used to represent a graph. Each list in this set represents a vertex and the elements in the list represent the edges of that vertex. The adjacency list is more spatially efficient than the adjacency matrix. This efficiency is especially noticeable when working with discrete matrices.

I have shown a simple example of creating an adjacency list and implementing a graph with its help.

# Create a graph with 4 vertices and 5 edges
graph = {0: [1, 2],
         1: [0, 2, 3],
         2: [0, 1, 3],
         3: [1, 2]}
# Print the graph
for vertex in graph:
    print(vertex, ":", graph[vertex])

After executing the above code, the following output will be displayed to the user in the Python console.

0 : [1, 2]
1 : [0, 2, 3]
2 : [0, 1, 3]
3 : [1, 2]

Now, as in the previous section, consider an example of a simple undirected graph that has four vertices and four edges.

      0
      / \
     1---2
      \ /
       3

If we want to implement the adjacency list related to the simple graph shown in the above example with the help of Python, we will get a list similar to the box below.

adjacency_list = [
    [1, 2],
    [0, 2, 3],
    [0, 1, 3],
    [1, 2]
]

In Python, we can display the above list with the help of a list containing other lists - exactly like the box above.

adjacency_list = [
    [1, 2],  # adjacent to vertex 0
    [0, 2, 3],  # adjacent to vertex 1
    [0, 1, 3],  # adjacent to vertex 2
    [1, 2]  # adjacent to vertex 3
]

Adjacency lists are more spatially efficient than adjacency matrices. In fact, the amount of memory consumption is much more optimal. Especially about empty graphs, because these lists only store information about existing edges. Therefore, memory is not wasted to show non-existent edges. Although these lists may have a slower scrolling process. Because each vertex must search its adjacency list to find its neighbors.

Object-oriented representation of graphs is called a class-based graph implementation in Python. This implementation provides a more abstract and reusable representation of graphs. In this method, each graph is represented as a set of vertices and edges. In this representation, each vertex is an object with its own attributes. For example, we can refer to attributes such as "ID" number identification and the neighbors of that vertex.

I have shown an example of the code related to the implementation of the object-oriented representation of the graph in the Python programming language.

class Vertex:
    def __init__(self, vertex_id):
        self.id = vertex_id
        self.neighbors = []
    def add_neighbor(self, neighbor):
        if neighbor not in self.neighbors:
            self.neighbors.append(neighbor)
class Graph:
    def __init__(self):
        self.vertices = {}
    def add_vertex(self, vertex):
        if isinstance(vertex, Vertex) and vertex.id not in self.vertices:
            self.vertices[vertex.id] = vertex
            return True
        else:
            return False
    def add_edge(self, v1, v2):
        if v1 in self.vertices and v2 in self.vertices:
            self.vertices[v1].add_neighbor(v2)
            self.vertices[v2].add_neighbor(v1)
            return True
        else:
            return False
    def get_vertices(self):
        return self.vertices.keys()
    def __iter__(self):
        return iter(self.vertices.values())
# Create a graph with 4 vertices and 5 edges
graph = Graph()
for i in range(4):
    graph.add_vertex(Vertex(i))
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)

Another method of graph display is using dictionaries in Python. We will use two different dictionaries to demonstrate this approach. We name one of these dictionaries as vertices and the other dictionary as edges. In the vertex dictionary, the key to display the vertices and their corresponding values ​​are the edges. In the edge dictionary, the keys represent the edge and the corresponding value of each key also indicates the vertices that each edge connects to each other.

To show how to use a dictionary in graph display, I use the same example as the steps above - a simple, undirected graph with four edges and four vertices. In this example, I show how dictionaries display the edges and vertices of a graph.

      0
      / \
     1---2
      \ /
       3

Now I display the above graph using both "Edges" and "Vertices" dictionaries.

vertices = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [1, 2]
}
edges = {
    0: {1, 2},
    1: {0, 2, 3},
    2: {0, 1, 3},
    3: {1, 2}
}

In the above codes, the keys of the vertices dictionary represent all the vertices of the graph and the corresponding value of each key shows its adjacent vertices. The keys in the edges dictionary indicate the edges of the graph and the values ​​corresponding to each key indicate the vertices connected by that edge. Remember to use SET in Python to display edges. This will make sure that no edge is mistakenly repeated.

To add new vertices to the graph, we can simply add key-value pairs to the vertices dictionary.

vertices[4] = [2, 3]

But in order to add a new edge between two vertices already in the dictionary, it is enough to simply find and update the collections of those vertices in the dictionary.

edges[0].add(3)
edges[3].add(0)

Using dictionaries to display graph edges and vertices in Python is a flexible and memory-optimized method. Also, in this method, removing and adding vertices and edges to the graph is done in a simple way. However, traversing the graph with this method may be slower than other methods such as adjacency list.