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.

cgznl

The game of maze represented as a graph data structure.

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.

1-7-kbs-graph

# 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!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Advertisements
Advertisements
%d bloggers like this: