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

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 = {}

# add edge between start and end node with some 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
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")
```

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

In :

```# test
G1.print_edges()
```

Out:
{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