Held: Wednesday, 28 October 2015

Back to Outline 23 - Graphs. On to Outline 25 - Implementing the Graph ADT.

Summary

We consider ways to provide (or access) graphs programatically.

Related Pages

Overview

• Designing a graph ADT.
• Different perspectives on graph ADTs.
• Building graphs.
• Accessing values.
• Implementing graphs (if time).

Administrivia

Upcoming Work

• HW (Due Monday): 5-1, 5-2, 5-6, 5-7, 5-13, 5-20, 5-23, 5-28

Extra Credit

Academic

• Any visit to the current show in the Faulconer gallery.
• Any of the Grinnell Prize Week Activities this week.
• Grinnell Town Hall Wednesday at noon: Self-Gov.
• Conversation about Study Abroad at AIT in Hungary: Wednesday at 4:15 in 3821.
• Convocation Thursday at 11: Contesting Muhammad: Contermporary Controversies in Historical Perspective
• CS Extras Thursday at 4:15pm in 3821: Algorithms for Assembling the Tree of Life. (Plus grad school at UIowa!)
• What's the Deal with the Digital Liberal Arts? Thursday at 4:15 in the D-Lab. With Autumnal snacks!
• CS Table next Tuesday: Why is everyone so mean on the Internet?
• Sexual Misconduct at Grinnell College: Results from the 2013 and 2015 Sexual Conduct Surveys. 1-3 pm, November 8, JRC 101.
• R.L. Stephens II events Thursday and Friday.

Peer Support

• Women's Soccer, Wednesday, 4 p.m. vs. UW-Platteville
• Men's Soccer, Thursday, 4 p.m. vs. Coe
• Women's Soccer, Saturday, 11 a.m. vs. Beloit (Senior day!)
• Men's Soccer, Saturday, 1:30 p.m. vs. Beloit (Senior day!)
• Halloween Day on Saturday

Designing a Graph ADT

Reminder! My goal is as much process as product. Not just what you come up with, but also how you compare different approaches.

• Philosophy
• Use cases
• Methods

Discuss with your partners the three parts. Plan to present methods.

• Think about both building graphs and accessing graphs.
• You might also consider related data types that you will need.
• Don't worry about providing implementations of common algorithms; you just want to assume that people can implement those algorithms using your ADT.

Different Perspectives on Graph ADTs

• Do we build the graph all at once and then access elements, or do we dynamically change the graph as time goes on?
• Does that affect how you design the ADT?

Building Graphs

• Add vertices (all at once? one at a time? implicitly?)
• Add edges (all at once? one at a time?)
• Remove vertices?
• Remove edges?

Extracting Info from Graphs

• edge?(a,b)
• edge(a,b)
• Iterator<Vertex> vertices();
• Iterator<Vertex> neighbors();
• Iterator<Edge> edgesFrom(v)
• Iterator<Edge> edgesTo(v)

Implementing Graphs

• Edge lists
• Adjacency lists
• Adjacency matrix