Traverser
Traverser copied to clipboard
intuit
Create post order examples in Scala
DFS/BFS pre/post order examples in Scala
1. Issue Link:
2. Brief explanation of a change:
3. Will it break existing clients and code in production?
@vibhu172000 Thank you for the contribution. How would you use traverser library (which this repo is about) to perform same task in scala?
DFS-
Graph
9 7
0 1
1 2
1 3
2 3
3 4
6 7
6 8
Result
Component 1 0 1 2 3 4
Component 2 5
Component 3 6 7 8
There are 3 connected components
The important things worth mentioning here is the use of forEachwith it
variable and ranges from Kotlin helped me quite a lot. Use of Pair and
variable like tv.first is also helpful.
enum class Color { BLACK, WHITE } var vert: MutableList<Color> = mutableListOf() var adj: MutableList<MutableList<Pair<Int, Int>>> = mutableListOf()
vert is a list of Color enum which is used track the visit status of each
node. WHITE denotes if it’s unvisited while BLACK means it’s visited. adj
maintains are graph in the form of adjacency list which list of list of Pairs. Pair contains two numbers of which first denotes the node and
second denotes the weight associated with that edge which is in this case
is 1.
the core DFS is very small
fun dfs(u: Int) {
vert[u] = Color.BLACK
print(" $u")
(0..adj[u].size-1).forEach {
val tv = adj[u][it]
if(vert[tv.first] == Color.WHITE) dfs(tv.first)
}
}
BFS Graph 9 7 0 1 1 2 1 3 2 3 3 4 6 7 6 8 Result u: 0 and [Node(color=BLACK, distance=0, parent=-1), Node(color=BLACK, distance=1, parent=1), Node(color=BLACK, distance=2, parent=2), Node(color=BLACK, distance=2, parent=3), Node(color=BLACK, distance=3, parent=4)] u: 6 and [Node(color=BLACK, distance=0, parent=-1), Node(color=BLACK, distance=1, parent=7), Node(color=BLACK, distance=1, parent=8)] u: 5 and [Node(color=BLACK, distance=0, parent=-1)]
use the following variables and enum class.
enum class Color {
BLACK, WHITE
}
var adj: MutableList<MutableList<Pair<Int, Int>>> = mutableListOf()
We make use of a data class Node to keep track of color for visiting,
distance and parent of the node while doing BFS.
On Mon, Oct 19, 2020, 08:24 Alex Matiushkin <[email protected] wrote:
@vibhu172000 https://github.com/vibhu172000 Thank you for the contribution. How would you use traverser library (which this repo is about) to perform same task in scala?
— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/intuit/Traverser/pull/20#issuecomment-711481536, or unsubscribe https://github.com/notifications/unsubscribe-auth/APYLMOXEPECN5V24HREJFHLSLOS4TANCNFSM4SUAPXRQ .
@vibhu172000 thanks for sharing. I wonder how the mechanism you've described would improve traverser component?