Classes For Graphs and Directed Graphs In Python: Graph Theory

In computer science and mathematics, graphs are ubiquitous. They are just everywhere. We use graphs to solve a lot of problems that involve relationships. Since 1735 when the Swiss Mathematician, Leonhard Euler, used what we now know as graph theory to solve the Seven Bridges of Königsberg problem, graphs have become a brand name of sorts. That is why I decided to write a post on graphs and explore graphs in subsequent posts.

 

What are graphs?

In simple terms, graphs are structures used to represent the relationship between objects (called vertices or nodes) where two objects (or nodes) have an edge connecting them if they are related. Diagrammatically, they are depicted with a set of dots or circles for the objects or nodes, and related objects are joined by lines called edges.

The graph below has 6 nodes or vertices, and 7 edges.

 

The edges of a graph may be directed or undirected.

I will be writing code for both directed and undirected graphs. What made me attracted to writing code on graphs was because they are used in every area of life. From scientists to businesses, graphs are used to model solutions to problems.

So, let’s start with writing classes for graphs and we will implement them.

First, we’ll create a class for a Node and an Edge.

A node is just an object in a graph. One attribute every object has is a Name. So, we’ll give our node a name attribute to start with. Here is the code for the Node class.

    
class Node(object):

    def __init__(self, name):
        ''' assumes name a string '''
        self.name = name

    def get_name(self):
        return self.name

    def __str__(self):
        return self.name

Every instance of a Node, as you can see from the code, has a name and each instance has a method, get_name, which you can use to retrieve the name.

An edge is a relation connector between objects. If two objects are connected to each other by a relationship, they will have an edge between them. Edges can be directed or non-directed. Let’s model the Edge class to start with.

    
class Edge(object):

    def __init__(self, src, dest):
        '''assume src and dest are nodes '''
        self.src = src
        self.dest = dest

    def get_source(self):
        return self.src

    def get_destination(self):
        return self.dest

    def __str__(self):
        return self.src.get_name() + '-->' + \
            self.dest.get_name()

From the code you can see that each instance of an Edge has a source node, self.src, and a destination node, self.dest. On creation of a node the source and destination nodes have to be passed as arguments to the constructor, __init__. Then I added a special method for representing an Edge as a string of source and destination nodes, __str__(). This would make for easy printing.

Now that we have the Node and Edge classes, let us go on to model the directed graphs and undirected graphs.

Directed graphs in Python code

A directed graph is a graph in which edges have orientations. The relationship in directed graphs goes one-sided and never both way. The edges are represented by arrows.

A simple class for a directed graph might be written in the following way:

    
class Digraph(object):
    # nodes is a list of the nodes in the graph
    # edges is a dict mapping each node to 
    # a list of its children 
    def __init__(self):
        self.nodes = []
        self.edges = {}

    def add_node(self, node):
        if node in self.nodes:
            raise ValueError('Duplicate Node')
        else:
            self.nodes.append(node)
            self.edges[node] = []

    def add_edge(self, edge):
        src = edge.get_source()
        dest = edge.get_destination()
        if not (src in self.nodes and dest in self.nodes):
            raise ValueError('Node not in graph')
        self.edges[src].append(dest)

    def children_of(self, node):
        return self.edges[node]

    def has_node(self, node):
        return node in self.nodes

    def __str__(self):
        result = ''
        for src in self.nodes:
            for dest in self.edges[src]:
                result = result + src.get_name() + \
                    '-->' + dest.get_name() + '\n'
        return result[:-1] # remove last newline

The class, Digraph, represents a class for objects of a directed graph. If you look at the constructor, we are representing all the nodes in the graph as a list, while the edges are represented by a mapping of nodes to child nodes which mapping goes only one way. Therefore, a dictionary data structure was used for this mapping. To have a graph, it needs nodes. To add a node, we use the method add_node that takes a node as its sole argument. To add a node, we need first to check if the node already exists in the list of nodes and if it does, the method raises a ValueError. If not, it then appends the node to the list of nodes in the graph and then creates a mapping for that node with its values as an empty list that would later be populated when edges are added. To add an edge to the graph, we use the add_edge method. We first initialize the source and destination nodes of the edge, and before adding the edge we check that the source and destination nodes are already in the list of nodes for the graph. If they are not in the list, we raise a ValueError exception. If no exception is raised, a directed edge is created with the source, src, mapped to its value, the destination node, dest. The class also has complementary methods, children_of, that would bring out a list of the nodes connected to that node as source, and also another method, has_node, that returns a Boolean value after evaluating whether the node in question is in the list of nodes for the graph.

That sums up our directed graph, Digraph, class. Now, let’s show that the code works. Let’s implement it by creating an instance of a directed graph, or Digraph. The Digraph instance I will be creating will be based on the directed graph below with 5 nodes and 6 edges. 

 

The only new code is the driver code that creates a Digraph instance. For the sake of brevity, I would recommend that you read the driver code starting from line 67 down to line 106. It is really an exciting code. I hope you appreciate it.

Now the question I asked myself is: why create a class for a graph and not just write code direct? This is because I would be reusing the code in the future. So, we will be coming back to this code for solving problems involving graphs in the future. Maybe you could bookmark this code for the Digraph class. You can download the file here, directed_graph.py.

Undirected graphs or simple graphs in Python code.

An undirected graph or graph for short is a connection between a pair of nodes using their edges. The edges can go both ways which distinguishes it from directed graphs that have orientations.

Now while writing the code for undirected graphs, I ran into a dilemma about inheritance. I was stuck between which graph should inherit from which. Should a directed graph inherit from a undirected graph or should it be vice versa? I decided that it was best for a graph to inherit from a directed graph. This was because instances of graphs can substitute for instances of digraphs and still add one more behavior by making the relationship go the other way. But instances of digraphs cannot stand as substitutes for instances of graphs; digraphs relationship goes only one way. Therefore, I decided to make digraph the superclass and graph the subclass.

Now, this is the code for the class graph.

    
class Graph(Digraph):

    def add_edge(self, edge):
        Digraph.add_edge(self, edge)
        rev = Edge(edge.get_destination(), edge.get_source())
        Digraph.add_edge(self, rev)                                            

Notice that the class, Graph, is inheriting from Digraph so it shares the same attributes with Digraph instances but it only overrides the add_edge method of Digraph. In the add_edge method of Graph I made it that the relationship can go both ways i.e every node in a relationship or edge is both a source and destination node for that edge.

So, for a little implementation that creates an instance of a Graph, I will be modeling the Graph pictured below:

 

Run the code and notice the differences between this instance of a Graph and instances of a Digraph. The driver code that creates the Graph instances starts at line 73. You can alternatively download the code and run it on your own machine, graph.py script, so you can bookmark it.

I hope to see you in the future when we begin solving problems with graphs like the traveling salesman problem. To receive updates when I post new articles, just subscribe to my blog.

Happy pythoning.