#This python file is used to search the tree
from collections import deque
class GraphSearcher:
    res = []
    flag = [];
    adjMat = [];
    nodeNames = [];
    def init(self, fileName, nodeNameFile):
        #reset everything
        self.res = []
        self.adjMat = []
        self.nodeNames = []
        self.flag = []
        f = open(fileName, "r");
        for line in f:
            self.adjMat.append(eval("["+line.replace(" ",",")+"]"))
        self.flag = [0]*len(self.adjMat);
        f.close();
        f = open(nodeNameFile, "r");
        for line in f:
            self.nodeNames.append(line);
        self.nodeNames.pop(0) #remove table header
        f.close();
    def DFS(self):
        s = [0];
        while len(s) != 0:
            v = s.pop();
            if self.flag[v] == 0:
                self.flag[v] = 1
                self.res.append(self.nodeNames[v]);
                for i in range(0, len(self.adjMat)):
                    if self.adjMat[v][i] == 1:
                        s.append(i)
    def BFS(self):
        q = deque([0]);
        self.flag[0] = 1;
        while len(q) != 0:
            v = q.popleft()
            self.res.append(self.nodeNames[v]);
            for i in range(0, len(self.adjMat)):
                if self.adjMat[v][i] == 1 and self.flag[i] != 1:
                    q.append(i)
                    self.flag[i] = 1
    def getRes(self):
        return self.res



#testing
if __name__ == "__main__":
    graph=GraphSearcher();
    graph.init("./DataAssignment_1/100/AdjacencyMatrix_of_Graph_G.txt", "./DataAssignment_1/100/Node_Information_of_Graph_G.txt");
    graph.DFS();
    graph.DFS();
    graph.BFS();