blob: fa45c290eb309fb34f59137ab0f04d01e209c050 [file] [log] [blame]
khenaidooac637102019-01-14 15:44:34 -05001package goraph
2
3// BFS does breadth-first search, and returns the list of vertices.
4// (https://en.wikipedia.org/wiki/Breadth-first_search)
5//
6// 0. BFS(G, v):
7// 1.
8// 2. let Q be a queue
9// 3. Q.push(v)
10// 4. label v as visited
11// 5.
12// 6. while Q is not empty:
13// 7.
14// 8. u = Q.dequeue()
15// 9.
16// 10. for each vertex w adjacent to u:
17// 11.
18// 12. if w is not visited yet:
19// 13. Q.push(w)
20// 14. label w as visited
21//
22func BFS(g Graph, id ID) []ID {
23 if g.GetNode(id) == nil {
24 return nil
25 }
26
27 q := []ID{id}
28 visited := make(map[ID]bool)
29 visited[id] = true
30 rs := []ID{id}
31
32 // while Q is not empty:
33 for len(q) != 0 {
34
35 u := q[0]
36 q = q[1:len(q):len(q)]
37
38 // for each vertex w adjacent to u:
39 cmap, _ := g.GetTargets(u)
40 for _, w := range cmap {
41 // if w is not visited yet:
42 if _, ok := visited[w.ID()]; !ok {
43 q = append(q, w.ID()) // Q.push(w)
44 visited[w.ID()] = true // label w as visited
45
46 rs = append(rs, w)
47 }
48 }
49 pmap, _ := g.GetSources(u)
50 for _, w := range pmap {
51 // if w is not visited yet:
52 if _, ok := visited[w.ID()]; !ok {
53 q = append(q, w.ID()) // Q.push(w)
54 visited[w.ID()] = true // label w as visited
55
56 rs = append(rs, w.ID())
57 }
58 }
59 }
60
61 return rs
62}
63
64// DFS does depth-first search, and returns the list of vertices.
65// (https://en.wikipedia.org/wiki/Depth-first_search)
66//
67// 0. DFS(G, v):
68// 1.
69// 2. let S be a stack
70// 3. S.push(v)
71// 4.
72// 5. while S is not empty:
73// 6.
74// 7. u = S.pop()
75// 8.
76// 9. if u is not visited yet:
77// 10.
78// 11. label u as visited
79// 12.
80// 13. for each vertex w adjacent to u:
81// 14.
82// 15. if w is not visited yet:
83// 16. S.push(w)
84//
85func DFS(g Graph, id ID) []ID {
86 if g.GetNode(id) == nil {
87 return nil
88 }
89
90 s := []ID{id}
91 visited := make(map[ID]bool)
92 rs := []ID{}
93
94 // while S is not empty:
95 for len(s) != 0 {
96
97 u := s[len(s)-1]
98 s = s[:len(s)-1 : len(s)-1]
99
100 // if u is not visited yet:
101 if _, ok := visited[u]; !ok {
102 // label u as visited
103 visited[u] = true
104
105 rs = append(rs, u)
106
107 // for each vertex w adjacent to u:
108 cmap, _ := g.GetTargets(u)
109 for _, w := range cmap {
110 // if w is not visited yet:
111 if _, ok := visited[w.ID()]; !ok {
112 s = append(s, w.ID()) // S.push(w)
113 }
114 }
115 pmap, _ := g.GetSources(u)
116 for _, w := range pmap {
117 // if w is not visited yet:
118 if _, ok := visited[w.ID()]; !ok {
119 s = append(s, w.ID()) // S.push(w)
120 }
121 }
122 }
123 }
124
125 return rs
126}
127
128// DFSRecursion does depth-first search recursively.
129//
130// 0. DFS(G, v):
131// 1.
132// 2. if v is visited:
133// 3. return
134// 4.
135// 5. label v as visited
136// 6.
137// 7. for each vertex u adjacent to v:
138// 8.
139// 9. if u is not visited yet:
140// 10. recursive DFS(G, u)
141//
142func DFSRecursion(g Graph, id ID) []ID {
143 if g.GetNode(id) == nil {
144 return nil
145 }
146
147 visited := make(map[ID]bool)
148 rs := []ID{}
149
150 dfsRecursion(g, id, visited, &rs)
151
152 return rs
153}
154
155func dfsRecursion(g Graph, id ID, visited map[ID]bool, rs *[]ID) {
156 // base case of recursion
157 //
158 // if v is visited:
159 if _, ok := visited[id]; ok {
160 return
161 }
162
163 // label v as visited
164 visited[id] = true
165 *rs = append(*rs, id)
166
167 // for each vertex u adjacent to v:
168 cmap, _ := g.GetTargets(id)
169 for _, u := range cmap {
170 // if u is not visited yet:
171 if _, ok := visited[u.ID()]; !ok {
172 // recursive DFS(G, u)
173 dfsRecursion(g, u.ID(), visited, rs)
174 }
175 }
176 pmap, _ := g.GetSources(id)
177 for _, u := range pmap {
178 // if u is not visited yet:
179 if _, ok := visited[u.ID()]; !ok {
180 // recursive DFS(G, u)
181 dfsRecursion(g, u.ID(), visited, rs)
182 }
183 }
184}