Basics of Graphs in Python

thumbnail

A graph contains vertices and edges. Vertices are also known as Nodes. Vertices in a graph is connected with each other through edges represented by a line. Not all the vertices in a graph need to be connected with each other.

If the edges between the vertices are undirected, the graph is called an undirected graph. When the edges are directed, essentially by an arrow, it is called a directed graph. In an undirected graph, if there is an edge between vertex A and B, that means you can traverse from A to B and vice versa. But in an directed graph, if the edge represented as an arrow pointing from A to B, that means you can traverse from A to B but not the other way.

If all the vertices in a graph is has edges in such a way that you can reach from any vertex to another vertex in the graph, it is known as Connected Graph. If a vertex has edge to itself, it is known as a Loop. Any graph without a loop is called a Simple Graph.

The direct neighbors of a vertex is called Adjacent nodes. The number of adjacent nodes is called the degree of a particular node. Here is a picture of a undirected graph:

Source: Wikimedia

Though many of us used to think that graphs are only interesting for Mathematics lords but it has become a very important topics among Computer Science people in last couple of decades as well. Some important graphs we are seeing in our day to day lives are Internet networks, social networks friends list, servers organization, conncted devices, sitemaps in websites, etc.

There are different way to represent a graph in Python, but no built-in modules. The simplest way to represent a graph in Python probably using a list or a dict. For example, the above graph can be represented in Python as:

graph = [[1, 2, 5], [3, 5], [2, 4], [3, 5, 6], [1, 2, 4], [4]]

So, we used the list index (+1, as list index starts from 0) to represent a node in the graph and the value in that index as the edges from the current node.

List index: 0, Node: 1, Edges to: 1, 2, 5
List index: 1, Node: 2, Edges to: 3, 5
List index: 2, Node: 3, Edges to: 2, 4
...and so on.

Definitely, it is not the most intuitive representation of graphs in Python. But you might need to solve some problem on small graphs when it can be pretty handy to use.

The more intuitive way of the above approach is using a dict instead of a list. For example:

graph = {
    1: [1, 2, 5],
    2: [3, 5],
    3: [2, 4],
    4: [3, 5, 6],
    5: [1, 2, 4],
    6: [4]
}

As you can see, using a dict is almost similar as using a list, except it makes it easy to read and manipulate by the dictionary key.

Now, lets traverse our graph using python.

Find the first path between two nodes

Now, we will write a function which will accept a graph, a source and destination node and will give us the first path from the source to destination node, if any. Here is the function:

def find_first_path(graph, src, dst, path=[]):
    path = path + [src]
    if src == dst:
        return path

    if not src in graph:
        return None

    for node in graph[src]:
        if node not in path:
            new_path = find_first_path(graph, node, dst, path)
            if new_path:
                return new_path
    return None

If we call the above function on our graph:

if __name__ == '__main__':
    graph = {
        1: [1, 2, 5],
        2: [3, 5],
        3: [2, 4],
        4: [3, 5, 6],
        5: [1, 2, 4],
        6: [4]
    }

    path = find_first_path(graph, 1, 6)

    print(path)

It will give us output:

[1, 2, 3, 4, 6]

Find all the paths between two nodes

Now, lets improve our function to give us all the available path between two nodes.

def find_all_paths(graph, src, dst, path=[]):
    path = path + [src]
    if src == dst:
        return [path]
    if not src in graph:
        return []
    paths = []
    for node in graph[src]:
        if node not in path:
            new_paths = find_all_paths(graph, node, dst, path)
            for new_path in new_paths:
                paths.append(new_path)
    return paths

After running our new method on our graph, will give us output a list of all paths from node 1 to 6:

[[1, 2, 3, 4, 6], [1, 2, 5, 4, 6], [1, 5, 2, 3, 4, 6], [1, 5, 4, 6]]

I hope you enjoyed the reading. See you again!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Back To Top