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