Eric Roberts Handout #50CS 106B May 22, 2009GraphsGraphsEric RobertsCS 106BMay 22, 2009Examples of GraphsExamples of Graphs Transportation GraphsSeattleSan FranciscoLos AngelesLas VegasSalt Lake CityMissoulaFargoDenverPheonixDallasKansas CityChicagoAtlantaOrlandoWashingtonNew YorkBostonThe Definition of a Graph•A graph consists of a set of nodes together with a set of arcs.The nodes correspond to the dots or circles in a graphdiagram—which might be cities, words, neurons, or whoknows what—and the arcs correspond to the links thatconnect two nodes.• In some graphs, arcs are shown with an arrow that indicatesthe direction in which two nodes are linked. Such graphs arecalled directed graphs.• Other graphs, arcs are simple connections indicating that onecan move in either direction between the two nodes. Thesegraphs are undirected graphs.• Question: Which of these two structures is more general?Graph Terminology• Mathematicians often use the words vertex and edge for thestructures that computer scientists call node and arc. We’llstick with the computer science names, but you might seetheir mathematical counterparts in algorithmic descriptions.• The nodes to which a particular node is connected are calledits neighbors.• In an undirected graph, the number of connections from anode is called its degree. In a directed graph, the number ofarcs leading outward is called the out-degree, and the numberof arcs leading inward is called the in-degree.• A series of arcs that connect two nodes is called a path. Apath that returns to its starting point is called a cycle.• A graph in which there is a path between every pair of nodesis said to be connected.– 2 –Designing a Graph Interface• To take maximum advantage of the intuition that people havewith graphs, it makes sense to design a graph package in C++so that it adheres as closely as possible to the way graphs inmathematics. In particular, the idea that a graph is a set ofnodes together with a set of arcs should be clear from thedefinition.• Both nodes and arcs have some properties that are closely tiedto the graph in which they belong. Each node, for example,must keep track of the arcs that lead to its neighbors. In muchthe same way, each arc needs to know what nodes it connects.• At the same time, both nodes and arcs are likely to containother information that depends on the application, such as thename of a node or the cost of traversing an arc.• Question: In C++, how could you allow clients to extend thebasic definitions of nodes and arcs./* * File: graph.h * ------------- * This interface exports three classes: * * 1. The class Graph, which represents the graph as a whole. As in * mathematics, a graph consists a set of nodes and a set of arcs. * * 2. The class Node, which defines the basic functionality of a node. * Clients that use this class will typically extend it to create * a Node subclass that contains additional information, such as the * name of the node or other similar information. * * 3. The class Arc, which defines the basic functionality of an arc. * Clients that use this class will typically extend it to create * an Arc subclass that contains additional information, such as the * cost of traversing an arc. */#ifndef _graph_h#define _graph_h#include "set.h"Designing the graph.h Interface/* * Class: Graph * ------------ * This class defines the basic structure for a graph. */class Node;class Arc;class Graph {public: Graph(); ~Graph(); void add(Node *np); Set<Node *> getNodeSet(); Set<Arc *> getArcSet(); Set<Node *>::Iterator getNodeIterator(); Set<Arc *>::Iterator getArcIterator();private:#include "graphpriv.h"}Designing the graph.h Interface/* * Class: Graph * ------------ * This class defines the basic structure for a graph. */class Node;class Arc;class Graph {public: Graph(); ~Graph(); void add(Node *np); Set<Node *> getNodeSet(); Set<Arc *> getArcSet(); Set<Node *>::Iterator getNodeIterator(); Set<Arc *>::Iterator getArcIterator();private:#include "graphpriv.h"}Designing the graph.h Interface/* * Class: Node * ----------- * This class defines the base class for a node in the graph. * Most clients will define a subclass that contains more information. */class Node {public: Node(); virtual ~Node(); void addArc(Arc *ap); Set<Arc *> getArcSet(); Set<Arc *>::Iterator getArcIterator(); virtual int compareTo(Node & otherNode);private:#include "nodepriv.h"}Designing the graph.h Interface/* * Class: Arc * ---------- * This class defines the base class for an arc in the graph. Each arc * is a connection from a start node to an end node. If you want to * represent an undirected graph, you need to create arcs in each direction. * Most clients will define a subclass that contains more information. */class Arc {public: Arc(Node *start, Node *end); virtual ~Arc(); Node *getStartNode(); Node *getEndNode(); virtual int compareTo(Arc & otherArc);private:#include "arcpriv.h"}Designing the graph.h
View Full Document
Unlocking...