Graph Implementation In Python [PART 2] By albro

[albro]

Let's look at some different examples of graph implementations in Python using dictionaries.

In the first example, I want to implement the undirected graph drawn in the box below using Python dictionaries.

      0
      / \
     1---2
      \ /
       3

The above graph can be easily displayed using dictionaries. In the box below, I have implemented the above graph definition code with 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 this example, I decide to implement directed graph maintenance code using Python dictionaries. To solve this problem, I use the arbitrary graph drawn in the box below.

 0 --> 1 --> 2 --> 3
   |           |     |
   v           v     v
   4           5 --> 6

Dictionaries are among the most widely used structures in the Python programming language. Graph definition is one of the smallest capabilities of this structure. With the help of the dictionaries implemented below, I have displayed the above graph.

vertices = {
    0: [1, 4],
    1: [2],
    2: [3, 5],
    3: [6],
    4: [],
    5: [6],
    6: []
}
edges = {
    0: {1, 4},
    1: {2},
    2: {3, 5},
    3: {6},
    4: set(),
    5: {6},
    6: set()
}

A weighted graph is a graph in which each edge has a specific weight. The general shape of the graph we want is the same as the first example in the post that I have shown below.

      0
      / \
     1---2
      \ /
       3

In this problem, the weights of all edges are determined as follows.

• The weight of the edge between vertices 0 and 1 is equal to 4.
• The weight of the edge between vertices 0 and 2 is equal to 5.
• The weight of the edge between vertices 1 and 2 is equal to 3.
• The weight of the edge between vertices 1 and 3 is equal to 2.
• The weight of the edge between vertices 2 and 3 is equal to 6.

Now in the box below, I have implemented the above weighted graph with the help of dictionaries.

vertices = {
    0: [(1, 4), (2, 5)],
    1: [(0, 4), (2, 3), (3, 2)],
    2: [(0, 5), (1, 3), (3, 6)],
    3: [(1, 2), (2, 6)]
}
edges = {
    0: {(1, 4), (2, 5)},
    1: {(0, 4), (2, 3), (3, 2)},
    2: {(0, 5), (1, 3), (3, 6)},
    3: {(1, 2), (2, 6)}
}

In the code above, the values ​​of the keys in the vertices dictionary are tuples in Python. In both dictionaries, the keys represent all the vertices of the graph. In these tuples, the first element shows the adjacent vertex and the second element shows the weight of the edge connecting them. The values ​​of each key in the edges dictionary are also displayed in the form of tuples. In these tuples, the first element shows the adjacent vertex and the second element is the weight of the edge connecting these vertices together.

Using a dictionary to display graph vertices and edges in Python is a flexible and optimal method in terms of memory consumption. In this method to display graphs, operations related to removing and adding vertices and edges are done simply. However, traversing graphs in this method is slower than other methods such as adjacency lists.

Comments

[stemsocial]

Thanks for your contribution to the STEMsocial community. Feel free to join us on discord to get to know the rest of us!

Please consider delegating to the @stemsocial account (85% of the curation rewards are returned).

You may also include @stemsocial as a beneficiary of the rewards of this post to get a stronger support.