|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--structure.AbstractStructure | +--structure.GraphMatrix | +--structure.GraphMatrixDirected
A GraphMatrixDirected is a matrix-based graph representation that consists of a collection of vertices and directed 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 = newGraphMatrixDirected(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 betweenlocation[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."); } }
GraphMatrix
,
GraphMatrixUndirected
,
GraphListDirected
Field Summary |
Fields inherited from class structure.GraphMatrix |
data, dict, directed, freeList, size |
Constructor Summary | |
GraphMatrixDirected(int size)
Construct a directed, adjacency-matrix based graph. |
Method Summary | |
void |
addEdge(java.lang.Object vLabel1,
java.lang.Object vLabel2,
java.lang.Object label)
Add an edge between two vertices within the graph. |
int |
edgeCount()
Determine the number of edges in graph. |
java.util.Iterator |
edges()
Construct an traversal over all edges. |
java.lang.Object |
removeEdge(java.lang.Object vLabel1,
java.lang.Object vLabel2)
Remove possible edge between vertices labeled vLabel1 and vLabel2. |
java.lang.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, wait, wait, wait |
Methods inherited from interface structure.Structure |
elements, values |
Constructor Detail |
public GraphMatrixDirected(int size)
size
- The maximum number of vertices allowed in graph.Method Detail |
public void addEdge(java.lang.Object vLabel1, java.lang.Object vLabel2, java.lang.Object label)
addEdge
in interface Graph
addEdge
in class GraphMatrix
vLabel1
- Source vertex.vLabel2
- Destination vertex.label
- Label associated with the edge.public java.lang.Object removeEdge(java.lang.Object vLabel1, java.lang.Object vLabel2)
removeEdge
in interface Graph
removeEdge
in class GraphMatrix
vLabel1
- Source vertex.vLabel2
- Destination vertex.
public int edgeCount()
edgeCount
in interface Graph
edgeCount
in class GraphMatrix
public java.util.Iterator edges()
edges
in interface Graph
edges
in class GraphMatrix
public java.lang.String toString()
toString
in class java.lang.Object
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |