Eric Roberts Handout #51CS106B May 27, 2009Graph AlgorithmsThis handout contains additional material that will someday be in a new chapter ongraphs. It also include a new example of the important graph algorithms you need for thePathfinder assignment.Changes to the assignmentAfter implementing the Pathfinder several different ways over the long weekend, I havebecome convinced that doing it the “right” way—by taking advantage of inheritance tocreate a general graph abstraction and then allow clients to extend it throughsubclassing—cannot work as an assignment in CS106B without a lot more work. I havetherefore reverted to the more traditional approach of building the Pathfinder applicationusing structures instead of objects. Much of the handout doesn’t change beyond thediscussion of the graph.h interface on page 2. Rather than reprint the handout, here isthe relevant section:The starter project contains a file graph.h that defines the following types:1. The structure graphT, which represents the graph as a whole. Mathematically, a graphconsists of two sets: a set of nodes and a set of arcs. The two Set-valued fields in the graphTstructure follow immediately from this definition. In addition, each graph contains a Map forconverting names to nodes and the name of the image file.2. The structure nodeT, which defines the data structure for a node in the graph. In Pathfinder,each nodeT has a name and a set of arcs leading to other nodes, along with coordinateinformation and a visited flag that clients can set to indicate that the node has been visited.3. The structure arcT, which represents a connection between two nodes. Each arcT representsa connection in one direction, which makes it possible to use the graph.h interface to modeldirected graphs. If you want to use it to represent an undirected graph, you need to add an arcin each direction. In Pathfinder, each arcT has the addresses of the “from” and “to” nodes,along with the cost of traversing the arc.The contents of the revised graph.h interface appear in Figure 1 on the next page.The other important change is that you no longer have to implement this interface inthe traditional sense. Step 1 has vanished from the list of tasks, along with some of Step2. You’ve made considerable progress toward the goal just by waiting for us to makethings easier.The foreach macroA little more than a decade ago, I introduced a simplification into the CS106B curriculumthat reduced considerably the overall level of confusion and ended up, I’m convinced,saving an entire lecture day of explanation. Through all of my planning and redesignwork, I had concluded that the same simplification could not be made to work in C++,and that we’d have to suffer through the considerably less convenient approach to usingiterators. An new idea this weekend ended up giving new life to that simplification, andI’ve added it to the Set class as you have it in the starter folders.Suppose that you want to step through all of the nodes in a graph to which you have apointer in the variable gp. If you look at Figure 1, you’ll see that the graphT class has afield called nodes, which is a Set<nodeT *>. If you use iterators the way we have beenall quarter, you first have to declare an iterator, initialize it to contain an iterator over thenodes in the graph, and then use the standard iterator idiom to cycle through the nodes.– 2 –Figure 1 The graph.h interface/* * File: graph.h * ------------- * This file defines structure types for the graphT, nodeT, and arcT * types used in the Pathfinder assignment and section problems. */#ifndef _graph_h#define _graph_h#include "coord.h"#include "map.h"#include "set.h"struct nodeT; /* Forward references to these two types so */struct arcT; /* that the C++ compiler can recognize them. *//* * Type: graphT * ------------ * This type represents a graph and consists primarily of two * sets -- a set of nodes and a set of arcs -- along with a map * of names to nodes and display information. */struct graphT { Set<nodeT *> nodes; Set<arcT *> arcs; Map<nodeT *> nodeMap; string imageName;};/* * Type: nodeT * ----------- * This type represents an individual node and consists of the set * of arcs leaving this node, along with a name, a flag indicating * whether the node has been visited, and the node coordinates. */struct nodeT { Set<arcT *> arcs; string name; bool visited; coordT loc;};/* * Type: arcT * ---------- * This type represents an individual arc and consists of pointers * to the endpoints, along with the cost of traversing the arc. */struct arcT { nodeT *from; nodeT *to; double cost;};#endif– 3 –The resulting code looks like this:Set<nodeT *>::Iterator iter = gp->nodes.iterator();while (iter.hasNext()) { nodeT *np = iter.next(); . . . do something with that node . . .}While that code isn’t all that bad, most of you will end up thinking a lot about exactlywhat goes on each line and how to get the various bits of syntax right. In the process,your mind will be occupied with those details long enough to lose track of the big picture.Wouldn’t it be better if you could say something closer to what you meant in the firstplace—possibly like this:foreach (nodeT *np in gp->nodes) { . . . do something with that node . . .}It’s now almost English. The good news is that you can now write precisely that.Indeed, for any Set<type>, you can writeforeach (type var in set) { . . . do something with the element stored in var . . .}Depth-first searchThe depth-first strategy for traversing a graph is quite similar to the preorder traversal oftrees and has the same recursive structure. The only additional complication is thatgraphs—unlike trees—can contain cycles. If you don’t check to make sure that nodes arenot processed many times during the traversal, the recursive process can go on forever asthe algorithm proceeds.The algorithm to perform depth-first search on a graph, which is written using theforeach idiom, looks like this:void DepthFirstSearch(nodeT *start) { if (start->visited) return; Visit(start); foreach (arcT *ap in start->arcs) { DepthFirstSearch(ap->to); }}The depth-first strategy is most easily understood by tracing its operation in thecontext of a simple example, such as the following directed graph:n1n2n5n6n7n3n4– 4 –The open circles in the diagram indicate nodes that have not yet been visited. When