class Graph():
    def __init__(self):
        import queue
        self.d = {}
    def addNode(self, node):
        if node not in self.d:
            self.d[node] = []
    def __repr__(self):
        return(str(self.d))
    def addEdge(self, source, target):
        if self.d[source] != []:
            if target not in self.d[source]:
                self.d[source].append(target)
            else:
                print("takie polaczenie juz istnieje", (source, target))
        else:
            self.d[source] = [target]
        if source not in self.d[target]:
            self.addEdge(target, source)
    def visit(self,node):
        print("odwiedzamy teraz wezel: ", node)
    def w_glab(self, start):
        try:
            self.visited.append(start)
        except:
            self.visited = [start]
        for node in self.d[start]:
            if node not in self.visited:
                self.w_glab(node)
        #self.visit(start)
        return self.visited



    def wszerz(self, start):
        self.q = queue.Queue()
        self.visited2 = {}
        self.q.put(start)
        self.visited2[start] = True
        while not self.q.empty():
            start = self.q.get()
            #self.visit(start)
            for node in self.d[start]:
                if node in self.visited2.keys():
                    if self.visited2[node] != True:
                        self.q.put(node)
                        self.visited2[node] = True
                else:
                    self.q.put(node)
                    self.visited2[node] = True
        self.v = self.visited2.keys()
        return(list(self.v))


    def najkrotszy(self, start, koniec):
        self.wszerz(start)
        self.visited3 = {}
        self.p = {}
        self.qu = queue.Queue()
        self.p[start] = start
        self.qu.put(start)
        self.visited3[start] = True
        while not self.qu.empty():
            start = self.qu.get()
            if start == koniec:
                while self.p[start] != start:
                    print(start)
                    start = self.p[start]
                self.qu = None
                return True
            for node in self.d[start]:
                if node in self.visited3.keys():
                    if self.visited3[node] != True:
                        self.p[node] = self.p[start]
                        self.qu.put(node)
                        self.visited3[node] = True
                else:
                    self.p[node] = start
                    self.qu.put(node)
                    self.visited3[node] = True
        print("sciezka nie istnieje")
        return True


import queue
g = Graph()
for element in "ABCDEFGHIJ":
    g.addNode(element)
g.addEdge("A","B")
g.addEdge("A","D")
g.addEdge("A","C")
g.addEdge("C","F")
g.addEdge("D","F")
g.addEdge("F","G")
g.addEdge("B","G")
g.addEdge("G","H")
print("Twoj graf to: ", g)
pocz = input("Podaj wierzcholek przeszukiwania wglab: ")
print(g.w_glab(pocz))
szerz = input("Podaj wierzcholek przeszukiwania wszerz: ")
print(g.wszerz(szerz))
a = input("Podaj wierzcholek poczatkowy: ")
b = input("Podaj wierzcholek koncowy: ")
print("Najkrotsza sciezka pomiedzy: ", a, " oraz ", b)
g.najkrotszy(a, b)