1
Student Name: __________________
Class and Section __________________
Total Points (10 pts) __________________
Due: Wednesday 14, 2012 before the class
Project: Graph Visualization
CSCI 2410 Data Structures and Algorithms
Armstrong Atlantic State University
Problem Description:
Modify Listing 30.7, DisplayUSMap to add Savannah in the graph with weighted
edges to Atlanta, New York, and Miami. Display all the weights on the edges.
Download Graph.java, AbstractGraph.java, and
WeightedGraph.java, ViewGraph.java, and
Displayable.java from the book’s Website.
Modify ViewGraph.java to display weights on the edges.
You need write a program named Exercise31_01.java
What to submit?
1. Email me screen shots.
2. Compile and Submit to LiveLab (you must submit the program regardless whether it
complete or incomplete, correct or incorrect)
2
3. Fill in self-evaluation:
1. Can your program display weights on edges? _______________
Graph.java
AbstractGraph.java
UnweightedGraph.java
/** Return the degree for a specified vertex */
public int getDegree(int v);
/** Print the edges */
public void printEdges();
/** Clear graph */
public void clear();
/** Add a vertex to the graph */
public void addVertex(V vertex);
protected List<V> vertices = new ArrayList<V>(); // Store vertices
protected List<List<Integer>> neighbors
= new ArrayList<List<Integer>>(); // Adjacency lists
/** Construct a graph for integer vertices 0, 1, 2 and edge list */
protected AbstractGraph(List<Edge> edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
vertices.add((V)(new Integer(i))); // vertices is {0, 1, …}
createAdjacencyLists(edges, numberOfVertices);
}
/** Construct a graph from integer vertices 0, 1, and edge array */
protected AbstractGraph(int[][] edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
vertices.add((V)(new Integer(i))); // vertices is {0, 1, …}
createAdjacencyLists(edges, numberOfVertices);
}
for (int i = 0; i < numberOfVertices; i++) {
neighbors.add(new ArrayList<Integer>());
}
for (Edge edge: edges) {
neighbors.get(edge.u).add(edge.v);
}
}
}
@Override /** Return the neighbors of the specified vertex */
public List<Integer> getNeighbors(int index) {
return neighbors.get(index);
}
@Override /** Return the degree for a specified vertex */
public int getDegree(int v) {
return neighbors.get(v).size();
}
5
vertices.add(vertex);
neighbors.add(new ArrayList<Integer>());
}
public Tree dfs(int v) {
List<Integer> searchOrder = new ArrayList<Integer>();
int[] parent = new int[vertices.size()];
for (int i = 0; i < parent.length; i++)
parent[i] = –1; // Initialize parent[i] to -1
// Mark visited vertices
boolean[] isVisited = new boolean[vertices.size()];
// Recursively search
dfs(v, parent, searchOrder, isVisited);
6
int[] parent = new int[vertices.size()];
for (int i = 0; i < parent.length; i++)
parent[i] = –1; // Initialize parent[i] to -1
return new Tree(v, parent, searchOrder);
}
/** Construct a tree with root, parent, and searchOrder */
public Tree(int root, int[] parent, List<Integer> searchOrder) {
this.root = root;
this.parent = parent;
this.searchOrder = searchOrder;
}
7
/** Return the path of vertices from a vertex to the root */
public List<V> getPath(int index) {
ArrayList<V> path = new ArrayList<V>();
}
/** Print a path from the root to vertex v */
public void printPath(int index) {
List<V> path = getPath(index);
}
}
import java.util.*;
public class UnweightedGraph<V> extends AbstractGraph<V> {
/** Construct an empty graph */
public UnweightedGraph() {
}
8
super(edges, numberOfVertices);
}
/** Construct a graph from integer vertices 0, 1, and edge array */
public UnweightedGraph(int[][] edges, int numberOfVertices) {
super(edges, numberOfVertices);
}
}
public class GraphView extends javax.swing.JPanel {
private Graph<? extends Displayable> graph;
public GraphView(Graph<? extends Displayable> graph) {
this.graph = graph;
g.drawLine(x1, y1, x2, y2); // Draw an edge for (i, v)
}
}
}
}
9
new City(“San Francisco”, 50, 210),
new City(“Los Angeles”, 75, 275), new City(“Denver”, 275, 175),
// Edge array for graph in Figure 27.1
private int[][] edges = {
{0, 1}, {0, 3}, {0, 5}, {1, 0}, {1, 2}, {1, 3},
private Graph<City> graph
= new UnweightedGraph<City>(edges, vertices);
public DisplayUSMap() {
add(new GraphView(graph));
}
}
public static void main(String[] args) {
JFrame frame = new JFrame(“DisplayUSMap”);
DisplayUSMap applet = new DisplayUSMap();
frame.add(applet);
applet.init();
10
applet.start();