Graph Data Structure – Python Implementation

Today, as data volumes are growing almost exponentially, search in artificial intelligence and computer science is regaining it’s popularity. There is basically no field without application of at least some of the search algorithms. Many of these search algorithms in computer science and artificial intelligence rely heavily on graphs and trees as underlying data structure for performing search strategies.

Graphs in Computer Science are abstract Data Structures for representing, among other things, many real life phenomena, e.g. social networks, brain activity, road maps, organizational hierarchies etc. They consist of vertices or nodes, and edges that interconnect vertices. Tree Data Structures are also a kind of graph. Graphs may be directed or undirected.

There are basically 2 main implementation approaches for graph data structures. Adjacency list, where each node or vertex keeps a list of it’s adjacent nodes.
Adjacency matrix, represented as 2D matrix where rows represent source nodes, and columns represent target nodes. The corresponding row, column value is the weight or distance of that edge that connects source and target node. In the latter case, this value could only be 1, representing that there exists a connection between two nodes.

I would warmly recommend you one of the best books on algorithms and data structures.

Both implementations have their use cases depending on the size, interconnectedness  of your data and the final purpose of your search algorithm.

Over the period of next few weeks, I will publish some of my search algorithm implementations and discuss their use cases. Today, I will start with basic graph implementation in Python which, I hope, will find many use cases in your future projects.

‘Nuff said, here’s the code:

#
# Vertex class
#
class Vertex:
    def __init__(self, name):
        self.name = name
        self.neighbors = {}

    # just for representation
    def __str__(self):
        return self.name
    def __repr__(self):
        return self.name

    # add neighbor
    def add_neighbor(self, node, distance):
        self.neighbors[node] = distance

    # print all neighbors
    def print_neighbors(self):
        for key, value in self.neighbors.iteritems():
            print key, value

    # size of neighborhood
    def neighbor_size(self):
        print len(self.neighbors)

Now, we can instantiate some nodes or vertices.

# list of nodes in graph
S = Vertex("S")
A = Vertex("A")
D = Vertex("D")
B = Vertex("B")
C = Vertex("C")
T = Vertex("T")

Let’s create a Graph to hold that vertices together.

#
# Graph class
#
class Graph:
    def __init__(self, name):
        self.name = name
        self.vertices = set()
        self.edges = {}

    def add_vertice(self, vertex):
        self.vertices.add(vertex)

    # add edge between start and end node with some distance
    def add_edge(self, start, end, distance):
        if start not in self.edges:
            self.edges[start] = {}
        # else
        self.edges[start][end] = distance

    # print vertices
    def print_vertices(self):
        for v in self.vertices:
            print v

    # get list of edges
    def print_edges(self):
        print self.edges

    # get neighbors
    def get_adjecent(self, node):
        return self.edges[node]

We have everything what we need to start experimenting with graph structures.
Let’s take some basic graph and implement it in Python. For example the one below.

# construct graph
G1 = Graph("example")
G1.add_edge(S,D,4)
G1.add_edge(S,A,7)
G1.add_edge(A,D,1)
G1.add_edge(A,B,1)
G1.add_edge(D,B,5)
G1.add_edge(D,C,7)
G1.add_edge(B,C,8)
G1.add_edge(B,T,10)
G1.add_edge(C,T,1)

That’s it. You have the complete graph implementation in python. You can test the functionality with lines like

In [15]:

# test
G1.print_edges()

Out[15]:
{S: {A: 7, D: 4}, B: {T: 10, C: 8}, A: {B: 1, D: 1}, D: {B: 5, C: 7}, C: {T: 1}}

# test adjecency
G1.get_adjecent(B)

Out[16]:
{C: 8, T: 10}

Please note that this implementation contains only basic functionality. As a practice, you could add additional graph operations described here.

As I already mentioned, this graph implementation will be used in next few search algorithm implementations of mine, which I shall publish here soon. So stay tuned!

You can find the whole code at https://github.com/dzenanh/algorithms/blob/master/Graph-Implementation.ipynb.

Cheers!