Home » maths » graph theory » Graphs as Objects in Python

# Graphs as Objects in Python

This time we are going to combine the lessons learned about objects and decorators in Python, and about graph theory, to represent graphs as objects.

Let’s jump right in and create classes of vertices and edges. We’ll start with a vertex:

```class BasicNode: #should be interfaced to from a graph object
def __init__(self, content=None, labels=None):
self.content = content
self.incident_edges =set([])
self.incident_outward_edges=set([])
self.incident_inward_edges=set([])
if labels is None:
self.labels=set([])
else:
self.labels=labels

if self in Edge.ends:
if Edge.source()==self:
else:
else:
print 'Cannot add edge to vertex, vertex not in ends.'

def remove_edge(self,Edge):

def get_neighbors(self):
neighbors = [Edge.ends for Edge in self.incident_edges]
unique_neighbors = list(set(reduce(lambda x,y: x+y, neighbors)))
if [self, self] not in neighbors: #checks for a loop
unique_neighbors.remove(self)
return unique_neighbors

def get_targets(self):
#targets = set([Edge.target() for Edge in self.incident_outward_edges])
targets = set(map(lambda x: x.target(), self.incident_outward_edges))
return targets

def get_sources(self):
#sources = set([Edge.source() for Edge in self.incident_inward_edges])
sources = set(map(lambda x: x.source(), self.incident_inward_edges))
return sources

def remove_label(self, label):
```

This is pretty self-explanatory, but notice the philosophy of the design: vertices and edges are ‘dumb’, they don’t know about what graphs they might be in, the only things they know are which other vertices and edges are associated to it.

Also notice the ‘content’ attribute, this is just to emphasise that a vertex can be a vertex whilst also being a function, another object, a list etc…

Now we’ll do the edges:

```class BasicEdge: #should be interfaced to from a graph object
def __init__(self, content=None, ends=[], labels=None):
self.content = content
self.ends = ends
if labels is None:
self.labels=set([])
else:
self.labels=labels

def source(self):
return self.ends

def target(self):
return self.ends

def remove_label(self, label):
```

Again pretty self-explanatory. Now just like in the previous post we want to enable subgraph supergraph communication, so we preface our class definition with some update decorators.

```def update_up(class_method):
def inner(self, *args, **kwargs):
method_name = class_method.func_name
class_method(self, *args, **kwargs)
for Supergraph in self.supergraphs:
getattr(Supergraph, method_name)(*args, **kwargs)
return inner

def update_up_down(class_method):
def inner(self, *args, **kwargs):
method_name = class_method.func_name
if class_method(self, *args, **kwargs):
for Supergraph in self.supergraphs:
getattr(Supergraph, method_name)(*args, **kwargs)
for Subgraph in self.subgraphs:
getattr(Subgraph, method_name)(*args, **kwargs)
return inner
```

Ok now we’re ready to define the Graph class. This is a bit long but all of its methods are pretty simple. It basically acts as a manager for all the vertices and edges, it is in charge of keeping track of changes, for instance telling a vertex when a new edge connecting to it has been created.

It is not in charge of deleting edges and vertices, it simply forgets about them when they are no longer part of the Graph. That way it can play with other Graphs who may be sharing Vertices in a relation other than super/sub graph.

It is also neutral on the issue of whether it is directed, these will be implemented as subclasses.

Another neat point is that when we initialise the Graph object we pass it a vertex and edge classes, which means that we can easily expand the behaviour of the Graph by using different edge and vertex classes.

```import numpy as np
class Graph(object):
def __init__(self, subgraphs=None, supergraphs=None, vertices=None, edges=None, Vertex=BasicNode, Edge=BasicEdge):

if edges == None:
edges = []
self.edges=set(edges)
if vertices == None:
vertices = []
self.vertices=vertices
if subgraphs == None:
subgraphs=[]
self.subgraphs =set(subgraphs)
if supergraphs == None:
supergraphs =[]
self.supergraphs=set(supergraphs)
for Supergraph in supergraphs:
for Subgraph in subgraphs:
self.vertex_dict = {}
self.edges_dict={}
self.Vertex = Vertex
self.Edge = Edge

@update_up
def create_vertex(self):
self.vertices.append(self.Vertex())

def create_vertices(self, no_create):
for i in range(no_create):
self.create_vertex()

@update_up
if Vertex in self.vertices:
return
self.vertices.append(Vertex)

@update_up
def create_edge(self, ends):
NewEdge=self.Edge(ends=ends)
for Vertex in ends:

@update_up_down
def remove_edge(self, Edge):
if not Edge in self.edges:
return False
return True

def get_incident_edges(self, Vertex):
incident_edges = Vertex.incident_edges & self.edges
return incident_edges

@update_up_down
def remove_vertex(self, Vertex):
if Vertex not in self.vertices:
return False
edges_to_remove = self.get_incident_edges(Vertex)
for Edge in edges_to_remove:
self.remove_edge(Edge)
self.vertices.remove(Vertex)
return True

def get_vertex_neighbors(self, Vertex):
neighbors = (Vertex.get_neighbors() & set(self.vertices))
return neighbors

def get_degree(self, Vertex):
return len(self.get_incident_edges(Vertex))

def get_number_vertices(self):
return len(self.vertices)

def get_number_edges(self):
return len(self.edges)

self.vertices=[]
self.edges=[]

def is_in(self,vertex_or_edge):
if (vertex_or_edge in self.edges) or (vertex_or_edge in self.vertices):
return True
else:
return False

def get_incident_outward_edges(self,Vertex):
return (Vertex.incident_outward_edges & self.edges)

def get_incident_inward_edges(self,Vertex):
return (Vertex.incident_inward_edges & self.edges)

def get_vertex_targets(self, Vertex):
targets = (Vertex.get_targets() & set(self.vertices))
return targets

def get_vertex_sources(self, Vertex):
sources = (Vertex.get_sources() & set(self.vertices))
return sources

self.vertex_dict[label] = vertex

def get_vertex(self,label):
if label in self.vertex_dict.keys():
return self.vertex_dict[label]
else:
return None

def get_vertex_label(self, vertex):
labels = vertex.get_labels()
labels = labels & self.vertex_dict.keys()
labels = filter(lambda x: self.get_vertex[x]==vertex,labels)

def remove_vertex_label(self, label):
return
else:
vertex.remove_label(label)

self.edge_dict[label] = edge

def get_edge(self,label):
if label in self.edge_dict.keys():
return self.edge_dict[label]
else:
return None

def get_edge_label(self, edge):
labels = edge.get_labels()
labels = labels & self.edge_dict.keys()
labels = filter(lambda x: self.get_edge[x]==edge,labels)

def remove_edge_label(self, label):
return
else:
edge.remove_label(label)
```

Phew. Now we want to distinguish between directed and undirected graphs for the purposes of working with adjacency matrices and the like, and of course plotting.

For the purposes of displaying graphs I have enlisted an excellent library for graphs – igraph. I interface to this for plotting purposes.

```import igraph as ig

class UnDirGraph(Graph, object):

N = self.get_number_vertices()
adj_list= [0 for x in range(N)]
incident_edges = self.get_incident_edges(Vertex)
for Edge in incident_edges:
ends = Edge.ends
if ends != Vertex:
index = self.vertices.index(ends)
else:
index = self.vertices.index(ends)

if shape != shape:
print 'Wrong shape, expecting square matrix.'
return
n = shape
self.vertices=[]
self.edges=[]
self.create_vertices(n)
for row in range(n):
Source = self.vertices[row]
for col  in range(row+1):
Target = self.vertices[col]
for Edge in range(no_edges):
self.create_edge(ends=[Source, Target])

def plot(self):
ig.plot(convert_to_igraph)

class DirGraph(Graph):
def get_incident_outward_edges(self,Vertex):
return (Vertex.incident_outward_edges & self.edges)

def get_incident_inward_edges(self,Vertex):
return (Vertex.incident_inward_edges & self.edges)

N = self.get_number_vertices()
adj_list= [0 for x in range(N)]
incident_edges = self.get_incident_outward_edges(Vertex)
for Edge in incident_edges:
target = Edge.target()
index = self.vertices.index(target)

if shape != shape:
print 'Wrong shape, expecting square matrix.'
return
n = shape
self.vertices=[]
self.edges=[]
self.create_vertices(n)
for row, col in range(n):
Source = self.vertices[row]
Target = self.vertices[col]
for Edge in range(no_edges):
self.create_edge(ends=[Source, Target])

def get_vertex_targets(self, Vertex):
targets = (Vertex.get_targets() & set(self.vertices))
return targets

def get_vertex_sources(self, Vertex):
sources = (Vertex.get_sources() & set(self.vertices))
return sources

def plot(self):
ig.plot(convert_to_igraph)
```

And that’s it for this post! I am not going to bother uploading the code as a file, because we haven’t done the fun stuff yet, that is classes for different kinds of graphs like linear, cycle, complete etc… Fun because we can easily create some graphs and plot them, and everybody likes pretty graphs.

Let me know what you think.

1. […] back! Last time we introduced the Vertex, Edge, Graph, DirGraph and UnDirGraph classes, now we are going to have […]

2. […] orientated programming here, decorators in python here, and how to represent graphs in python here and here. Note that to produce plots of the graphs, you will need the igraph module for […]

3. […] Graphs as Objects in Python (triangleinequality.wordpress.com) […]

4. Abhishek Sharma says:

First of all please accept by heartfelt gratitude for writing such an outstanding tutorial to explain ML to newcomers like me.

I am facing difficulty while understanding the below line of codes.
neighbors = [Edge.ends for Edge in self.incident_edges]
unique_neighbors = list(set(reduce(lambda x,y: x+y, neighbors)))
I would really appreciate if you could explain this with 1 example.