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

    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.

Advertisements