Scala in graph algorithms
While algorithmic textbooks teach us the basics of various algorithms via descriptive analysis and pseudo codes, they somehow implicitly wire that language specific aspect as well.
Let’s say we need only traverse a fragment of a full graph / we need only perform a search (depth / breadth) until so far, how do we do that in a language like scala. At least break are not encouraged in the functional style of programming.
Why not pick up a graph problem and see how well we can solve it the scala way ? Here goes the problem:
We have a grid of letters (imagine a matrix of letters) and are given a word. We need to determine whether we can form the word selecting letters from the grid. While we are allowed to start from any cell in the grid, we can only choose the adjacent cell (top, down, bottom, left) for next matching letter and are not allowed to re-use cells in grid.
| A | B | T | P |
| T | E | E | S |
| S | B | E | N |
|W | I | M | Q |
Can we find BET in the grid ? What about SWIM ?
Let’s invert the graph traversal using the following pseudo-code
(position <- all_possible_moves_from_here)
.exists(dfs(position, state))with the assumption that dfs method returns true if end state can be reached from current position and state
def dfs(position, state) : Boolean = {}We go 0–60 rather real quick, so why not delve right into the code.
Finally let us verify our algorithm by running some unit test.
val grid = Array(
Array('A','B','C','E'),
Array('S','F','C','S'),
Array('A','D','E','E')
)assertResult(true)(exist(grid, "SEE"))assertResult(false)(exist(grid, "ABCB"))
Points to note:
1. We have leveraged the exists combinator as a way to search through valid solution paths in the graph and as an alternate to being able to return a solution as we find it in java.
2. The inner method dfs relies on method arguments of exist to be able to operate
3. We’ve used Array as the only mutable collection to be able to store our graph algorithm state.
If you like this article or have any feedbacks, I’d love to hear them.
Until then ❤ coding.
