Module 2 - Past Exams¶

class DiGraphLL:
    def __init__(self):
        self.nodes = dict()

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

        if test == None:
            self.nodes[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:
            test = self.nodes[node1].get(node2, None)
            if test != None:
                exStr= "Edge {} --> {} already existing.".format(node1,node2)
                raise Exception(exStr)
            else:
                self.nodes[node1][node2] = weight


    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

    # do not modify code ABOVE this line!

    def checkSelfEdge(self, node):
        """
        Return Boolean based on whether the node has a self-edge or not
        """
        raise NotImplementedError


    def isolatedNodes(self):
        """
        Return a list of isolated nodes (see pdf)
        """
        raise NotImplementedError


if __name__ == "__main__":

    G = DiGraphLL()
    for i in range(7):
        n = "Node_{}".format(i+1)
        G.insertNode(n)

    G.insertEdge("Node_2", "Node_1", 7)
    G.insertEdge("Node_1", "Node_2", 2)
    G.insertEdge("Node_1", "Node_4", 5)
    G.insertEdge("Node_2", "Node_5", 6)
    G.insertEdge("Node_6", "Node_5", 3)
    G.insertEdge("Node_4", "Node_5", 15)
    G.insertEdge("Node_6", "Node_6", 2)
    G.insertEdge("Node_7", "Node_7", 4)
    G.insertEdge("Node_4", "Node_4", 4)

    print("Size is: {}".format(len(G)))
    print("Nodes: {}".format(G.nodes))

    #PART 1
    print("\nPART 1\n")
    print("Check for self edge --> \n")
    print("Node_10:")
    print(G.checkSelfEdge("Node_10"))
    print("Node_2:")
    print(G.checkSelfEdge("Node_2"))
    print("Node_6:")
    print(G.checkSelfEdge("Node_6"))
    print("Node_7:")
    print(G.checkSelfEdge("Node_7"))

    print("\nPART 2\n")
    print("Isolated nodes:\n")
    print(G.isolatedNodes())

    assert(G.isolatedNodes() == ['Node_3', 'Node_7'])

import random

class SortingAlgorithm:
    def __init__(self, data, verbose = True):
        self.data = data
        self.comparisons = 0
        self.operations = 0
        self.verbose = verbose

    def getData(self):
        return self.data

    def getOperations(self):
        return self.operations

    def getComparisons(self):
        return self.comparisons

    def sort(self):
        raise NotImplementedError

class GnomeSort(SortingAlgorithm):

    def sort(self):
        self.comparisons = 0
        self.operations = 0
        """
        to implement
        """


if __name__ == "__main__":

    d = [7, 5, 10, -11 ,3, -4, 99, 1]
    print("Before sorting:\n")
    print(d)
    gnSort = GnomeSort(d, verbose = True)
    gnSort.sort()
    print("After sorting:\n")
    print(d)
    d = []

    for i in range(0,1000):
        d.append(random.randint(0,1000))
    gnSort = GnomeSort(d, verbose = False)
    gnSort.sort()
    print("\nNumber of elements: {}".format(len(d)))
    print("Number of comparisons: {}".format(gnSort.getComparisons()))
    print("Number of swaps: {}".format(gnSort.getOperations()))

    d = []
    for i in range(0,2000):
        d.append(random.randint(0,1000))
    gnSort = GnomeSort(d, verbose = False)
    gnSort.sort()
    print("\nNumber of elements: {}".format(len(d)))
    print("Number of comparisons: {}".format(gnSort.getComparisons()))
    print("Number of swaps: {}".format(gnSort.getOperations()))

    test = True
    for el in range(0,len(d)-1):
        test = test and (d[el]<= d[el+1])
    print("\nSorting test passed? {}".format(test))

class DiGraphLL:
    def __init__(self):
        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 __len__(self):
        return len(self.nodes)

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


    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 MinNumConnection(self, n):
        """
        Methods that returns the nodes with at least n incoming edges
        """
        raise NotImplementedError


    def edgeWeightSum(self):
        """
        Methods that returns the sum of all the edges
        """
        sum_weights = 0
        raise NotImplementedError



if __name__ == "__main__":
    G = DiGraphLL()

    for i in range(6):
        n = "Node_{}".format(i+1)
        G.insertNode(n)


    for i in range(2,4):
        n = "Node_" + str(i+1)
        six = "Node_6"
        n_plus = "Node_" + str((i+2) % 6)
        G.insertEdge(n, n_plus,3)
        G.insertEdge(n, six,2)

    G.insertEdge("Node_2","Node_1",3)
    G.insertEdge("Node_2","Node_4",4)
    G.insertEdge("Node_5","Node_4",10)
    G.insertEdge("Node_5", "Node_1", 4)
    G.insertEdge("Node_5", "Node_6", 2)
    G.insertEdge("Node_6", "Node_6", 2)
    print(G)

    #part 1
    print("\n Nodes with at least n incoming edges:\n")
    assert(['Node_1', 'Node_4', 'Node_5', 'Node_6'] == G.MinNumConnection(1))
    print("n=1 --> "+ str(G.MinNumConnection(1)))
    assert(['Node_1', 'Node_4', 'Node_6'] == G.MinNumConnection(2))
    print("n=2 --> "+ str(G.MinNumConnection(2)))
    assert(['Node_4' , 'Node_6'] == G.MinNumConnection(3))
    print("n=3 --> "+ str(G.MinNumConnection(3)))
    assert(['Node_6'] == G.MinNumConnection(4))
    print("n=4 --> "+ str(G.MinNumConnection(4)))
    assert([] == G.MinNumConnection(5))
    print("n=5 --> "+ str(G.MinNumConnection(5)))

    #part 2

    print("\nSum of all weights: ")
    print(G.edgeWeightSum())
    assert(35 == G.edgeWeightSum())