Home » maths » graph theory » Special Graphs and Dynamic Inheritance

# Special Graphs and Dynamic Inheritance

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()
```

Producing:

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')

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
for Child in children:
Child.parent=vertex
self.create_edge(ends=[vertex, Child])

def fuse_vertex(self, vertex):
try:
children=vertex.children
except AttributeError:
return
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.