Implementing Graph Algorithms Using Scala

In this video, we learn about how we can traverse a graph by exploring it in a depth first manner.

• Understand what it means to traverse a graph

• See how the depth first search algorithm works

• Develop pseudo code for the recursive and non-recursive algorithm

In this video, clip we build on the concepts learned from the previous video and develop the Scala code for the depth first search algorithm.

• Learn about Scala’s sets

• Gain an understanding on the fold left function

• Define higher order functions

In this video, we describe the other manner in which graphs can be traversed. This is known as breadth first search.

• Visualize how breadth first differs from depth first search

• Find out how the breadth first search algorithm works

• Develop pseudo code for the algorithm

Here we continue on the breadth first search algorithm by developing the Scala code.

• Learn about Scala’s queues

• See the use of streams

• Consolidate your understanding of higher order functions

In this video, we explore the different practical applications of topological sorting.

• Understand the limitations of topological sorting

• Walk through a practical example

• Summarize other types of practical usages

Here we discuss one of the main methods of performing topological sorting, known as Kahn’s algorithm

• Discover some general background on the algorithm

• See the algorithm in action by solving an example.

• Understand the pseudo code for Kahn’s Algorithm

In this video, clip we perform a code walkthrough to develop Kahn’s algorithm in Scala.

• Learn about scala maps

• See usage of the groupBy function

• Find out how we can easily merge maps together

Here we find out how we can change the DFS algorithm to perform a topological sort.

• Learn some background on the algorithm

• See how the algorithm works by going through an example

• Explore the pseudo code for the Algorithm

In this video, clip we develop the code to perform the DFS topological sorting.

• Consolidate your understanding of case classes in Scala

• See how to use case classes for storing intermediate steps

• Understand immutability and the role of copy functions

In this video, we explore the different practical applications for cycle detection.

• Find out what we mean by a graph cycle

• Understand which types of graphs cannot contain cycles

• Learn about the many applications of cycle detection

In this video, clip we see how the depth first search algorithm can be modified to discover a cycle in a graph.

• Learn by example how the cycle detection algorithm works

• Find out what back edges are

• Build the pseudocode for cycle detection

Here we develop the depth first search cycle detection algorithm in Scala.

• Understand the distinction between the exists and forall functions

• See how to use Scala’s pattern matching in this implementation

• Consolidate your knowledge of case classes

Here we learn about an algorithm that can be used to determine if a buffer is a circular one or not.

• Learn about when this algorithm can be used

• Look at how the algorithm functions by an example walkthrough

• Develop the pseudo code for the Algorithm

In this video, we implement the Floyd’s algorithm in Scala.

• Revisit Scala’s streams to generate sequences.

• See how we can zip two sequences together.

• Learn about the takeWhile function when used on sequences.

In this video, we discuss the problem we are trying to solve and practical applications.

• Understand what the shortest path means on different graph types

• See an example problem where finding the shortest path would be useful

• Discover other applications for the shortest path

In this video, we explore Dijkstra’s algorithm for finding the shortest path in a weighted graph.

• Find out some general background on Dijkstra’s algorithm

• Walkthrough a real world example of the algorithm

• Build the pseudocode for the shortest path

In this clip, we implement the Dijkstra’s algorithm in Scala.

• Learn about the Try object in Scala

• Find out how we use the collect function in the implementation

• Explore the usage of the minBy function

In this video, we introduce flow networks and their applications. We also see examples where it’s useful to determine the max flow.

• Learn about flow networks and their applications

• See a real world example of max flow

• Adapt max flow to solve bipartite matching

In this video, we examine both the Ford-Fulkerson and the Edmonds-Karp algorithm for solving max flow.

• Find out some general background on the algorithms

• Walkthrough an example of the Ford-Fulkerson algorithm

• See how to change the algorithm to the faster Edmonds-Karp one

Here we build the base tools required to implement the max flow algorithm.

• Understand why we use a matrix representation for the solution

• Discover the use of multi-dimensional arrays

• Figure out how to map 1 dimensional vectors to 2

In this video, clip we implement the first part in the max flow algorithm, that of finding a path using breadth first search.

• Use various data structures to build the BFS findPath function

• Understand how to use the zipWithIndex function

• Adapt the BFS algorithm to build a spanning tree

Here we conclude the max flow algorithm by using the previously developed matrix representation.

• See how we can find the minimum along a path

• Discover how to use a foldLeft function to update the graph

• See the implementation in action by trying it out