structure
Class GraphMatrixUndirected

java.lang.Object
  |
  +--structure.AbstractStructure
        |
        +--structure.GraphMatrix
              |
              +--structure.GraphMatrixUndirected

All Implemented Interfaces:

Graph, Structure

public class GraphMatrixUndirected

extends GraphMatrix

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 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.addEdge(locations[0],locations[i],new Double(distances[i]));
	}
	
	//place neighbors of lab in into priority queue
	for(Iterator i=theaters.neighbors(locations[0]); i.hasNext();){
	    Object theater = i.next();
	    Object distance = theaters.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.");
	}
  }
 

See Also:

GraphMatrix, GraphMatrixDirected, GraphListUndirected

Fields inherited from class structure.GraphMatrix

data, dict, directed, freeList, size

Constructor Summary

GraphMatrixUndirected(int size)
Construct an undirected, adjacency-matrix based graph.

Method Summary

void	addEdge(Object vLabel1, Object vLabel2, Object label) Add an edge between two vertices within the graph.
int	edgeCount() Determine the number of edges in graph.
Iterator	edges() Construct an traversal over all edges.
Object	removeEdge(Object vLabel1, Object vLabel2) Remove possible edge between vertices labeled vLabel1 and vLabel2.
String	toString() Construct a string representation of graph.

Methods inherited from class structure.GraphMatrix

add, clear, contains, containsEdge, degree, get, getEdge, isDirected, isEmpty, isVisited, isVisitedEdge, iterator, neighbors, remove, reset, size, visit, visitEdge

Methods inherited from class structure.AbstractStructure

elements, hashCode, values

Methods inherited from class java.lang.Object

, clone, equals, finalize, getClass, notify, notifyAll, registerNatives, wait, wait, wait

Methods inherited from interface structure.Structure

elements, values

Constructor Detail

GraphMatrixUndirected

public GraphMatrixUndirected(int size)

Construct an undirected, adjacency-matrix based graph.

Parameters:

size - Maximum number of vertices in graph.

Method Detail

addEdge

public void addEdge(Object vLabel1,
                    Object vLabel2,
                    Object label)

Add an edge between two vertices within the graph. Edge is undirected. Duplicate edges are silently replaced. Labels on edges may be null.

Overrides:

addEdge in class GraphMatrix

Parameters:

vLabel1 - One vertex.

vLabel2 - Another vertex.

label - Label associated with the edge.

Precondition:

vLabel1 and vLabel2 are labels of existing vertices, v1 & v2

Postcondition:

an edge (undirected) is inserted between v1 and v2; if edge is new, it is labeled with label (can be null)

removeEdge

public Object removeEdge(Object vLabel1,
                         Object vLabel2)

Remove possible edge between vertices labeled vLabel1 and vLabel2.

Overrides:

removeEdge in class GraphMatrix

Parameters:

vLabel1 - One vertex.

vLabel2 - Another vertex.

Precondition:

vLabel1 and vLabel2 are labels of existing vertices

Postcondition:

edge is removed, its label is returned

Returns:

The label associated with the edge removed.

edgeCount

public int edgeCount()

Determine the number of edges in graph.

Overrides:

edgeCount in class GraphMatrix

Postcondition:

returns the number of edges in graph

Returns:

Number of edges in graph.

edges

public Iterator edges()

Construct an traversal over all edges. edge is considered exactly once. Order is not guaranteed.

Overrides:

edges in class GraphMatrix

Postcondition:

returns traversal across all edges of graph (returns Edges)

Returns:

AbstractIterator over edges.

toString

public String toString()

Construct a string representation of graph.

Overrides:

toString in class Object

Postcondition:

returns string representation of graph

Returns:

String representing graph.