GRAPHS AND APPLICATIONS - Introduction to Java Programming: Comprehensive Version - page 1034

19 public UnweightedGraph(List<Edge> edges, int numberOfVertices) { constructor

20 super (edges, numberOfVertices);

21 }
22
23 /** Construct a graph from integer vertices 0, 1, and edge array */

24 public UnweightedGraph( int [][] edges, int numberOfVertices) {

constructor

25 super (edges, numberOfVertices);

26 }
27 }

The code in the Graph interface in Listing 28.2 and the UnweightedGraph class in
Listing 28.4 are straightforward. Let us digest the code in the AbstractGraph class in
Listing 28.3.
The AbstractGraph class defines the data field vertices (line 4) to store vertices and
neighbors (line 5) to store edges in adjacency lists. neighbors.get(i) stores all edges adja-
cent to vertex i . Four overloaded constructors are defined in lines 9-42 to create a default graph,
or a graph from arrays or lists of edges and vertices. The createAdjacencyLists(int[][]
edges, int numberOfVertices) method creates adjacency lists from edges in an array (lines
45-50). The createAdjacencyLists(List<Edge> edges, int numberOfVertices)
method creates adjacency lists from edges in a list (lines 53-58).
The getNeighbors(u) method (lines 81-87) returns a list of vertices adjacent to vertex
u . The clear() method (lines 106-110) removes all vertices and edges from the graph. The
addVertex(u) method (lines 112-122) adds a new vertex to vertices and returns true. It
returns false if the vertex is already in the graph (line 120).
The addEdge(e) method (lines 124-139) adds a new edge the adjacency edge list and
returns true. It returns false if the edge is already in the graph. This method may throw
IllegalArgumentExcepiton if the edge is invalid (lines 126-130).
The printEdges() method (lines 95-104) displays all vertices and edges adjacent to
each vertex.
The code in lines 164-293 gives the methods for finding a depth-first search tree and a
breadth-first search tree, which will be introduced in Sections 28.7 and 28.9, respectively.

28.7 Describe the relationships among Graph , AbstractGraph , and UnweightedGraph .
28.8

✓ ✓

Check

Point

For the code in Listing 28.1, TestGraph.java, what is graph1.getIndex("Seattle") ?
What is graph1.getDegree(5) ? What is graph1.getVertex(4) ?

28.5 Graph Visualization
To display a graph visually, each vertex must be assigned a location.

Key
Point

The preceding section introduced how to model a graph using the Graph interface,
AbstractGraph class, and UnweightedGraph class. This section discusses how to display
graphs graphically. In order to display a graph, you need to know where each vertex is dis-
played and the name of each vertex. To ensure a graph can be displayed, we define an inter-
face named Displayable that has the methods for obtaining the x- and y- coordinates and
their names, and make vertices instances of Displayable , in Listing 28.5.

L ISTING 28.5

Displayable.java
1 public interface Displayable {
2

Displayable interface

public int getX(); // Get x-coordinate of the vertex

3 public int getY(); // Get y-coordinate of the vertex

4 public String getName(); // Get display name of the vertex

5 }

A graph with Displayable vertices can now be displayed on a pane named GraphView ,
as shown in Listing 28.6.