Graph definition and implementation

We all familiar with linear data structures such as arrays, stacks, and queues. For non-linear data structures, we know trees that have a hierarchical structure. In this post, I’ll introduce another type of non-linear data structure: graph, along with its implementation in python.

Definition

A graph consists of a set of vertices, V, and a set of edges E. Vertices are similar to nodes in the tree, or cities in a map that is connected by roads. Edges are path who connects two vertices together. The following picture is showing a basic undirected graph. As we can see, this graph consists of a set of vertices = {v1, v2, v3, v4, v5}, and edges = {{v1, v2}, {v1, v3}, {v1, v5}, {v2, v5}, {v3, v4}, {v4, v5}}.

An undirected graph example

There are two types of graphs: directed and undirected. The previous graph is an undirected graph, meaning there’s no direction between two vertices. The directed graph, on the other hand, is pointing from the origin vertice to the destination vertice. The binary tree is a classical example of a directed graph. Each node in the tree could have two children, which implies the direction is from the root to leaves.

How to identify whether a graph is directed or undirected? Usually, for the undirected graph, each edge is represented by unordered pair such as a set. Because for a set, {a, b} = {b, a}. So the edges for the undirected graph looks like: E = {{a,b}, {a,c}, {c,d}} The directed graph uses ordered pairs to tell an edge. And the first element in the pair is the origin vertice, the second element is the destination vertice. An example of directed edge: E = {(a, b),(a,c),(a,d)}.

Application

The graph is widely used to tell the relationship between two things. For example, a graph is used to tell friendships in your Facebook connections. Friend connections can be represented as an undirected graph since friendships are mutual. As shown in the following graph, I have connections with Lily, Sam, and Mike, as labeled in green. I could have potential connections(labeled in yellow) with Alex, Peter, and Joy since they are friends of my friends. And I could have further connections with their connections.

graph of a social network

Besides social networks, graphs are also applied to implement maps, websites (re-direction relationships), and so on.

Implementation

Let’s implement the simplest version of the directed graph. First, we need to implement the edge class:

class Edge:
    def __init__(self, origin, destination):
        self.origin = origin
        self.destination = destination

Then, we implement the graph:

class Graph:
    def __init__(self, edges):
        self.adj = [[] for _ in range(len(edges))]
    
        for current in edges:
            self.adj[current.origin].append(current.destination)

That’s it! We connect each vertice with its corresponding edges!

Thanks for reading!