// Graph, implemented with an adjacency matrix // (c) 1998, 2001 duane a. bailey package structure; import java.util.Iterator; /** * A GraphMatrixUndirected is a matrix-based graph representation that * consists of a collection of vertices and undirected edges. Portions of * the graph may be marked visited to support iterative algorithms. * Iteration is provided over vertices, edges, and vertices adjacent to a * particular vertex. * GraphMatrix differs from GraphList in that the user must commit to * an upper bound on number of vertices in graph. *
* Example Usage: *
* To create a graph representation of the movie theaters nearest * the Williams College Department of Computer Science's unix laboratory, * and to print these theaters out in order of increasing distance, * we could use the following: *
*
* public static void main(String[] argv){
* Graph theaters = new {@link #GraphMatrixUndirected(int) GraphMatrixUndirected(9)};
* FibHeap heap = new FibHeap();
*
* //instantiate array of locations
* String[] locations = new String[]{"TCL 312", "Images Cinema",
* "Movie Plex 3", "Cinema 1,2,&3",
* "Cinema 7", "Berkshire Mall Cinemas"
* ,"Hathaway's Drive Inn Theatre",
* "Hollywood Drive-In Theatre"};
*
* //instantiate array of distances between location[0]
* //and movie theaters
* double[] distances = new double[]{-1, 0.0, 12.6, 12.9, 12.9,
* 14.7, 16.5, 18.0};
*
* //build graph
* for(int i=0; i < locations.length; i++) theaters.add(locations[i]);
* for(int i=1; i < distances.length; i++){
* theaters.{@link #addEdge(Object, Object, Object) addEdge(locations[0],locations[i],new Double(distances[i]))};
* }
*
* //place neighbors of lab in into priority queue
* for(Iterator i=theaters.{@link #neighbors(Object) neighbors(locations[0])}; i.hasNext();){
* Object theater = i.next();
* Object distance = theaters.{@link #getEdge(Object,Object) getEdge(locations[0], theater).label()};
* heap.add(new ComparableAssociation((Comparable)distance,theater));
* }
*
* //print out theaters in order of distance
* while(!heap.isEmpty()){
* ComparableAssociation show = (ComparableAssociation)heap.remove();
* System.out.println(show.getValue()+" is "+show.getKey()+" miles away.");
* }
* }
*
*
*
* @version $Id: GraphMatrixUndirected.java,v 1.1 2005/09/22 22:01:14 terescoj Exp $
* @author, 2001 duane a. bailey and kimberly tabtiang
* @see GraphMatrix
* @see GraphMatrixDirected
* @see GraphListUndirected
*/
public class GraphMatrixUndirected