GraphSearchVisualizer/bidirectional.py at main · hasathcharu/GraphSearchVisualizer · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import queue
from graph import G
from backtrack import backtrack_path


def bidirectional(graph, start_node, end_node):
    visited = set()
    sq = queue.Queue()
    eq = queue.Queue()
    sq.put(start_node)
    eq.put(end_node)
    sorder = []
    eorder = []
    while not (sq.empty() and eq.empty()):
        svertex = ""
        evertex = ""
        if not sq.empty() and not eq.empty():
            svertex = sq.get()
            evertex = eq.get()
        elif sq.empty():
            evertex = eq.get()
        elif eq.empty():
            svertex = sq.get()

        if svertex in eorder:
            ueorder = eorder[: eorder.index(svertex) + 1]
            order = sorder.copy()
            order.extend(ueorder[::-1])
            break
        if evertex in sorder:
            usorder = sorder[: sorder.index(evertex) + 1]
            order = usorder.copy()
            order.extend(eorder[::-1])
            break
        if svertex and svertex not in visited:
            visited.add(svertex)
            sorder.append(svertex)

            for node in graph[svertex]:
                if node not in visited:
                    sq.put(node)

        if evertex and evertex not in visited:
            visited.add(evertex)
            eorder.append(evertex)
            for node in graph[evertex]:
                if node not in visited:
                    eq.put(node)

    return sorder, eorder, order, backtrack_path(start_node, end_node, order, graph)


# print(bidirectional(G, 'Haritha', 'Rashmi'))