Graph-Visualizer/dfs.js at master · Abdullah-Rady/Graph-Visualizer · 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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
let visiteddfs;
let layersDFS;


function inistalizationDFS(){
    visiteddfs = []
    layersDFS = []

    for (let i = 0; i < nrows; i++) {
        visiteddfs.push(Array(ncols).fill(false))
        layersDFS.push(Array(ncols).fill(0))
    }
}


function dfs(startx, starty) {

    highestTimeoutId = -1;
    inistalizationDFS()

    visiteddfs[starty][startx] = true

    const stack  = []

    stack.push([startx, starty])

    let step = 1
    let maxTime = -1

    while (stack.length > 0) {

        const s = stack.pop()

        let nx = s[0]
        let ny = s[1]

        visiteddfs[ny][nx] = true

        if (graphRefrence[ny].children[nx].classList.contains('endDiv')){
            tracePathDFS(maxTime)
            return
        }


        highestTimeoutId = setTimeout(() => {
            graphRefrence[ny].children[nx].classList.add('node-search')
            step++

        }, 10 * step);

        maxTime = Math.max(maxTime, 10 * step)

        for (let i = 0; i < 4; i++) {

            if (inBounds(nx + dx[directions[i]], ny + dy[directions[i]]) && !visiteddfs[ny + dy[directions[i]]][nx + dx[directions[i]]] && !graphRefrence[ny + dy[directions[i]]].children[nx + dx[directions[i]]].classList.contains('node-wall')){

                stack.push([nx + dx[directions[i]], ny + dy[directions[i]]])

            }

        }
        step++

    }


}


function tracePathDFS(maxTime){

    inistalizationDFS()


    visiteddfs[starty][startx] = true

    const stack  = []

    stack.push([startx, starty])

    let step = 1

    while (stack.length > 0) {

        const s = stack.pop()

        let nx = s[0]
        let ny = s[1]

        visiteddfs[ny][nx] = true

        if (graphRefrence[ny].children[nx].classList.contains('endDiv')){
            return
        }


        setTimeout(() => {
            graphRefrence[ny].children[nx].classList.add('node-path')
        }, 10 * step + maxTime);


        for (let i = 0; i < 4; i++) {

            if (inBounds(nx + dx[directions[i]], ny + dy[directions[i]]) && !visiteddfs[ny + dy[directions[i]]][nx + dx[directions[i]]] && !graphRefrence[ny + dy[directions[i]]].children[nx + dx[directions[i]]].classList.contains('node-wall')){

                stack.push([nx + dx[directions[i]], ny + dy[directions[i]]])

            }

        }
        step++

    }

}