Welcome back! Last time we introduced the Vertex, Edge, Graph, DirGraph and UnDirGraph classes, now we are going to have some fun and introduce the special graphs like linear, cycle, complete and so on. If you want to refresh your memory on the special graphs, we discussed them here.

There is also a wider programming lesson to be learned concerning ‘dynamic inheritance’. Each of these special graphs, take the linear graph for instance, might want to be directed or undirected, but how to model this? We want a general notion of a linear graph, that changes depending upon whether it is directed or undirected, meaning we would like a class that can somehow choose to inherit from different classes.

My solution for this problem is to wrap our class definition in a function, and so inheritance is decided at runtime! If you know of a better one, please let me know! Let’s see how it works for a linear graph.

#This is a wrapper to a class definition, deciding whether to inherit #from DirGraph or UnDirGraph at runtime. It can be initialised by #number of vertices or the number of edges. def return_linear_class(directed=False): if directed: base=DirGraph else: base=UnDirGraph class Linear(base, object): def __init__(self, number_vertices=0, number_edges=0, **kwargs): super(Linear, self).__init__(**kwargs) self.linear_generate(number_vertices, number_edges) def linear_generate(self,number_vertices, number_edges): if (not number_edges ==0) and (not number_vertices==0): if not number_vertices == number_edges+1: print 'Number of edges and vertices incompatible!' return else: self.number_vertices=number_vertices elif not number_edges==0: self.number_vertices = number_edges +1 else: self.number_vertices = number_vertices self.create_vertices(self.number_vertices) for index in range(self.number_vertices -1): Source = self.vertices[index] Target = self.vertices[index+1] self.create_edge([Source, Target]) return Linear

Now this gives us a class definition, but we still need to instantiate the class, which we also do with a function, this is straightforward. Notice that we use **kwargs to pass down any regular Graph or UnDirGraph or DirGraph arguments you might want to specify.

#This instantiates the Linear class. def create_linear(directed=False, number_vertices=0, number_edges=0,**kwargs): linear = return_linear_class(directed)(number_vertices, number_edges,**kwargs) return linear

And that is that. Now just so you believe that it works we will make a directed and undirected linear graph with 10 vertices and plot the results.

testdir=create_linear(number_vertices=10) testundir=create_linear(directed=True,number_vertices=10) testdir.plot() testundir.plot()

Producing the following images:

Notice that the plotting in igraph is sometimes a bit random!

Next up is cycle graphs, we do the same inheritance trick as before, and also we use object composition to build the cycle by joining the ends of a linear graph.

#Class definition wrapper to dynamically inherti from DirGraph or UnDirGraph. #Also has a composition from Linear, to create a cycle it joins the ends #of a linear graph. def return_cycle_class(directed=False): if directed: base = DirGraph else: base = UnDirGraph class Cycle(base, object): def __init__(self, number_vertices=0, number_edges=0, **kwargs): super(Cycle, self).__init__(**kwargs) if (not number_edges==0) and (not number_vertices==0): if not number_edges == number_vertices: print 'Numbers of edges and vertices incompatible!' return elif not number_edges ==0: number_vertices = number_edges Linear_part = create_linear() Linear_part.linear_generate(number_vertices, number_edges) self.vertices = Linear_part.vertices self.edges = Linear_part.edges self.cycle_generate(number_vertices) def cycle_generate(self, number_vertices): Target = self.vertices[0] Source = self.vertices[number_vertices-1] self.create_edge(ends=[Source, Target]) return Cycle

To test it I will show you an undirected cycle on 10 vertices.

t=create_cycle(number_edges=9) t.plot()

as desired.

Next up is the complete graph, very easy to do, I only made it for undirected graphs, but it could easily be altered to dynamically inherit.

class Complete(UnDirGraph, object): def __init__(self,number_vertices=0, **kwargs): super(Complete, self).__init__(**kwargs) self.create_vertices(no_create=number_vertices) ends=[] for Source in self.vertices: for Target in self.vertices: if [Source,Target] not in ends: if not Source == Target: self.create_edge(ends=[Source,Target]) ends.append([Source,Target]) ends.append([Target, Source])

Now writing

t = Complete(number_vertices=10) t.plot()

produces

Now we create a Tree class, along with a subclass of nary-trees.

def return_tree_class(directed=False): if directed: base = DirGraph else: base = UnDirGraph class Tree(base, object): def __init__(self, **kwargs): super(Tree, self).__init__(**kwargs) def is_leaf(self, vertex): if self.get_degree(vertex) == 1: return True elif self.get_number_vertices() ==1: return True else: return False def set_root(self, vertex): if vertex in self.vertices: self.remove_vertex_label('Root') self.add_vertex_label(vertex, label='Root') def get_root(self): return self.get_vertex('Root') def get_leaves(self): leaves = filter(self.is_leaf,self.vertices) return leaves return Tree def create_tree(directed=False, **kwargs): tree = return_tree_class(directed)(**kwargs) return tree def return_nary_tree_class(directed=False): base = return_tree_class(directed) class NaryRootedTree(base,object): def __init__(self, N=0, **kwargs): super(NaryRootedTree, self).__init__(**kwargs) self.N = N def split_vertex(self, vertex): if self.is_leaf(vertex): children = [self.Vertex() for i in range(self.N)] vertex.children = children self.leaves.discard(vertex) for Child in children: self.add_vertex(Child) self.leaves.add(Child) Child.parent=vertex self.create_edge(ends=[vertex, Child]) def fuse_vertex(self, vertex): try: children=vertex.children except AttributeError: return self.leaves.add(vertex) for child in children: self.fuse_vertex(child) self.remove_vertex(child) child.parent = None vertex.children = None def create_full_n_level(self, n): self.vertices =[] self.edges =set([]) self.create_vertex() self.set_root(self.vertices[0]) for level in range(n): leaves=self.find_leaves() for Leaf in leaves: self.split_vertex(Leaf) return NaryRootedTree def create_nary_tree(directed=False, N=0,**kwargs): nary_tree = return_nary_tree_class(directed)(N, **kwargs) return nary_tree

Let’s make a binary tree, since we are doing computer science after all.

t=create_nary_tree(N=2) t.create_full_n_level(n=6) t.plot()

Which looks like:

And that’s all folks! You find all the code for the graph stuff so far here. Let me know what you think!

Next time we will probably be looking at decision trees.

[…] we’ll create a binary tree, inheriting from the nary-tree class we made last time and also using our new DecisionNode […]

[…] Special Graphs and Dynamic Inheritance (triangleinequality.wordpress.com) […]

[…] Special Graphs and Dynamic Inheritance (triangleinequality.wordpress.com) […]

[…] 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 […]