Java Reference
In-Depth Information
implement all the methods defined in the Graph interface. For convenience, we assume the
graph is a simple graph, i.e., a vertex has no edge to itself and there are no parallel edges from
vertex u to v .
AbstractGraph implements all the methods from Graph , and it does not introduce any
new methods except a convenient addEdge(edge) method that adds an Edge object to the
adjacency edge list. UnweightedGraph simply extends AbstractGraph with five construc-
tors for creating the concrete Graph instances.
Note
You can create a graph with any type of vertices. Each vertex is associated with an index,
which is the same as the index of the vertex in the vertices list. If you create a graph
without specifying the vertices, the vertices are the same as their indices.
vertices and their indices
Note
The AbstractGraph class implements all the methods in the Graph interface. So
why is it defined as abstract? In the future, you may need to add new methods to
the Graph interface that cannot be implemented in AbstractGraph . To make the
classes easy to maintain, it is desirable to define the AbstractGraph class as abstract.
why AbstractGraph ?
Assume all these interfaces and classes are available. Listing 28.1 gives a test program that
creates the graph in Figure 28.1 and another graph for the one in Figure 28.3a.
L ISTING 28.1
TestGraph.java
1 public class TestGraph {
2 public static void main(String[] args) {
3 String[] vertices = { "Seattle" , "San Francisco" , "Los Angeles" ,
4
vertices
"Denver" , "Kansas City" , "Chicago" , "Boston" , "New York" ,
5
"Atlanta" , "Miami" , "Dallas" , "Houston" };
6
7 // Edge array for graph in Figure 28.1
8 int [][] edges = {
9 { 0 , 1 }, { 0 , 3 }, { 0 , 5 },
10 { 1 , 0 }, { 1 , 2 }, { 1 , 3 },
11 { 2 , 1 }, { 2 , 3 }, { 2 , 4 }, { 2 , 10 },
12 { 3 , 0 }, { 3 , 1 }, { 3 , 2 }, { 3 , 4 }, { 3 , 5 },
13 { 4 , 2 }, { 4 , 3 }, { 4 , 5 }, { 4 , 7 }, { 4 , 8 }, { 4 , 10 },
14 { 5 , 0 }, { 5 , 3 }, { 5 , 4 }, { 5 , 6 }, { 5 , 7 },
15 { 6 , 5 }, { 6 , 7 },
16 { 7 , 4 }, { 7 , 5 }, { 7 , 6 }, { 7 , 8 },
17 { 8 , 4 }, { 8 , 7 }, { 8 , 9 }, { 8 , 10 }, { 8 , 11 },
18 { 9 , 8 }, { 9 , 11 },
19 { 10 , 2 }, { 10 , 4 }, { 10 , 8 }, { 10 , 11 },
20 { 11 , 8 }, { 11 , 9 }, { 11 , 10 }
21 };
22
23 Graph<String> graph1 = new UnweightedGraph<>(vertices, edges);
24 System.out.println( "The number of vertices in graph1: "
25 + graph1.getSize());
26 System.out.println( "The vertex with index 1 is "
27 + graph1.getVertex( 1 ));
28 System.out.println( "The index for Miami is " +
29 graph1.getIndex( "Miami" ));
30 System.out.println( "The edges for graph1:" );
31
edges
create a graph
number of vertices
get vertex
get index
graph1.printEdges();
print edges
32
33 // List of Edge objects for graph in Figure 28.3a
34 String[] names = { "Peter" , "Jane" , "Mark" , "Cindy" , "Wendy" };
 
 
Search WWH ::




Custom Search