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 def add_edge(self,Edge): if self in Edge.ends: self.incident_edges.add(Edge) if Edge.source()==self: self.incident_outward_edges.add(Edge) else: self.incident_inward_edges.add(Edge) else: print 'Cannot add edge to vertex, vertex not in ends.' def remove_edge(self,Edge): self.incident_edges.discard(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 add_label(self, label): self.labels.add(label) def remove_label(self, label): self.labels.discard(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[0] def target(self): return self.ends[1] def add_label(self, label): self.labels.add(label) def remove_label(self, label): self.labels.discard(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: Supergraph.add_subgraph(self) for Subgraph in subgraphs: Subgraph.add_supergraph(self) 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 def add_vertex(self, Vertex): if Vertex in self.vertices: return self.vertices.append(Vertex) @update_up def create_edge(self, ends): NewEdge=self.Edge(ends=ends) self.edges.add(NewEdge) for Vertex in ends: Vertex.add_edge(NewEdge) @update_up_down def remove_edge(self, Edge): if not Edge in self.edges: return False self.edges.discard(Edge) 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) def get_adjacency_matrix(self): #adj_list = [self.get_adjacency_list_of_vertex(Vertex) for Vertex in self.vertices] adj_list = map(lambda x: self.get_adjacency_list_of_vertex(x), self.vertices) adj_mat = np.array(adj_list) return adj_mat def get_adjacency_matrix_as_list(self): return self.get_adjacency_matrix().tolist() def set_adjacency_list(self, adj_list): self.vertices=[] self.edges=[] def add_subgraph(self,Subgraph): self.subgraphs.add(Subgraph) def add_supergraph(self, Supergraph): self.supergraphs.add(Supergraph) 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 def add_vertex_label(self, vertex, label): self.vertex_dict[label] = vertex vertex.add_label(label) 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): vertex=self.vertex_dict.pop(label, 'Not Found') if vertex == 'Not Found': return else: vertex.remove_label(label) def add_edge_label(self, edge, label): self.edge_dict[label] = edge edge.add_label(label) 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): edge=self.edge_dict.pop(label, 'Not Found') if edge == 'Not Found': 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): def get_adjacency_list_of_vertex(self, Vertex): 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[0] != Vertex: index = self.vertices.index(ends[0]) else: index = self.vertices.index(ends[1]) adj_list[index] += 1 return adj_list def set_adjacency_matrix(self, adj_mat): shape = np.shape(adj_mat) if shape[0] != shape[1]: print 'Wrong shape, expecting square matrix.' return n = shape[0] self.vertices=[] self.edges=[] self.create_vertices(n) for row in range(n): Source = self.vertices[row] for col in range(row+1): no_edges = adj_mat[row, col] Target = self.vertices[col] for Edge in range(no_edges): self.create_edge(ends=[Source, Target]) def plot(self): A = self.get_adjacency_matrix_as_list() convert_to_igraph = ig.Graph.Adjacency(A, mode='undirected') 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) def get_adjacency_list_of_vertex(self, Vertex): 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) adj_list[index] += 1 return adj_list def set_adjacency_matrix(self, adj_mat): shape = np.shape(adj_mat) if shape[0] != shape[1]: print 'Wrong shape, expecting square matrix.' return n = shape[0] self.vertices=[] self.edges=[] self.create_vertices(n) for row, col in range(n): no_edges = adj_mat[row, col] 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): A = self.get_adjacency_matrix_as_list() convert_to_igraph = ig.Graph.Adjacency(A) 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.
[…] back! Last time we introduced the Vertex, Edge, Graph, DirGraph and UnDirGraph classes, now we are going to have […]
[…] 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 […]
[…] Graphs as Objects in Python (triangleinequality.wordpress.com) […]
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.
Thank You in advance!