Implementing Graph Algorithms Using Scala

In this video, clip we discuss what the principles of what makes programming functional are. We see how these principles can be applied to represent graphs.

• Find out about the three main functional principles

• Understand the benefits of functional programming

• Adopt certain data structures to enable us to follow these principles

Here we implement the different types of graphs in Scala in a functional manner.

• Use functional friendly data structures to model graphs

• Discover how to use Scala’s vectors and map

• Follow code walkthrough for weighted and Directed graphs

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