graph
Class HashKeyedDigraph

java.lang.Object
  |
  +--graph.HashKeyedDigraph

All Implemented Interfaces:

Digraph, KeyedDigraph

public class HashKeyedDigraph

extends java.lang.Object

implements KeyedDigraph

An implementation of KeyedDigraph that wraps another Digraph (no matter what its implementation) and adds a hash table.

Field Summary

(package private) graph.Digraph	g The underlying graph.
protected java.util.Map	m Maps keys to vertices.

Constructor Summary

HashKeyedDigraph(graph.Digraph g)
If g is an empty Digraph, this constructs a new empty KeyedDigraph.

Method Summary

static graph.KeyedDigraph	fig12_15() Returns the undirected, weighted graph from figure 12.15 of the textbook.
static graph.KeyedDigraph	fig12_2() Returns the directed graph from figure 12.2 of the textbook.
graph.Vertex	findKeyedVertex(java.lang.Object k) Return the vertex with key k.
graph.Vertex	findOrInsertKeyedVertex(java.lang.Object k) Return the vertex with key k.
graph.DirectedEdge	insertDirectedEdge(graph.Vertex from, graph.Vertex to, java.lang.Object element) Adds a new directed edge from one vertex to another.
private void	insertDistance(java.lang.String s1, java.lang.String s2, int i)
void	insertReverseOf(graph.DirectedEdge e) Convenience method: Add the reverse of the given edge, with the same element.
graph.Vertex	insertVertex(java.lang.Object element) Insert and return a new vertex.
graph.DirectedEdge	keyedInsertDirectedEdge(java.lang.Object keyFrom, java.lang.Object keyTo, java.lang.Object element) Convenience method: Add a directed edge between two keyed vertices, which are looked up or added using findOrInsertKeyedVertex().
static void	main(java.lang.String[] args) This test method does some work but doesn't actually print anything.
int	numEdges() Return the size of the graph (number of edges, m).
int	numVertices() Return the order of the graph (number of vertices, n).
java.util.Iterator	outIncidentEdges(graph.Vertex v) Return an iterator over all the directed edges from a vertex.

Methods inherited from class java.lang.Object

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

Field Detail

g

graph.Digraph g

The underlying graph.

m

protected java.util.Map m

Maps keys to vertices.

Constructor Detail

HashKeyedDigraph

public HashKeyedDigraph(graph.Digraph g)

If g is an empty Digraph, this constructs a new empty KeyedDigraph. This KeyedDigraph is really just a keyed "view" of g, not a separate graph. That's because if the KeyedDigraph is modified in any way, the Digraph g will change too, and vice-versa.

Any vertices already in g will not be accessible via keys, but new vertices added through findOrInsertKeyedVertex may have keys.

Method Detail

findKeyedVertex

public graph.Vertex findKeyedVertex(java.lang.Object k)

Description copied from interface: KeyedDigraph

Return the vertex with key k.

Specified by:

findKeyedVertex in interface KeyedDigraph

findOrInsertKeyedVertex

public graph.Vertex findOrInsertKeyedVertex(java.lang.Object k)

Description copied from interface: KeyedDigraph

Return the vertex with key k. If there is none, create a new vertex with key k, and return it. The new vertex's element is initially k as well, but can be changed using Vertex.replaceElement().

This is the ONLY way to add a keyed vertex. Unkeyed vertices can be added with ordinary insertVertex(); but they do not have keys, and cannot be looked up by findKeyedVertex().

Specified by:

findOrInsertKeyedVertex in interface KeyedDigraph

keyedInsertDirectedEdge

public graph.DirectedEdge keyedInsertDirectedEdge(java.lang.Object keyFrom,
                                                  java.lang.Object keyTo,
                                                  java.lang.Object element)

Description copied from interface: KeyedDigraph

Convenience method: Add a directed edge between two keyed vertices, which are looked up or added using findOrInsertKeyedVertex().

Specified by:

keyedInsertDirectedEdge in interface KeyedDigraph

numVertices

public int numVertices()

Description copied from interface: Digraph

Return the order of the graph (number of vertices, n).

Specified by:

numVertices in interface Digraph

numEdges

public int numEdges()

Description copied from interface: Digraph

Return the size of the graph (number of edges, m).

Specified by:

numEdges in interface Digraph

outIncidentEdges

public java.util.Iterator outIncidentEdges(graph.Vertex v)

Description copied from interface: Digraph

Return an iterator over all the directed edges from a vertex.

Specified by:

outIncidentEdges in interface Digraph

insertVertex

public graph.Vertex insertVertex(java.lang.Object element)

Description copied from interface: Digraph

Insert and return a new vertex. The vertex has no incident edges yet.

Specified by:

insertVertex in interface Digraph

Parameters:

element - the element stored at the vertex.

insertDirectedEdge

public graph.DirectedEdge insertDirectedEdge(graph.Vertex from,
                                             graph.Vertex to,
                                             java.lang.Object element)
                                      throws InvalidPositionException

Description copied from interface: Digraph

Adds a new directed edge from one vertex to another.

Specified by:

insertDirectedEdge in interface Digraph

Parameters:

element - the element stored on the edge.

Throws:

InvalidPositionException - if the implementation detects that one of the vertices is not actually in this graph.

insertReverseOf

public void insertReverseOf(graph.DirectedEdge e)

Description copied from interface: Digraph

Convenience method: Add the reverse of the given edge, with the same element. Thus, to add a pair of opposing edges, you can do something like

    insertReverseOf(insertDirectedEdge(from, to, element));
 

This is convenient if from, to, or element is a complicated expression.

Specified by:

insertReverseOf in interface Digraph

fig12_2

public static graph.KeyedDigraph fig12_2()

Returns the directed graph from figure 12.2 of the textbook.

insertDistance

private void insertDistance(java.lang.String s1,
                            java.lang.String s2,
                            int i)

fig12_15

public static graph.KeyedDigraph fig12_15()

Returns the undirected, weighted graph from figure 12.15 of the textbook. Each undirected edge is represented as a pair of directed edges, each of which store the same Integer.

main

public static void main(java.lang.String[] args)

This test method does some work but doesn't actually print anything. See the Dijkstra class for a test method that actually does something with the graphs.