Module 2, Practical 9

In this practical we will keep working with graphs.

Graphs recap

Graphs are mathematical structures made of two key elements: nodes (or vertices) and edges. Nodes are things that we want to represent and edges are relationships among the objects. Mathematically, a graph is an entity \(G = (N,E)\) where \(N\) is a set of nodes and \(E = N \times N\) is the set of edges.

Nodes are normally represented as circles, while edges (relationships) are represented by lines/arrows connecting nodes. An example follows:

_images/graph_1.png

Relations represented by edges can be transitive (e.g. sibling_of: if \(X\) is sibling of \(Y\) then \(Y\) is sibling of \(X\)) and in this case the edges are just lines rather than arrows. In this case the graph is directed. In case relationships are not transitive (i.e. \(X \rightarrow Y\) does not imply \(Y \rightarrow X\)) we put an arrow to indicate the direction of the relationship among the nodes and in this case we say the graph is undirected.

Some terminology (from the lecture):

_images/graphTerms.png

The degree of a node is the number of connection it has with other nodes. In directed graphs the in-degree is the number of incoming edges, while the out-degree is the number of outgoing edges.

_images/degree.png

A path in the graph is a sequence of nodes connected by edges.

_images/path.png

Up to now, we have seen two different strategies for implementing graphs: adjacency matrices and linked lists. In the remainder, we will work with the DiGraphLL and DiGraphLLAnalyzer class implemented in the previous practical.

Visits

Visiting graphs means traversing through its edges and nodes following the connections that make up the graph. Graphs can have cycles and this makes it quite tricky to visit the graph. Differently from what seen in the case of trees, we need to keep a data structure of visited nodes to avoid getting stuck in loops like the following (or you can pretty much end up in an infinite while loop):

_images/circle.png

Traversing a graph \(G = (V,E)\) in mathematical terms can be described as, given a node \(r\), visit all the nodes reachable from \(r\) going through the nodes exactly once.

As in the case of Trees, two ways exist to perform a visit of a graph: depth-first and breadth-first search.

As said above, the base class that we will extend is DiGraphLL, whose code is reported below as a reminder:

[3]:

class DiGraphLL:
    def __init__(self):
        """Every node is an element in the dictionary.
        The key is the node id and the value is a dictionary
        with second node as key and the weight as value
        """
        self.__nodes = dict()

    def insertNode(self, node):
        test = self.__nodes.get(node, None)

        if test == None:
            self.__nodes[node] = {}
            #print("Node {} added".format(node))

    def insertEdge(self, node1, node2, weight):
        test = self.__nodes.get(node1, None)
        test1 = self.__nodes.get(node2, None)
        if test != None and test1 != None:
            #if both nodes exist othewise don't do anything
            test = self.__nodes[node1].get(node2, None)
            if test != None:
                exStr = "Edge {} --> {} already existing.".format(node1,node2)
                raise Exception(exStr)
            else:
                #print("Inserted {}-->{} ({})".format(node1,node2,weight))
                self.__nodes[node1][node2] = weight

    def deleteNode(self, node):
        test = self.__nodes.get(node, None)
        if test != None:
            self.__nodes.pop(node)
        # need to loop through all the nodes!!!
        for n in self.__nodes:
            test = self.__nodes[n].get(node, None)
            if test != None:
                self.__nodes[n].pop(node)

    def deleteEdge(self, node1,node2):
        test = self.__nodes.get(node1, None)
        if test != None:
            test = self.__nodes[node1].get(node2, None)
            if test != None:
                self.__nodes[node1].pop(node2)

    def __len__(self):
        return len(self.__nodes)

    def nodes(self):
        return list(self.__nodes.keys())

    def graph(self):
        return self.__nodes

    def __str__(self):
        ret = ""
        for n in self.__nodes:
            for edge in self.__nodes[n]:
                ret += "{} -- {} --> {}\n".format(str(n),
                                                  str(self.__nodes[n][edge]),
                                                  str(edge))
        return ret

    def adjacent(self, node):
        """returns a list of nodes connected to node"""
        ret = []
        test = self.__nodes.get(node, None)
        if test != None:
            for n in self.__nodes:
                if n == node:
                    #all outgoing edges
                    for edge in self.__nodes[node]:
                        ret.append(edge)
                else:
                    #all incoming edges
                    for edge in self.__nodes[n]:
                        if edge == node:
                            ret.append(n)
        return ret

    def adjacentEdge(self, node, incoming = True):
        """
        If incoming == False
        we look at the edges of the node
        else we need to loop through all the nodes.
        An edge is present if there is a
        corresponding entry in the dictionary.
        If no such nodes exist returns None
        """
        ret = []
        if incoming == False:
            edges = self.__nodes.get(node,None)
            if edges != None:
                for e in edges:
                    w = self.__nodes[node][e]
                    ret.append((node, e, w))
                return ret
        else:
            for n in self.__nodes:
                edge = self.__nodes[n].get(node,None)
                if edge != None:
                    ret.append((n,node, edge))
            return ret

    def edges(self):
        """Returns all the edges in a list of triplets"""
        ret = []
        for node in self.__nodes:
            for edge in self.__nodes[node]:
                w = self.__nodes[node][edge]
                ret.append((node,edge, w))
        return ret

    def edgeIn(self,node1,node2):
        """Checks if edge node1 --> node2 is present"""
        n1 = self.__nodes.get(node1, None)
        if n1 != None:
            n2 = self.__nodes[node1].get(node2, None)
            if n2 != None:
                return True
            else:
                return False
        else:
            return False

Download the complete source file: DiGraphLL2.py

Depth First Search (DFS)

Depth-first search visits nodes of the graph going as deep as possible along each path.
This procedure is normally used to travel through all the nodes of the graph, and so it might have to be repeated several times (starting each time from a different node) as the output is, in general, a forest of DFS trees.
We have two possible versions of this algorithm: pre-order and post-order DFS.
This algorithm makes use of a stack (rather implicit, as done below by using recursion) or explicitly.

Example: Let’s implement DFS in the DiGraphLLAnalyzer class we implemented in the previous lab.

[4]:
from collections import deque

class DiGraphLL:

    # ... missing code ...

class DiGraphLLAnalyzer(DiGraphLL):
    """Every node is an element in the dictionary.
        The key is the node id and the value is a dictionary
        with key second node and value the weight
        """

    def getTopConnected_incoming(self):

        topN = ""
        #accumulator to count connections
        conn = [0]*len(self.nodes())
        for node in self.nodes():
            for el in self.graph()[node]:
                elInd = self.nodes().index(el)
                conn[elInd] +=1
        M = max(conn)
        ind = [x for x in range(len(conn)) if conn[x] == M]
        return [self.nodes()[x] for x in ind]

    def getTopConnected_outgoing(self):
        """Returns the node(s)"""
        topN = []
        conn = -1

        for node in self.nodes():
            n = len(self.graph()[node])
            if n > conn:
                topN = [node]
                conn = n
            else:
                if n == conn:
                    topN.append(node)

        return topN

    def hasPathAux(self, node1,node2):
        if node1 not in self.nodes() or node2 not in self.nodes():
            return False
        else:
            Q = deque()
            Q.append(node1)
            visited = set()
            while len(Q) > 0:
                curN = Q.popleft()
                #do not travel on already visited nodes
                if curN not in visited:
                    visited.add(curN)
                    #get all outgoing nodes of Q
                    for edge in self.graph()[curN]:
                        if edge == node2:
                            return True
                        else:
                            Q.append(edge)

            return False

    def hasPath(self, node1, node2):
        #checks both paths and returns True or false
        res = self.hasPathAux(node1,node2)
        if res:
            return True
        else:
            return self.hasPathAux(node2,node1)


    def DFSvisit(self, root, preorder = True, visited = set()):
        visited.add(root)
        if preorder:
            print("{}".format(root))
        #remember that the self.adjacentEdge method returns:
        #[('node1','node2', weight1), ...('node1', 'nodeX', weightX)]
        outGoingEdges = self.adjacentEdge(root, incoming = False)
        nextNodes = []
        if len(outGoingEdges) > 0:
            nextNodes = [x[1] for x in outGoingEdges]
            #print(nextNodes)
            for nextN in nextNodes:
                if nextN not in visited:
                    print("\tfrom {} --> {}".format(root, nextN))
                    self.DFSvisit(nextN, preorder, visited)
        if not preorder:
            print("{}".format(root))

if __name__ == "__main__":
    G = DiGraphLLAnalyzer()
    for i in range(1,10):
        G.insertNode("Node_" + str(i))

    G.insertEdge("Node_1", "Node_2",1)
    G.insertEdge("Node_2", "Node_1",1)
    G.insertEdge("Node_1", "Node_3",1)
    G.insertEdge("Node_1", "Node_5",1)
    G.insertEdge("Node_2", "Node_3",1)
    G.insertEdge("Node_2", "Node_5",1)
    G.insertEdge("Node_3", "Node_4",1)
    G.insertEdge("Node_3", "Node_6",1)
    G.insertEdge("Node_5", "Node_3",1)
    G.insertEdge("Node_5", "Node_5",1)
    G.insertEdge("Node_6", "Node_4",1)
    G.insertEdge("Node_6", "Node_6",1)
    G.insertEdge("Node_7", "Node_5",1)
    G.insertEdge("Node_5", "Node_8",1)
    G.insertEdge("Node_8", "Node_7",1)
    G.insertEdge("Node_9", "Node_2",1)

    print("Preorder:")
    G.DFSvisit("Node_1", preorder = True, visited = set())
    print("\nPostorder:")
    G.DFSvisit("Node_1", preorder = False, visited = set())

    print("\nPreorder from Node_9")
    G.DFSvisit("Node_9", preorder = True, visited = set())
Preorder:
Node_1
        from Node_1 --> Node_2
Node_2
        from Node_2 --> Node_3
Node_3
        from Node_3 --> Node_4
Node_4
        from Node_3 --> Node_6
Node_6
        from Node_2 --> Node_5
Node_5
        from Node_5 --> Node_8
Node_8
        from Node_8 --> Node_7
Node_7

Postorder:
        from Node_1 --> Node_2
        from Node_2 --> Node_3
        from Node_3 --> Node_4
Node_4
        from Node_3 --> Node_6
Node_6
Node_3
        from Node_2 --> Node_5
        from Node_5 --> Node_8
        from Node_8 --> Node_7
Node_7
Node_8
Node_5
Node_2
Node_1

Preorder from Node_9
Node_9
        from Node_9 --> Node_2
Node_2
        from Node_2 --> Node_1
Node_1
        from Node_1 --> Node_3
Node_3
        from Node_3 --> Node_4
Node_4
        from Node_3 --> Node_6
Node_6
        from Node_1 --> Node_5
Node_5
        from Node_5 --> Node_8
Node_8
        from Node_8 --> Node_7
Node_7

Download the complete source file: DiGraphLLAnalyzer2.py

To make sure we visit all nodes we need to modify the code in the following way:

[5]:
from collections import deque

class DiGraphLL:

    # ... missing code ...

class DiGraphLLAnalyzer(DiGraphLL):

    # ... missing code ...

    def DFSvisit(self, root, preorder = True, visited = set()):
        visited.add(root)
        if preorder:
            print("{}".format(root))
        #remember that the self.adjacentEdge method returns:
        #[('node1','node2', weight1), ...('node1', 'nodeX', weightX)]
        outGoingEdges = self.adjacentEdge(root, incoming = False)
        nextNodes = []
        if len(outGoingEdges) > 0:
            nextNodes = [x[1] for x in outGoingEdges]
            #print(nextNodes)
            for nextN in nextNodes:
                if nextN not in visited:
                    print("\tfrom {} --> {}".format(root, nextN))
                    self.DFSvisit(nextN, preorder, visited)
        if not preorder:
            print("{}".format(root))

    def DFS(self, root, preorder = True):
        visited = set()
        #first visit from specified node then check all other nodes
        #set is mutable so the set is going to change!
        print("Starting from {}".format(root))
        self.DFSvisit(root, preorder, visited)

        for node in self.nodes():
            if node not in visited:
                print("Starting from {}".format(node))
                self.DFSvisit(node, preorder, visited)


if __name__ == "__main__":
    G = DiGraphLLAnalyzer()
    for i in range(1,10):
        G.insertNode("Node_" + str(i))

    G.insertEdge("Node_1", "Node_2",1)
    G.insertEdge("Node_2", "Node_1",1)
    G.insertEdge("Node_1", "Node_3",1)
    G.insertEdge("Node_1", "Node_5",1)
    G.insertEdge("Node_2", "Node_3",1)
    G.insertEdge("Node_2", "Node_5",1)
    G.insertEdge("Node_3", "Node_4",1)
    G.insertEdge("Node_3", "Node_6",1)
    G.insertEdge("Node_5", "Node_3",1)
    G.insertEdge("Node_5", "Node_5",1)
    G.insertEdge("Node_6", "Node_4",1)
    G.insertEdge("Node_6", "Node_6",1)
    G.insertEdge("Node_7", "Node_5",1)
    G.insertEdge("Node_5", "Node_8",1)
    G.insertEdge("Node_8", "Node_7",1)
    G.insertEdge("Node_9", "Node_2",1)

    print("Preorder:")
    G.DFS("Node_1", preorder = True)
    print("\nPostorder:")
    G.DFS("Node_1", preorder = False)
    print("\nPostorder:")
    G.DFS("Node_5", preorder = False)
Preorder:
Starting from Node_1
Node_1
        from Node_1 --> Node_2
Node_2
        from Node_2 --> Node_3
Node_3
        from Node_3 --> Node_4
Node_4
        from Node_3 --> Node_6
Node_6
        from Node_2 --> Node_5
Node_5
        from Node_5 --> Node_8
Node_8
        from Node_8 --> Node_7
Node_7
Starting from Node_9
Node_9

Postorder:
Starting from Node_1
        from Node_1 --> Node_2
        from Node_2 --> Node_3
        from Node_3 --> Node_4
Node_4
        from Node_3 --> Node_6
Node_6
Node_3
        from Node_2 --> Node_5
        from Node_5 --> Node_8
        from Node_8 --> Node_7
Node_7
Node_8
Node_5
Node_2
Node_1
Starting from Node_9
Node_9

Postorder:
Starting from Node_5
        from Node_5 --> Node_3
        from Node_3 --> Node_4
Node_4
        from Node_3 --> Node_6
Node_6
Node_3
        from Node_5 --> Node_8
        from Node_8 --> Node_7
Node_7
Node_8
Node_5
Starting from Node_1
        from Node_1 --> Node_2
Node_2
Node_1
Starting from Node_9
Node_9

Download the complete source file: DiGraphLLAnalyzer3.py

The graph created above is:

_images/testgraph.png

Exercises

  1. Implement depth first search for the class DiGraphLLAnalyzer using an explicit stack and a pre-order visit of the nodes (to keep things simple). Remember that you can simulate a stack (FILO – first in last out queue) by using a list with append(elem) and pop(-1) (or collections.deque and the methods append(elem) and pop(). Use the pseudocode below (I suggest to use a set rather than a boolean list for the visited structure):

_images/dfs_pseudocode.png

You can test your methods with the following code:

G = DiGraphLLAnalyzer()
    G1 = DiGraphLLAnalyzer()
    for i in range(1,10):
        G.insertNode("Node_" + str(i))
        G1.insertNode("Node_" + str(i))

    G.insertEdge("Node_1", "Node_2",1)
    G.insertEdge("Node_2", "Node_1",1)
    G.insertEdge("Node_1", "Node_3",1)
    G.insertEdge("Node_1", "Node_5",1)
    G.insertEdge("Node_2", "Node_3",1)
    G.insertEdge("Node_2", "Node_5",1)
    G.insertEdge("Node_3", "Node_4",1)
    G.insertEdge("Node_3", "Node_6",1)
    G.insertEdge("Node_5", "Node_3",1)
    G.insertEdge("Node_5", "Node_5",1)
    G.insertEdge("Node_6", "Node_4",1)
    G.insertEdge("Node_6", "Node_6",1)
    G.insertEdge("Node_7", "Node_5",1)
    G.insertEdge("Node_5", "Node_8",1)
    G.insertEdge("Node_8", "Node_7",1)
    G.insertEdge("Node_9", "Node_2",1)
    #Graph G1
    G1.insertEdge("Node_1" ,"Node_2", 1)
    G1.insertEdge("Node_1" ,"Node_4", 1)
    G1.insertEdge("Node_1" ,"Node_6", 1)
    G1.insertEdge("Node_1" ,"Node_7", 1)
    G1.insertEdge("Node_2" ,"Node_7", 1)
    G1.insertEdge("Node_3" ,"Node_4", 1)
    G1.insertEdge("Node_5" ,"Node_4", 1)
    G1.insertEdge("Node_6" ,"Node_5", 1)
    G1.insertEdge("Node_6" ,"Node_8", 1)
    G1.insertEdge("Node_7" ,"Node_9", 1)
    G1.insertEdge("Node_8" ,"Node_9", 1)

    G.DFS("Node_1")
    G.DFS("Node_5")

    G1.DFS("Node_1")
    G1.DFS("Node_4")
    G1.DFS("Node_6")

Show/Hide Solution

  1. Write a method getDFStime(self,start_sort = True) that for each node of a DiGraphLLAnalyzer, returns its start and end time in a DFS visit. Time is just a counter that counts the visiting operations. Start time is when a node has first been encountered, and end time is when all its subgraph has been visited and the algorithm moved to another part of the graph. Sort the results by start time or by end time depending on the value of start_sort that can be True or False (Hint: use lambda functions with sort!).

Hint: implement another function (dfsTime(self, root, visited, times, time)) that performs a dfs of the graph updating a structure of start and end times (times) and keeping a counter (time) that increases step by step by one.

Test the code with the following two graphs G and G1 (checking them with the pictures below):

_images/g1_g2.png

that can be generated by the following code:

G = DiGraphLLAnalyzer()
G1 = DiGraphLLAnalyzer()
for i in range(1,10):
    G.insertNode("Node_" + str(i))
    G1.insertNode("Node_" + str(i))

G.insertEdge("Node_1", "Node_2",1)
G.insertEdge("Node_2", "Node_1",1)
G.insertEdge("Node_1", "Node_3",1)
G.insertEdge("Node_1", "Node_5",1)
G.insertEdge("Node_2", "Node_3",1)
G.insertEdge("Node_2", "Node_5",1)
G.insertEdge("Node_3", "Node_4",1)
G.insertEdge("Node_3", "Node_6",1)
G.insertEdge("Node_5", "Node_3",1)
G.insertEdge("Node_5", "Node_5",1)
G.insertEdge("Node_6", "Node_4",1)
G.insertEdge("Node_6", "Node_6",1)
G.insertEdge("Node_7", "Node_5",1)
G.insertEdge("Node_5", "Node_8",1)
G.insertEdge("Node_8", "Node_7",1)
G.insertEdge("Node_9", "Node_2",1)
#Graph G1
G1.insertEdge("Node_1" ,"Node_2", 1)
G1.insertEdge("Node_1" ,"Node_4", 1)
G1.insertEdge("Node_1" ,"Node_6", 1)
G1.insertEdge("Node_1" ,"Node_7", 1)
G1.insertEdge("Node_2" ,"Node_7", 1)
G1.insertEdge("Node_3" ,"Node_4", 1)
G1.insertEdge("Node_5" ,"Node_4", 1)
G1.insertEdge("Node_6" ,"Node_5", 1)
G1.insertEdge("Node_6" ,"Node_8", 1)
G1.insertEdge("Node_7" ,"Node_9", 1)
G1.insertEdge("Node_8" ,"Node_9", 1)

Show/Hide Solution

Breadth First Search (BFS)

Breadth-first search visits all the nodes starting from a root node and proceeding level by level.
This means that we first visit all the nodes at distance 1 from the root, then all the nodes at distance 2 and so on.
This algorithm, in general, does not visit all the nodes, but only those that are reachable from the specified root. If all nodes must be visited, another visit should start from a node not touched in the first visit.

This algorithm is quite useful to find the shortest path between two nodes.

Example: Let’s implement BFS in the DiGraphLLAnalyzer class.

[7]:
from collections import deque

class DiGraphLL:

    # ... missing code ...

class DiGraphLLAnalyzer(DiGraphLL):

    # ... missing code ...

    def BFSvisit(self, root):
        if root in self.graph():
            Q = deque()
            Q.append(root)
            #visited is a set of visited nodes
            visited = set()
            visited.add(root)
            while len(Q) > 0:
                curNode = Q.popleft()
                outGoingEdges = self.adjacentEdge(curNode, incoming = False)
                nextNodes = []
                if outGoingEdges != None:
                    #remember that self.adjacentEdge returns:
                    #[('node1','node2', weight1), ...('node1', 'nodeX', weightX)]
                    nextNodes = [x[1] for x in outGoingEdges]
                print("From {}:".format(curNode))
                for nextNode in nextNodes:
                    if nextNode not in visited:
                        Q.append(nextNode)
                        visited.add(nextNode)
                        print("\t --> {}".format(nextNode ))


if __name__ == "__main__":
    G = DiGraphLLAnalyzer()
    for i in range(1,10):
        G.insertNode("Node_" + str(i))

    G.insertEdge("Node_1", "Node_2",1)
    G.insertEdge("Node_2", "Node_1",1)
    G.insertEdge("Node_1", "Node_3",1)
    G.insertEdge("Node_1", "Node_5",1)
    G.insertEdge("Node_2", "Node_3",1)
    G.insertEdge("Node_2", "Node_5",1)
    G.insertEdge("Node_3", "Node_4",1)
    G.insertEdge("Node_3", "Node_6",1)
    G.insertEdge("Node_5", "Node_3",1)
    G.insertEdge("Node_5", "Node_5",1)
    G.insertEdge("Node_6", "Node_4",1)
    G.insertEdge("Node_6", "Node_6",1)
    G.insertEdge("Node_7", "Node_5",1)
    G.insertEdge("Node_5", "Node_8",1)
    G.insertEdge("Node_8", "Node_7",1)
    G.insertEdge("Node_9", "Node_2",1)

    print("BFS(Node_1):")
    G.BFSvisit("Node_1")
    print("\nNow BFS(Node_5):")
    G.BFSvisit("Node_5")
    print("\nNow BFS(Node_9):")
    G.BFSvisit("Node_9")
BFS(Node_1):
From Node_1:
         --> Node_2
         --> Node_3
         --> Node_5
From Node_2:
From Node_3:
         --> Node_4
         --> Node_6
From Node_5:
         --> Node_8
From Node_4:
From Node_6:
From Node_8:
         --> Node_7
From Node_7:

Now BFS(Node_5):
From Node_5:
         --> Node_3
         --> Node_8
From Node_3:
         --> Node_4
         --> Node_6
From Node_8:
         --> Node_7
From Node_4:
From Node_6:
From Node_7:

Now BFS(Node_9):
From Node_9:
         --> Node_2
From Node_2:
         --> Node_1
         --> Node_3
         --> Node_5
From Node_1:
From Node_3:
         --> Node_4
         --> Node_6
From Node_5:
         --> Node_8
From Node_4:
From Node_6:
From Node_8:
         --> Node_7
From Node_7:

The created graph is:

_images/testgraph.png

Download the complete source file: DiGraphLLAnalyzer4.py

To visit all the nodes of the tree and get a forest of BFS trees we need to modify the code as follows:

[8]:
from collections import deque

class DiGraphLL:

    # ... missing code ...

class DiGraphLLAnalyzer(DiGraphLL):

    # ... missing code ...

    def BFSvisit(self, root, target):
        len_path = 0

        if root in self.graph():
            Q = deque()
            Q.append(root)
            #visited is a set of visited nodes
            visited = set()
            if root == target:
                return len_path
            visited.add(root)
            while len(Q) > 0:
                curNode = Q.popleft()
                len_path = len_path + 1
                outGoingEdges = self.adjacentEdge(curNode, incoming = False)
                nextNodes = []
                if outGoingEdges != None:
                    #remember that self.adjacentEdge returns:
                    #[('node1','node2', weight1), ...('node1', 'nodeX', weightX)]
                    nextNodes = [x[1] for x in outGoingEdges]
                    if target in nextNodes:
                        return len_path + 1
                print("From {}:".format(curNode))
                for nextNode in nextNodes:
                    if nextNode not in visited:
                        Q.append(nextNode)
                        visited.add(nextNode)
                        print("\t --> {}".format(nextNode ))
            return None

    def BFS(self, root):
        print("Starting from {}".format(root))
        visited = set()
        visited.add(root)
        self.BFSvisit(root,visited)
        for node in self.nodes():
            if node not in visited:
                print("Starting from {}".format(node))
                self.BFSvisit(node,visited)


if __name__ == "__main__":
    G = DiGraphLLAnalyzer()
    for i in range(1,10):
        G.insertNode("Node_" + str(i))

    G.insertEdge("Node_1", "Node_2",1)
    G.insertEdge("Node_2", "Node_1",1)
    G.insertEdge("Node_1", "Node_3",1)
    G.insertEdge("Node_1", "Node_5",1)
    G.insertEdge("Node_2", "Node_3",1)
    G.insertEdge("Node_2", "Node_5",1)
    G.insertEdge("Node_3", "Node_4",1)
    G.insertEdge("Node_3", "Node_6",1)
    G.insertEdge("Node_5", "Node_3",1)
    G.insertEdge("Node_5", "Node_5",1)
    G.insertEdge("Node_6", "Node_4",1)
    G.insertEdge("Node_6", "Node_6",1)
    G.insertEdge("Node_7", "Node_5",1)
    G.insertEdge("Node_5", "Node_8",1)
    G.insertEdge("Node_8", "Node_7",1)
    G.insertEdge("Node_9", "Node_2",1)

    print("BFS(Node_1):")
    G.BFS("Node_1")
    print("\nNow BFS(Node_5):")
    G.BFS("Node_5")
    print("\nNow BFS(Node_9):")
    G.BFS("Node_9")
BFS(Node_1):
Starting from Node_1
From Node_1:
         --> Node_2
         --> Node_3
         --> Node_5
From Node_2:
From Node_3:
         --> Node_4
         --> Node_6
From Node_5:
         --> Node_8
From Node_4:
From Node_6:
From Node_8:
         --> Node_7
From Node_7:
Starting from Node_2
From Node_2:
         --> Node_1
         --> Node_3
         --> Node_5
From Node_1:
From Node_3:
         --> Node_4
         --> Node_6
From Node_5:
         --> Node_8
From Node_4:
From Node_6:
From Node_8:
         --> Node_7
From Node_7:
Starting from Node_3
From Node_3:
         --> Node_4
         --> Node_6
From Node_4:
From Node_6:
Starting from Node_4
From Node_4:
Starting from Node_5
From Node_5:
         --> Node_3
         --> Node_8
From Node_3:
         --> Node_4
         --> Node_6
From Node_8:
         --> Node_7
From Node_4:
From Node_6:
From Node_7:
Starting from Node_6
From Node_6:
         --> Node_4
From Node_4:
Starting from Node_7
From Node_7:
         --> Node_5
From Node_5:
         --> Node_3
         --> Node_8
From Node_3:
         --> Node_4
         --> Node_6
From Node_8:
From Node_4:
From Node_6:
Starting from Node_8
From Node_8:
         --> Node_7
From Node_7:
         --> Node_5
From Node_5:
         --> Node_3
From Node_3:
         --> Node_4
         --> Node_6
From Node_4:
From Node_6:
Starting from Node_9
From Node_9:
         --> Node_2
From Node_2:
         --> Node_1
         --> Node_3
         --> Node_5
From Node_1:
From Node_3:
         --> Node_4
         --> Node_6
From Node_5:
         --> Node_8
From Node_4:
From Node_6:
From Node_8:
         --> Node_7
From Node_7:

Now BFS(Node_5):
Starting from Node_5
From Node_5:
         --> Node_3
         --> Node_8
From Node_3:
         --> Node_4
         --> Node_6
From Node_8:
         --> Node_7
From Node_4:
From Node_6:
From Node_7:
Starting from Node_1
From Node_1:
         --> Node_2
         --> Node_3
         --> Node_5
From Node_2:
From Node_3:
         --> Node_4
         --> Node_6
From Node_5:
         --> Node_8
From Node_4:
From Node_6:
From Node_8:
         --> Node_7
From Node_7:
Starting from Node_2
From Node_2:
         --> Node_1
         --> Node_3
         --> Node_5
From Node_1:
From Node_3:
         --> Node_4
         --> Node_6
From Node_5:
         --> Node_8
From Node_4:
From Node_6:
From Node_8:
         --> Node_7
From Node_7:
Starting from Node_3
From Node_3:
         --> Node_4
         --> Node_6
From Node_4:
From Node_6:
Starting from Node_4
From Node_4:
Starting from Node_6
From Node_6:
         --> Node_4
From Node_4:
Starting from Node_7
From Node_7:
         --> Node_5
From Node_5:
         --> Node_3
         --> Node_8
From Node_3:
         --> Node_4
         --> Node_6
From Node_8:
From Node_4:
From Node_6:
Starting from Node_8
From Node_8:
         --> Node_7
From Node_7:
         --> Node_5
From Node_5:
         --> Node_3
From Node_3:
         --> Node_4
         --> Node_6
From Node_4:
From Node_6:
Starting from Node_9
From Node_9:
         --> Node_2
From Node_2:
         --> Node_1
         --> Node_3
         --> Node_5
From Node_1:
From Node_3:
         --> Node_4
         --> Node_6
From Node_5:
         --> Node_8
From Node_4:
From Node_6:
From Node_8:
         --> Node_7
From Node_7:

Now BFS(Node_9):
Starting from Node_9
From Node_9:
         --> Node_2
From Node_2:
         --> Node_1
         --> Node_3
         --> Node_5
From Node_1:
From Node_3:
         --> Node_4
         --> Node_6
From Node_5:
         --> Node_8
From Node_4:
From Node_6:
From Node_8:
         --> Node_7
From Node_7:
Starting from Node_1
From Node_1:
         --> Node_2
         --> Node_3
         --> Node_5
From Node_2:
From Node_3:
         --> Node_4
         --> Node_6
From Node_5:
         --> Node_8
From Node_4:
From Node_6:
From Node_8:
         --> Node_7
From Node_7:
Starting from Node_2
From Node_2:
         --> Node_1
         --> Node_3
         --> Node_5
From Node_1:
From Node_3:
         --> Node_4
         --> Node_6
From Node_5:
         --> Node_8
From Node_4:
From Node_6:
From Node_8:
         --> Node_7
From Node_7:
Starting from Node_3
From Node_3:
         --> Node_4
         --> Node_6
From Node_4:
From Node_6:
Starting from Node_4
From Node_4:
Starting from Node_5
From Node_5:
         --> Node_3
         --> Node_8
From Node_3:
         --> Node_4
         --> Node_6
From Node_8:
         --> Node_7
From Node_4:
From Node_6:
From Node_7:
Starting from Node_6
From Node_6:
         --> Node_4
From Node_4:
Starting from Node_7
From Node_7:
         --> Node_5
From Node_5:
         --> Node_3
         --> Node_8
From Node_3:
         --> Node_4
         --> Node_6
From Node_8:
From Node_4:
From Node_6:
Starting from Node_8
From Node_8:
         --> Node_7
From Node_7:
         --> Node_5
From Node_5:
         --> Node_3
From Node_3:
         --> Node_4
         --> Node_6
From Node_4:
From Node_6:

Download the complete source file: DiGraphLLAnalyzer5.py

Exercise

  1. Write a method shortestPath(self, node1, node2) that finds the shortest path between two nodes node1 and node2 (if it exists) ignoring any weight on the edges.

Hint: modify the BFS in such a way at it stops when the second node is reached (or when no more nodes can be explored). Apply this code twice, that is once from node1–>node2 and the other from node2–>node1 to find the shortest of the two. You need to change the code in order to obtain the path.

Structuring the code (hints):

  1. Implement a method shortestPath(self,node1,node2) that finds and prints the shortest path between node1 and node2 (testing both node1 –> node2 and node2 –> node1 and returning the shortest of the two) calling the other two functions;

  2. Implement a method path = findShortestPath(self,node1,node2) that returns the path going from node1 to node2 if this exist. Note: in my implementation, path is a list starting with the terminal node [node2, nodex, nodexx, node1] and ending with the first node of the sought path. The idea behind the implementation of this method is to store somewhere (like in a dictionary) the parent of each visited node and then produce the list above going backwards from node2 up to node1.

  3. Implement a method printPath(self,path) that gets a path as specified above and prints it out like:

Shortest path between: Node_1 and Node_6
Node_1 --> Node_3
    Node_3 --> Node_6

Test the code with the following two graphs G and G1 (checking them with the pictures below):

G = DiGraphLLAnalyzer()
G1 = DiGraphLLAnalyzer()
for i in range(1,10):
    G.insertNode("Node_" + str(i))
    G1.insertNode("Node_" + str(i))

G.insertEdge("Node_1", "Node_2",1)
G.insertEdge("Node_2", "Node_1",1)
G.insertEdge("Node_1", "Node_3",1)
G.insertEdge("Node_1", "Node_5",1)
G.insertEdge("Node_2", "Node_3",1)
G.insertEdge("Node_2", "Node_5",1)
G.insertEdge("Node_3", "Node_4",1)
G.insertEdge("Node_3", "Node_6",1)
G.insertEdge("Node_5", "Node_3",1)
G.insertEdge("Node_5", "Node_5",1)
G.insertEdge("Node_6", "Node_4",1)
G.insertEdge("Node_6", "Node_6",1)
G.insertEdge("Node_7", "Node_5",1)
G.insertEdge("Node_5", "Node_8",1)
G.insertEdge("Node_8", "Node_7",1)
G.insertEdge("Node_9", "Node_2",1)
#Graph G1
G1.insertEdge("Node_1" ,"Node_2", 1)
G1.insertEdge("Node_1" ,"Node_4", 1)
G1.insertEdge("Node_1" ,"Node_6", 1)
G1.insertEdge("Node_1" ,"Node_7", 1)
G1.insertEdge("Node_2" ,"Node_7", 1)
G1.insertEdge("Node_3" ,"Node_4", 1)
G1.insertEdge("Node_5" ,"Node_4", 1)
G1.insertEdge("Node_6" ,"Node_5", 1)
G1.insertEdge("Node_6" ,"Node_8", 1)
G1.insertEdge("Node_7" ,"Node_9", 1)
G1.insertEdge("Node_8" ,"Node_9", 1)

G.shortestPath("Node_1","Node_6")
G.shortestPath("Node_8","Node_9")
G.shortestPath("Node_8","Node_4")

print("\n\nG1:")
G1.shortestPath("Node_8","Node_4")
G1.shortestPath("Node_9","Node_1")
G1.shortestPath("Node_4","Node_1")
_images/g1_g2.png

Show/Hide Solution

Exercise

  1. Write a method isCyclic(self) that identifies if a direct graph (implemented as a DiGraphLLAnalyzer) is cyclic or not (i.e. returns True for a graph with cycles and False for a graph without cycles).

Hint: you can perform a recursive DFS and check if any edge that is being explored is actually a back-edge (i.e. an edge that points back to one of the nodes present in the recursion-stack of the nodes found so far). To do that you have to store a set of nodes that are along the path that is traversed recursively and check if the nodes that you are adding to the path are already present in this set of nodes).

Test the code with the following three graphs:

G = DiGraphLLAnalyzer()
    G1 = DiGraphLLAnalyzer()
    G2 = DiGraphLLAnalyzer()
    for i in range(1,10):
        G.insertNode("Node_" + str(i))
        G1.insertNode("Node_" + str(i))
        if i<9:
            G2.insertNode("Node_" + str(i))

    G.insertEdge("Node_1", "Node_2",1)
    G.insertEdge("Node_2", "Node_1",1)
    G.insertEdge("Node_1", "Node_3",1)
    G.insertEdge("Node_1", "Node_5",1)
    G.insertEdge("Node_2", "Node_3",1)
    G.insertEdge("Node_2", "Node_5",1)
    G.insertEdge("Node_3", "Node_4",1)
    G.insertEdge("Node_3", "Node_6",1)
    G.insertEdge("Node_5", "Node_3",1)
    G.insertEdge("Node_5", "Node_5",1)
    G.insertEdge("Node_6", "Node_4",1)
    G.insertEdge("Node_6", "Node_6",1)
    G.insertEdge("Node_7", "Node_5",1)
    G.insertEdge("Node_5", "Node_8",1)
    G.insertEdge("Node_8", "Node_7",1)
    G.insertEdge("Node_9", "Node_2",1)

    #Graph G1
    G1.insertEdge("Node_1" ,"Node_2", 1)
    G1.insertEdge("Node_1" ,"Node_4", 1)
    G1.insertEdge("Node_1" ,"Node_6", 1)
    G1.insertEdge("Node_1" ,"Node_7", 1)
    G1.insertEdge("Node_2" ,"Node_7", 1)
    G1.insertEdge("Node_3" ,"Node_4", 1)
    G1.insertEdge("Node_5" ,"Node_4", 1)
    G1.insertEdge("Node_6" ,"Node_5", 1)
    G1.insertEdge("Node_6" ,"Node_8", 1)
    G1.insertEdge("Node_7" ,"Node_9", 1)
    G1.insertEdge("Node_8" ,"Node_9", 1)

    #Graph G2
    G2.insertEdge("Node_1" ,"Node_2", 1)
    G2.insertEdge("Node_2" ,"Node_3", 1)
    G2.insertEdge("Node_2" ,"Node_4", 1)
    G2.insertEdge("Node_2" ,"Node_5", 1)
    G2.insertEdge("Node_6" ,"Node_2", 1)
    G2.insertEdge("Node_6" ,"Node_7",1)
    G2.insertEdge("Node_8" ,"Node_7", 1)
    G2.insertEdge("Node_8" ,"Node_4", 1)
    G2.insertEdge("Node_7" ,"Node_5", 1)

    print("Is G cyclic? {}".format(G.isCyclic()))
    print("\nG1:")
    print("Is G1 cyclic? {}".format(G1.isCyclic()))
    print("\nG2:")
    print("Is G2 cyclic? {}".format(G2.isCyclic()))

Here are the graphs:

_images/3g.png

Show/Hide Solution