structure5
Class GraphListUndirected<V,E>

java.lang.Object
  structure5.AbstractStructure<V>
      structure5.GraphList<V,E>
          structure5.GraphListUndirected<V,E>

All Implemented Interfaces:

java.lang.Iterable<V>, Graph<V,E>, Structure<V>

public class GraphListUndirected<V,E>
extends GraphList<V,E>

A GraphListUndirected is a list-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.

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 GraphListUndirected();
      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:

GraphList, GraphListDirected, GraphMatrixUndirected

Field Summary

Fields inherited from class structure5.GraphList

dict, directed

Constructor Summary

GraphListUndirected()
Construct an undirected, adjacency-list based graph.

Method Summary

void	addEdge(V vLabel1, V vLabel2, E label) Add an edge between two vertices within the graph.
int	edgeCount() Determine the number of edges in graph.
V	remove(V label) Remove a vertex from the graph.
E	removeEdge(V vLabel1, V vLabel2) Remove possible edge between vertices labeled vLabel1 and vLabel2.
java.lang.String	toString() Construct a string representation of graph.

Methods inherited from class structure5.GraphList

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

Methods inherited from class structure5.AbstractStructure

elements, hashCode, values

Methods inherited from class java.lang.Object

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

Methods inherited from interface structure5.Structure

elements, values

Constructor Detail

GraphListUndirected

public GraphListUndirected()

Construct an undirected, adjacency-list based graph.

Postcondition:

constructs an undirected graph

Method Detail

addEdge

public void addEdge(V vLabel1,
                    V vLabel2,
                    E label)

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

Specified by:

addEdge in interface Graph<V,E>

Specified by:

addEdge in class GraphList<V,E>

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)

remove

public V remove(V label)

Remove a vertex from the graph. Associated edges are also removed. Non-vertices are silently ignored.

Specified by:

remove in interface Graph<V,E>

Specified by:

remove in interface Structure<V>

Specified by:

remove in class GraphList<V,E>

Parameters:

label - The label of the vertex within the graph.

Returns:

The label associated with the vertex.

Precondition:

label is non-null vertex label

Postcondition:

vertex with "equals" label is removed, if found

removeEdge

public E removeEdge(V vLabel1,
                    V vLabel2)

Remove possible edge between vertices labeled vLabel1 and vLabel2.

Specified by:

removeEdge in interface Graph<V,E>

Specified by:

removeEdge in class GraphList<V,E>

Parameters:

vLabel1 - One vertex.

vLabel2 - Another vertex.

Returns:

The label associated with the edge removed.

Precondition:

vLabel1 and vLabel2 are labels of existing vertices

Postcondition:

edge is removed, its label is returned

edgeCount

public int edgeCount()

Determine the number of edges in graph.

Specified by:

edgeCount in interface Graph<V,E>

Specified by:

edgeCount in class GraphList<V,E>

Returns:

Number of edges in graph.

Postcondition:

returns the number of edges in graph

toString

public java.lang.String toString()

Construct a string representation of graph.

Overrides:

toString in class java.lang.Object

Returns:

String representing graph.

Postcondition:

returns string representation of graph