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:

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

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.

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

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

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:

[1]:

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.

[3]:

from collections import deque


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

If you look at the output of preorder visit from Node_1 you’ll notice that were are not visiting Node_9.

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

[6]:

from collections import deque



class DiGraphLLAnalyzer(DiGraphLL):

    # ... missing code ... same as above

    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 (except for the weights of the edges) is:

Exercises¶

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

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

[9]:

from collections import deque



class DiGraphLLAnalyzer(DiGraphLL):

    # ... missing code ...

    def DFSvisit(self, root, visited = set()):
        S = deque() # the stack
        S.append(root)
        order = 1
        while len(S) > 0:
            curNode = S.pop()
            if curNode not in visited:
                #pre-order visit
                print("{} (visit order: {})".format(curNode,order))
                order += 1
                visited.add(curNode)
                #remember that self.adjacentEdge returns:
                #[('node1','node2', weight1), ...('node1', 'nodeX', weightX)]
                outGoingEdges = self.adjacentEdge(curNode, incoming = False)
                nextNodes = []
                if len(outGoingEdges) > 0:
                    nextNodes = [x[1] for x in outGoingEdges]
                    #print(nextNodes)
                    for nextN in nextNodes:
                        print("\tfrom {} --> {}".format(curNode, nextN))
                        S.append(nextN)

    def DFS(self, root):
        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, visited)

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

if __name__ == "__main__":
    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)

    print("G from Node_1:")
    G.DFS("Node_1")
    print("\n\nG from Node_5:")
    G.DFS("Node_5")
    print("\n\nG1:")
    print("G1 from Node_1:")
    G1.DFS("Node_1")
    print("\nG1 from Node_4:")
    G1.DFS("Node_4")
    print("\nG1 from Node_6:")
    G1.DFS("Node_6")

G from Node_1:
Starting from Node_1
Node_1 (visit order: 1)
        from Node_1 --> Node_2
        from Node_1 --> Node_3
        from Node_1 --> Node_5
Node_5 (visit order: 2)
        from Node_5 --> Node_3
        from Node_5 --> Node_5
        from Node_5 --> Node_8
Node_8 (visit order: 3)
        from Node_8 --> Node_7
Node_7 (visit order: 4)
        from Node_7 --> Node_5
Node_3 (visit order: 5)
        from Node_3 --> Node_4
        from Node_3 --> Node_6
Node_6 (visit order: 6)
        from Node_6 --> Node_4
        from Node_6 --> Node_6
Node_4 (visit order: 7)
Node_2 (visit order: 8)
        from Node_2 --> Node_1
        from Node_2 --> Node_3
        from Node_2 --> Node_5
Starting from Node_9
Node_9 (visit order: 1)
        from Node_9 --> Node_2


G from Node_5:
Starting from Node_5
Node_5 (visit order: 1)
        from Node_5 --> Node_3
        from Node_5 --> Node_5
        from Node_5 --> Node_8
Node_8 (visit order: 2)
        from Node_8 --> Node_7
Node_7 (visit order: 3)
        from Node_7 --> Node_5
Node_3 (visit order: 4)
        from Node_3 --> Node_4
        from Node_3 --> Node_6
Node_6 (visit order: 5)
        from Node_6 --> Node_4
        from Node_6 --> Node_6
Node_4 (visit order: 6)
Starting from Node_1
Node_1 (visit order: 1)
        from Node_1 --> Node_2
        from Node_1 --> Node_3
        from Node_1 --> Node_5
Node_2 (visit order: 2)
        from Node_2 --> Node_1
        from Node_2 --> Node_3
        from Node_2 --> Node_5
Starting from Node_9
Node_9 (visit order: 1)
        from Node_9 --> Node_2


G1:
G1 from Node_1:
Starting from Node_1
Node_1 (visit order: 1)
        from Node_1 --> Node_2
        from Node_1 --> Node_4
        from Node_1 --> Node_6
        from Node_1 --> Node_7
Node_7 (visit order: 2)
        from Node_7 --> Node_9
Node_9 (visit order: 3)
Node_6 (visit order: 4)
        from Node_6 --> Node_5
        from Node_6 --> Node_8
Node_8 (visit order: 5)
        from Node_8 --> Node_9
Node_5 (visit order: 6)
        from Node_5 --> Node_4
Node_4 (visit order: 7)
Node_2 (visit order: 8)
        from Node_2 --> Node_7
Starting from Node_3
Node_3 (visit order: 1)
        from Node_3 --> Node_4

G1 from Node_4:
Starting from Node_4
Node_4 (visit order: 1)
Starting from Node_1
Node_1 (visit order: 1)
        from Node_1 --> Node_2
        from Node_1 --> Node_4
        from Node_1 --> Node_6
        from Node_1 --> Node_7
Node_7 (visit order: 2)
        from Node_7 --> Node_9
Node_9 (visit order: 3)
Node_6 (visit order: 4)
        from Node_6 --> Node_5
        from Node_6 --> Node_8
Node_8 (visit order: 5)
        from Node_8 --> Node_9
Node_5 (visit order: 6)
        from Node_5 --> Node_4
Node_2 (visit order: 7)
        from Node_2 --> Node_7
Starting from Node_3
Node_3 (visit order: 1)
        from Node_3 --> Node_4

G1 from Node_6:
Starting from Node_6
Node_6 (visit order: 1)
        from Node_6 --> Node_5
        from Node_6 --> Node_8
Node_8 (visit order: 2)
        from Node_8 --> Node_9
Node_9 (visit order: 3)
Node_5 (visit order: 4)
        from Node_5 --> Node_4
Node_4 (visit order: 5)
Starting from Node_1
Node_1 (visit order: 1)
        from Node_1 --> Node_2
        from Node_1 --> Node_4
        from Node_1 --> Node_6
        from Node_1 --> Node_7
Node_7 (visit order: 2)
        from Node_7 --> Node_9
Node_2 (visit order: 3)
        from Node_2 --> Node_7
Starting from Node_3
Node_3 (visit order: 1)
        from Node_3 --> Node_4

Download the complete source file: DiGraphLLAnalyzerEx1.py

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

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

[11]:

from collections import deque


class DiGraphLLAnalyzer(DiGraphLL):

    # ... missing code ...

    def dfsTime(self, root, visited, times, time = 1):
        visited.add(root)
        #print("\t--> {}".format(root))
        start = int(time)
        time = int(time) + 1
        #print("\tStack:{}".format(recStack))
        outGoingEdges = self.adjacentEdge(root, incoming = False)
        #print(outGoingEdges)
        nextNodes = []
        if len(outGoingEdges) > 0:
            nextNodes = [x[1] for x in outGoingEdges]

            for nextN in nextNodes:
                if nextN not in visited:
                    end = self.dfsTime(nextN, visited, times,time)
                    time = end
                    time += 1

        times[root]=(start, time)

        return time

    def getDFStime(self, start_sort = True):
        visited = set()
        times = dict()
        time = 1
        for node in self.nodes():
            if node not in visited:
                print("Starting from {}".format(node))
                time = self.dfsTime(node, visited,times, time)

        sortRes = []
        for node in self.nodes():
             sortRes.append((node,times[node][0],times[node][1]))

        if start_sort:
            sortRes.sort(key = lambda el : el[1])
        else:
            sortRes.sort(key = lambda el : el[2])

        for i in range(len(sortRes)):
            print("[{}] {} start Time: {} end Time: {}".format(i+1,
                                                              sortRes[i][0],
                                                              sortRes[i][1],
                                                              sortRes[i][2]))


if __name__ == "__main__":
    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)

    print("G (sorted by start):")
    G.getDFStime(start_sort = True)
    print("\nG (sorted by end):")
    G.getDFStime(start_sort = False)
    print("\nG1 (sorted by end):")
    G1.getDFStime(start_sort = False)

G (sorted by start):
Starting from Node_1
Starting from Node_9
[1] Node_1 start Time: 1 end Time: 16
[2] Node_2 start Time: 2 end Time: 15
[3] Node_3 start Time: 3 end Time: 8
[4] Node_4 start Time: 4 end Time: 5
[5] Node_6 start Time: 6 end Time: 7
[6] Node_5 start Time: 9 end Time: 14
[7] Node_8 start Time: 10 end Time: 13
[8] Node_7 start Time: 11 end Time: 12
[9] Node_9 start Time: 16 end Time: 17

G (sorted by end):
Starting from Node_1
Starting from Node_9
[1] Node_4 start Time: 4 end Time: 5
[2] Node_6 start Time: 6 end Time: 7
[3] Node_3 start Time: 3 end Time: 8
[4] Node_7 start Time: 11 end Time: 12
[5] Node_8 start Time: 10 end Time: 13
[6] Node_5 start Time: 9 end Time: 14
[7] Node_2 start Time: 2 end Time: 15
[8] Node_1 start Time: 1 end Time: 16
[9] Node_9 start Time: 16 end Time: 17

G1 (sorted by end):
Starting from Node_1
Starting from Node_3
[1] Node_9 start Time: 4 end Time: 5
[2] Node_7 start Time: 3 end Time: 6
[3] Node_2 start Time: 2 end Time: 7
[4] Node_4 start Time: 8 end Time: 9
[5] Node_5 start Time: 11 end Time: 12
[6] Node_8 start Time: 13 end Time: 14
[7] Node_6 start Time: 10 end Time: 15
[8] Node_1 start Time: 1 end Time: 16
[9] Node_3 start Time: 16 end Time: 17

Download the complete source file: DiGraphLLAnalyzerEx2.py

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.

[17]:

from collections import deque


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("\n------------")
    print("\nNow BFS(Node_5):")
    G.BFSvisit("Node_5")
    print("\n------------")
    print("\nNow BFS(Node_9):")
    G.BFSvisit("Node_9")
    print("\n------------")

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 (do not look at the weights):

Download the complete source file: DiGraphLLAnalyzer4.py

Also in this case Node_9 is not visited! (if you start from Node_1)

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

[18]:

from collections import deque


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("\n------------")
    print("\nNow BFS(Node_5):")
    #G.BFS("Node_5")
    print("\n------------")
    print("\nNow BFS(Node_9):")
    #G.BFS("Node_9")
    print("\n------------")

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

------------

Now BFS(Node_9):

------------

Download the complete source file: DiGraphLLAnalyzer5.py

Exercise¶

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

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;
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.
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")

Show/Hide Solution

[ ]:

from collections import deque

class DiGraphLL:

    # ... missing code ...

class DiGraphLLAnalyzer(DiGraphLL):

    # ... missing code ...

    def findShortestPath(self, node1, node2):
        Q = deque()
        Q.append(node1)
        visited = set()
        #visited is a set of visited nodes
        visited.add(node1)
        #for each node (apart from node1)
        #this will store the node that led to it
        #eg. if path is node1--> node3-->node2
        # previous[node2] = node3
        # previous[node3] = node1
        previous = dict()
        found = False
        while len(Q) > 0 and not found:
            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]

            for nextNode in nextNodes:
                if nextNode not in visited:
                    if nextNode == node2:
                        previous[node2] = curNode
                        found = True
                    else:
                        Q.append(nextNode)
                        visited.add(nextNode)
                        previous[nextNode] = curNode


        #if node2 is in the previous dictionary:
        ret = [node2]
        p = previous.get(node2, None)

        while p != None:
            ret.append(p)
            p = previous.get(p,None)

        #note that ret has the reverseof the path
        #[node2, node3, node1]
        #or just [node2] if not path exists
        return ret

    def printPath(self,path):
        L = len(path)
        print("Shortest path between: {} and {}".format(path[-1],
                                                            path[0])
                 )
        for i in range(len(path) -1,0,-1):
            print("{}{} --> {}".format("\t"*(L-i-1),
                                       path[i],
                                       path[i-1]))

    def shortestPath(self, node1, node2):
        nodes = self.nodes()
        if node1 not in nodes or node2 not in nodes:
            """one of the two is not in the graph"""
            return None
        else:
            if node1 == node2:
                """the path is just the node"""
                return node1
            else:

                path = self.findShortestPath(node1,node2)
                path1 = self.findShortestPath(node2,node1)
                if path == [node2] and path1 == [node1]:
                    print("No paths exist between {} and {}".format(node1,
                                                                    node2))
                else:
                    L = len(nodes)
                    L1 = L
                    if path != [node2]:
                        L = len(path)
                    if path1 != [node1]:
                        L1 = len(path1)

                    if L < L1:
                        """print first path"""
                        self.printPath(path)

                    else:
                        """print second path"""
                        self.printPath(path1)


if __name__ == "__main__":
    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")
    G.shortestPath("Node_9","Node_4")

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

Shortest path between: Node_1 and Node_6
Node_1 --> Node_3
        Node_3 --> Node_6
Shortest path between: Node_9 and Node_8
Node_9 --> Node_2
        Node_2 --> Node_5
                Node_5 --> Node_8
Shortest path between: Node_8 and Node_4
Node_8 --> Node_7
        Node_7 --> Node_5
                Node_5 --> Node_3
                        Node_3 --> Node_4
Shortest path between: Node_9 and Node_4
Node_9 --> Node_2
        Node_2 --> Node_3
                Node_3 --> Node_4


G1:
No paths exist between Node_8 and Node_4
Shortest path between: Node_1 and Node_9
Node_1 --> Node_7
        Node_7 --> Node_9
Shortest path between: Node_1 and Node_4
Node_1 --> Node_4

Download the complete source file: DiGraphLLAnalyzerEx3.py

Exercise¶

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:

Show/Hide Solution

[ ]:

from collections import deque

class DiGraphLL:

    # ... missing code ...

class DiGraphLLAnalyzer(DiGraphLL):

    # ... missing code ...

    def testCyclic(self, root, visited, recStack = set()):
        visited.add(root)
        recStack.add(root)
        ## Uncomment print lines to see what is going on
        print("CURRENT: {}".format(root))
        print("\tStack:{}".format(recStack))
        outGoingEdges = self.adjacentEdge(root, incoming = False)
        nextNodes = []
        if len(outGoingEdges) > 0:
            nextNodes = [x[1] for x in outGoingEdges]
            print("\tNEXTnodes:{}".format(nextNodes))
            for nextN in nextNodes:
                if nextN not in visited:
                    print("\tNext:{}".format(nextN))
                    if self.testCyclic(nextN,visited,recStack) == True:
                        return True
                else:
                    if nextN in recStack:
                        print("\t{} --> {} closes cycle".format(root,nextN))
                        return True

        #when the recursion ends
        #we remove the element from the stack
        recStack.pop()
        return False

    def isCyclic(self):
        visited = set()
        ret = False
        stack = set()
        for node in self.nodes():
            if node not in visited:
                ret = ret or self.testCyclic(node, visited, stack)
        return ret

if __name__ == "__main__":
    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()))

Download the complete source file: DiGraphLLAnalyzerEx4.py