Extra Credit

DFS.py

#Depth First Search

from collections import OrderedDict

class priorityQueue:
    def __init__(self):
        self.heap=OrderedDict()
        self.size = 0

    def __len__(self):
        return self.size



    def parent(self,index):
        keys = list(self.heap.keys())
        values = self.heap.values()
        index = keys.index(index)+1
        if index > self.size or index <= 1:
            return None
        else:
            return keys[index // 2 -1]

    def rightChild(self,index):
        keys = list(self.heap.keys())
        values = self.heap.values()
        index = keys.index(index)+1
        if index < 1 or 2*index > self.size:
            return None
        else:
            if 2*index == self.size:
                return keys[2*index-1]
            else:
                return keys[2*index]

    def leftChild(self,index):
        keys = list(self.heap.keys())
        values = self.heap.values()
        index = keys.index(index)+1
        if index < 1 or 2*index+1 > self.size:
            return None
        else:
            return keys[2*index-1]

    def add(self, x):
        self.size += 1
        self.heap[x] = False

    def _depthfirstsearch(self, current, dest, path = []):
        #print(current)
        keys = list(self.heap.keys())
        #print(keys)
        values = self.heap.values()
        candidates = [self.leftChild(current), self.rightChild(current)]
        #print(current, candidates)
        if dest in candidates:
            path.append(dest)
            return path
        elif candidates[0] == None or self.heap[candidates[0]] == True:
            if candidates[1] == None or self.heap[candidates[1]] == True:
                return self._depthfirstsearch(self.parent(current), dest, path)
            else:
                self.heap[candidates[1]] = True
                path.append(candidates[1])
                return self._depthfirstsearch(candidates[1], dest, path)
        elif [values[keys.index(candidates[0])], values[keys.index(candidates[1])]] == [False, False]:
            if candidates[0] < candidates[1]:
                self.heap[candidates[0]] = True
                path.append(candidates[0])
                return self._depthfirstsearch(candidates[0], dest, path)
            else:
                self.heap[candidates[1]] = True
                path.append(candidates[1])
                return self._depthfirstsearch(candidates[1], dest, path)
        else:
            self.heap[candidates[0]] = True
            path.append(candidates[0])
            return self._depthfirstsearch(candidates[0], dest, path)

    def depthfirstsearch(self, x, y):
        path = [x] + self._depthfirstsearch(x,y)
        return path




#Test code
h = priorityQueue()
h.add('A')
h.add('B')
h.add('C')
h.add('D')
h.add('E')
h.add('F')
h.add('G')
h.add('H')
h.add('I')
h.add('R')
print("Visited Nodes to reach destination", h.depthfirstsearch('A','F'))