**You are being recorded and transcribed.**

*Approximate overview*

- Administrivia
- Questions
- Modeling problems with graphs
- Some graph terminology
- Designing a graph ADT
- Implementing that ADT (if time)

- Friday, 2024-05-03, 11:00pm, MP10 post-reflection.
- Friday, 2024-05-03, 11:00pm, New set of LAs, repeated + old LAs
- Sunday, 2024-05-05, 11:00pm, Readings
- Friday, 2024-05-10, 11:00pm, New set of LAs, repeated + old LAs

- Tuesday, 2024-05-07, noon, Some PDR.
*CS Table: CS Humor*. - Tuesday, 2024-05-07, 8:00pm, Science 3819.
*Mentor Session*. Make Elene and Sam happy. Show up to mentor sessions!

Cultural

- Most days, 2024-04-xx and 2024-05-xx, 11am-6pm,
Grinnell College Museum of Art.
*BAX 2024*. Shouldn’t it be BAE? - Friday, 2024-05-03, 4:00–5:00pm, HSSC N1170.
*Middle of Everywhere*(Lebanon)

Peer

Wellness

- Sunday, 2024-05-05, 3:00pm–5:00pm, Somewhere.
*Bubble Soccer*. - Friday, 2024-05-10, 5:00pm–??:??pm, Merrill Park West.
*CS Picnic!*Survey forthcoming.

Misc

- Saturday, 2024-05-04 (aka “Star Wars Day”), 12:30pm–8:00pm, Central Campus.
*The Grinnellian.*

- Friday, 2024-05-03, 3:00–5:00pm, Softball Complex.
*Softball vs. Lawrence*. - Friday, 2024-05-03, 5:00–7:00pm, Softball Complex.
*Softball vs. Lawrence*. - Saturday, 2024-05-04, 2200–4:00pm, Softball Complex.
*Softball vs. Illinois*. (Because three games against the same team in one weekend is absurd.)

- Saturday, 2024-05-04 (aka “Star Wars Day”), noon–5:00pm, Cleveland Beach.
*Alice in Wonderland*.

- Please be moderate in all you do, even LAs.
- Consent is essential.

When are we getting those back?

I don’t know.

How many redos?

At least one, due at 5pm on the 17th.

What is my other question?

Will I pass?

Will I pass?

Probably. Almost certainly.

Could you put up a third MP1? It appears that I destroyed my code when fixing it.

Teams message me to remind me because I will forget otherwise.

Reminder me if I haven’t done so in twelve hours or if I get the MP number wrong.

Can you lower the number of LAs we need for an A?

Ask me again next Friday.

How many LAs are there?

Um … 48.

Some gaslight question about arguing for a grade.

You can argue about your MP grades.

Have you seen bandersnatch?

No.

Can you move the LA due date to Saturday night?

Sure. I would not recommend doing LAs after Alice. Although maybe it would amuse me.

And I suppose Alice is okay straight.

Do I need any code for the “IDE” LA?

No. Just explain what an IDE is and suggest how you have taken advantage of the IDE features of VSCode.

Didn’t we do a quiz in class for the recursive running time LA?

Yes. But they ended up with my 151 quizzes and then got shredded.

That’s okay, you can do it again.

What should use a source for the composition LA?

Composition is the concept that one object (class) can be built from other objects (classes). Put that in your own words and then give me an example that shows you’ve done it.

Where should we be using PUM or PM or P?

Any time you have to design or describe an ADT: Stacks, Queues, Lists, Priority Queues, Dictionaries, (Heaps), Graphs. Also the “Design an ADT”. Maybe Iterators.

What chances will we have to complete LAs?

Due on May 3; returned May 6.

Due on May 10; returned on May 13.

Due on May 17 at 5pm.

Maybe due on May 14, returned on May 16.

You changed the heaps one. Could I just implement heaps?

Sure.

- A core issue of CS (or at least computer programming): Take real-world problems and solve them computationally.
- We like to build “models” that let us represent the problem in the computer, often stripping away extraneous details.
- A lot of problems, particularly geographic problems, lead to structures we call “graphs”.

- You are a 911 dispatcher and need to send an ambulance to an address, from which ambulance depot do you send it?
- It has snowed. A lot. All of the streets are impassible. What’s the minimal set of streets we should clear so that the fire department can reach every corner in town?
- You work for the census. You need to visit every house in
Powesheik county. What’s the most efficient path to visit all
of those houses?
*Can*you visit all of those houses?

- What do these problems have in common?
- A bunch of “locations”
- Some locations are connected to each other.
- We sometimes assign a number to a connection:
- Cost to remove a log
- Time to get from to another
- Capacity

A *graph* is a collection of *vertices* and *edges* that connect them.
CLRS write this as $(V,E)$. $E$ is a subset of $V$x$V$.

- We typically say that a graph has $n$ vertices and $m$ edges.
- We might say that a graph has $v$ vertices and $e$ edges.

- We typically permit only one edge from one vertex to another.
- We don’t typically permit edges from a vertex to itself.

*Please do not use “vertice” as the singular of “vertices”.*

We often label the vertices of the graph.

- A, B, C, D, E
- v1 v2 v3

In a *weighted graph* every edge has an associated numeric “weight”,
representing some cost associated with the edge.

- For our geographic examples, that might be the distance between two locations or the time it takes to get between the two locations.
- We may sometimes associate more than one value with an edge, such as both a cost and a cpacity.
- In most situations, we require that weights be non-negative.
- Weights can be integers or reals. Surprisingly, using (conceptual) reals can make some problems more difficult.

In a *directed graph*, edges have a direction. That is, just because
we can get directly from A to B, we can’t necessarily get from B to A.

- You can think of these as one-way streets.

- TLA: Three-letter acronym
- ADT: Abstract data type
- TPS: Think, Pair, Share
- PUM: Philosophy, Use Cases, Methods (I’d appreciate a better TLA)
- LIA: Layout, Implementation, Analysis (I’d appreciate a better TLA)
- CAM: Constructors, Accessors, Mutators

*TPS: PUM* (yay TLAs)

Something with vertices and weighted, directed edges.

See above

`Graph()`

- Create a new, empty graph.

`int numEdges()`

`int numVertices()`

`boolean isEmpty()`

`Iterable<Vertex> vertices()`

`Iterable<Edge> edges()`

`Iterable<Edge> edgesFrom(Vertex v)`

`Iterable<Edge> edgesTo(Vertex v)`

`boolean containsVertex(Vertex v)`

`boolean containsEdge(Vertex source, Vertex target)`

`int edgeWeight(Vertex source, Vertex target)`

- Throws an exception if there is no such edge

`void addVertex(Vertex v)`

(vs`Vertex addVertex()`

)`void removeVertex(Vertex v)`

- Also removes all the edges

`void addEdge(Vertex source, Vertex target, int weight);`

- If we have not previously added
`source`

(or`target`

), this could throw an exception.*our choice* - Alternately, we could automatically add
`source`

and`target`

- If we already have an edge between
`source`

and`target`

, this will change the weight of that edge.

- If we have not previously added
`void removeEdge(Vertex source, Vertex target)`

It will be difficult to develop an implementation that makes all of these efficient. So we may want multiple implementations.

We could think about this in other ways, such as by having our vertices contain a list of outgoing (or incoming or just adjacent) edges.

*TPS: LIA* (yay TLAs)

Layout: See above and below

```
public class Graph {
Dictionary<VertexName,Vertex> vertices;
} // Graph
public class Vertex {
VertexName name;
List<Edge> outgoingEdges;
} // class Vertex
public class Edge {
VertexName source;
VertexName target;
int weight;
} // class Edge
```

Implementation + Analysis

`addEdge(VerteName source, VertexName target, int weight);`

- Create a new instance of edge. O(1)
- Look up the source in the hash table. O(1)
- Find the matching edge O(n)
- If there’s a matching edge, replace the weight/edge O(1)
- Otherwise, Add it to the list. O(1)

- addVertex
- edgeWeight

- Each vertex contains a hash table of edges (rather than a list)

Make a list of all the edges in the graph

Create an nxn matrix of weights.