Kotlin

Java

#### Graph Algorithms :

`60`#### Graphs :

`59`#### map-reduce-filter :

`58`#### Generics :

`57`#### Implementing a Map :

`56`#### Hashing :

`55`#### Binary Search :

`54`#### Quicksort :

`53`#### Merge Sort :

`52`#### Sorting Algorithms :

`51`#### Practice with Recursion :

`50`#### Trees and Recursion :

`49`#### Trees :

`48`#### Recursion :

`47`#### Lists Review and Performance :

`46`#### Linked Lists :

`45`#### Algorithms and Lists :

`44`#### Lambda Expressions :

`43`#### Anonymous Classes :

`42`#### Practice with Interfaces :

`41`#### Implementing Interfaces :

`40`#### Using Interfaces :

`39`#### Working with Exceptions :

`38`#### Throwing Exceptions :

`37`#### Catching Exceptions :

`36`#### References and Polymorphism :

`35`#### References :

`34`#### Data Modeling 2 :

`33`#### Equality and Object Copying :

`32`#### Polymorphism :

`31`#### Inheritance :

`30`#### Data Modeling 1 :

`29`#### Companion Objects :

`28`#### Encapsulation :

`27`#### Constructors :

`26`#### Objects, Continued :

`25`#### Introduction to Objects :

`24`#### Compilation and Immutability :

`23`#### Practice with Collections :

`22`#### Maps and Sets :

`21`#### Lists and Type Parameters :

`20`#### Imports and Libraries :

`19`#### Multidimensional Arrays :

`18`#### Practice with Strings :

`17`#### null :

`16`#### Algorithms and Strings :

`15`#### Strings :

`14`#### Functions and Algorithms :

`13`#### Practice with Functions :

`12`#### More About Functions :

`11`#### Errors and Debugging :

`10`#### Functions :

`9`#### Practice with Loops and Algorithms :

`8`#### Algorithms I :

`7`#### Loops :

`6`#### Arrays :

`5`#### Compound Conditionals :

`4`#### Conditional Expressions and Statements :

`3`#### Operations on Variables :

`2`#### Variables and Types :

`1`#### Hello, world! :

`0`

import cs1.graphs.UnweightedGraph

import cs1.graphs.GraphNode

import java.util.Arrays

val graph = UnweightedGraph.circleUndirectedGraph(listOf(1, 2, 4))

for (node in graph.nodes) {

println(node)

}

This lesson introduces a new data structure: *graphs*.
Graphs are extremely useful, both for modeling certain types of data, and for enabling certain algorithms.
In fact, trees, which we’ve been studying previously, are themselves a type of graph.
Graphs are also great for practice with recursion.
So let’s get started!

What is a Graph?

Wikipedia defines a graph as:

A graph data structure consists of a finite (and possibly mutable) set of vertices (also called nodes or points), together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges (also called links or lines), and for a directed graph are also known as edges but also sometimes arrows or arcs. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.

Let’s look at some diagrams that will help visualize this new data structure, and introduce some important terminology.

What Are Graphs For?

Graphs can be used to model a variety of real-world entities, which is part of what makes them so useful to computer scientists. Some examples include:

*Social graphs*, where each node is a person, edges represent friendships or acquaintances, and understanding the graph helps better understand the structure of human relationships.*Internet routing*, where each node is a machine connected to the internet, edges represent connections between machines, and understanding the graph helps data travel around the world.*Transit graphs*, where each node is a place on Earth, edges represent transit connections between different locations, and understanding the graph help*you*travel around the world.

Let’s look at these example a bit more:

Types of Graph

Depending on the properties of their edges, graphs can be directed or undirected, weighted or unweighted.
We’ll focus our attention on *undirected* *unweighted* graphs.
But let’s discuss the differences briefly.

Trees v. Graphs

We’ve discussed trees previously, and it turns out that trees are one specific type of graph. Now that we have been introduced to graphs, we can define a tree more precisely.

Graph Recursion

Previous we introduced recursion, a problem solving technique that works by breaking down large problems into smaller pieces, solving them, and then combining the results. Graphs are another data structure that we frequently will examine recursively. Let’s see why:

In addition, like trees, compared to lists and arrays and `String`

s, graphs can be hard to work with using iterative solutions!
Recursion is a much better approach…

Recursive Graph Size

To help you prepare for our next homework problem, let’s discuss the recursive approach to counting the number of nodes in a graph.
Specifically, we’ll review the idea of graph *traversal*, and how not to get stuck along the way.

Created By: Geoffrey Challen

/ Version: `2021.10.0`

Create a method name `size`

that receives a reference to an unweighted graph containing `Int`

values using `cs1.graphs.UnweightedGraph`

, so a `UnweightedGraph<Int>`

,
and returns the size of the graph as an `Int`

.

To complete this problem you'll need to implement graph traversal.
From a given node, you want to visit all of its neighbors *except* any nodes that you've already visited.
If you use a `Set`

to track the nodes that you've visited, then you can simply return the size of that `Set`

when
you are finished.
We've provided some starter code to get you off on the right track.

For reference, `cs1.graphs.UnweightedGraph`

is declared somewhat like this:

And `cs1.graphs.GraphNode`

is declared somewhat like this:

import cs1.graphs.GraphNode

import cs1.graphs.UnweightedGraph

fun size(graph: UnweightedGraph<Int>): Int {

val nodes = mutableSetOf<GraphNode<Int>>()

traverse(graph.node, nodes)

return 0

}

private fun traverse(

node: GraphNode<Int>,

nodes: MutableSet<GraphNode<Int>>,

) {

// Add this node to the set

// Iterate through all the neighbors

// If the neighbor hasn't been visited, call traverse on it and pass it the visited set

}

Created By: Geoffrey Challen

/ Version: `2021.10.0`

Create a class `Connections`

with a single primary constructor that accepts a `String`

.
The `String`

contains, in CSV format, a list of cities and other cities that they are connected to.
So, for example, the input:

```
Champaign,Chicago,St. Louis
Chicago,Detroit,Milwaukee
St. Louis,Champaign,Cincinnati
```

Means that Champaign is connected to Chicago and St. Louis, and that Chicago is connected to Detroit and
Milwaukee, and so on.
Essentially the CSV serializes a directed graph, where the first item on each line is a node and the other items
represent other nodes that it is connected to.
This is one way of serializing a directed, unweighted graph.
Make sure to `trim`

all the `String`

s that you extract from the CSV.

Your class should parse this `String`

and provide a single instance method `isConnected`

.
`isConnected`

accepts two `String`

s and returns `true`

if the first city is connected to the second based on the
graph passed to the constructor.
So, given the input above, `isConnected("Champaign", "Chicago")`

would return `true`

, but
`isConnected("Chicago", "Champaign")`

would return `false`

.
(Note that the graph is not necessarily symmetric.)
If you don't have connection information for the source, you should throw an `IllegalArgumentException`

.

Note that only the cities that appear first on each line in the CSV should be treated as cities you have
connection information for.
So, for example, even though "Detroit" appears as a destination from "Chicago" in the data set above, we do not
have a line starting with "Detroit", and therefore a call to `isConnected`

with "Detroit" as the first parameter
should throw an `IllegalArgumentException`

.

Our suggestion is to use a private field to store a data structure that you populate in your constructor.
This will keep your `isConnected`

method simpler.
Good luck, and have fun!

Need more practice? Head over to the practice page.