CSC152 2006S, Class 51: Graphs Admin: * Those of you who have studied this topic in combinatorics should not volunteer too much. * Reminder: Visitor on Friday. * EC for attending talk Thursday at 7:30 p.m. * EC for attending baseball game at 2ish tomorrow * EC for attending paper-sculpture-dance thing on May 11 * Double EC for setting Danny Zamora on fire (THIS IS A JOKE, DON'T ARREST FOR TERRORISM) (AND BUSH SUCKS) * EC for Orchestra Concert on Sunday * EC for attending art show * EC for attending Emanate concert if they ever get their act together and decide upon a time * Are there questions on the exam? Overview: * Introduction: Modeling in CS. * One Modeling ADT: The Graph. * Some Graph Problems. * A Graph ADT. * Solving the Reachability Problem. * Coding the Solution. The kind of picture we draw for lots of problems should be represented as an ADT. We call it a "Graph". * The "places" we call "vertices" (each one is a vertex) (some call them vertexes) * The connections between places we call "edges" (some folks call them edgi) * Edges can be directed (one-direction) or undirected (two-direction) * Edges may have an associated value which we call the "weight" (or cost) General version of "Get Ian A home cheap": Shortest path * Given a weighted, directed, graph, and two vertices, source and destination * Find the sequence of edges that connects source to destination * Which has the lowest total sum of edge weights Weightless version of shortest path: Reachability * Given a directed graph and two vertices, source and destiation, * Determine whether there is a path from source to destination The seven bridges of some place Kings town (Koenigsburg) * Can you cross all of the bridges and return to your starting point? * In general: Can you visit all of the vertices exactly once and return to your starting point? * Sam thinks that there is no known efficient solution to this problem. Variant of "cycle": Traveling Salescritter Problem * In a weighted, directed graph, find the smallest cycle * No known efficient solution In order to code any algorithms we develop, we must have a graph ADT. What methods belong in that ADT? (Suppose weighted and directed.) * makeEdge(Vertex source, Vertex target, int weight) * Simplifying assumption: Use integers to represent vertices * makeEdge(int source, int target, int weight) * removeEdge(int source, int target) * isEdge(int source, int target) * Iterator getSources(int vertex) * Iterator getTargets(int vertex) * int weightOf(int source, int target) * compare weight of edges int cheapestEdge(int source) How do we deal with the "creation" of vertices? * When someone refers to a vertex, create it. * Require the client to specify the vertices in advance [0..n-1] Let's write boolean reachable(WDG g, int source, int target) * For each unmarked successor that follows source * Mark the successor * If successor = target, return true * If not, recurse * If we ran through all the successors, return false * Problem: Might recursive infinitely