goldman.graph
Class AbstractWeightedGraph<V,E extends WeightedEdge<V>>

java.lang.Object
  extended by goldman.graph.AbstractGraph<V,E>
      extended by goldman.graph.AbstractWeightedGraph<V,E>
All Implemented Interfaces:
Graph<V,E>, WeightedGraph<V,E>, Iterable<V>
Direct Known Subclasses:
WeightedAdjacencyList, WeightedAdjacencyMatrix

public abstract class AbstractWeightedGraph<V,E extends WeightedEdge<V>>
extends AbstractGraph<V,E>
implements WeightedGraph<V,E>

The AbstractWeightedGraph class embodies algorithms that perform computations on a weighted graph in terms of the WeightedGraph interface. This allows subclasses that use any graph representation to benefit from these algorithms.


Nested Class Summary
 class AbstractWeightedGraph.FlowGraph
           
 
Field Summary
 
Fields inherited from class goldman.graph.AbstractGraph
INF
 
Constructor Summary
AbstractWeightedGraph(GraphRepresentation<V,E> rep, boolean multigraph)
           
 
Method Summary
 ShortestPathMatrix<V,E> allPairsShortestPaths()
          Uses the Floyd-Warshall all-pairs shortest path algorithm to compute and return a shortest path matrix.
 InTree<V,E> generalShortestPathFromSource(V source)
          This method implements the Bellman-Ford single-source shortest path algorithm
 void greedyTreeBuilder(InTree<V,E> tree, double seedCost, Comparator<Double> comp)
           
 Set<E> kruskalMST()
          Uses Kruskal's minimum spanning tree to return a set of edges that form a minimum spanning tree for this graph.
 AbstractWeightedGraph.FlowGraph maximumFlow(V s, V t)
          Uses the Edmonds-Karp implementation of the basic Ford-Fulkerson augmenting path method to find a maximum flow (and a minimum cut) for the flow network defined by the provided source and sink.
 Set<E> primMST()
          Uses Prim's minimum spanning tree to return a set of edges that forms a minimum spanning tree for this graph.
 InTree<V,E> weightedShortestPaths(V s)
          Uses Dijkstra's shortest path algorithm to compute and return a shortest path tree for the given source vertex.
 
Methods inherited from class goldman.graph.AbstractGraph
addEdge, addVertex, allowsMultiEdges, containsEdge, containsVertex, edgesFrom, edgesTo, getConnectedComponents, getCycle, getEdge, getStronglyConnectedComponents, hasCycle, isDirected, iterator, numConnectedComponents, numStronglyConnectedComponents, numVertices, removeEdge, removeVertex, topologicalOrder, toString, unweightedShortestPaths
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.graph.Graph
addEdge, addVertex, allowsMultiEdges, containsEdge, containsVertex, edgesFrom, edgesTo, getConnectedComponents, getCycle, getEdge, getStronglyConnectedComponents, hasCycle, isDirected, iterator, numConnectedComponents, numStronglyConnectedComponents, numVertices, removeEdge, removeVertex, topologicalOrder, unweightedShortestPaths
 

Constructor Detail

AbstractWeightedGraph

public AbstractWeightedGraph(GraphRepresentation<V,E> rep,
                             boolean multigraph)
Parameters:
rep - the graph representation to use
multigraph - which indicates if the graph is a multigraph
Method Detail

greedyTreeBuilder

public void greedyTreeBuilder(InTree<V,E> tree,
                              double seedCost,
                              Comparator<Double> comp)
                       throws NegativeWeightEdgeException
Parameters:
tree - an (initially empty) in-tree to be constructed
seedCost - the cost that should be associated with the first vertex placed in the tree
comp - the comparator to apply to the cost function so that the highest priority vertex is the one that should be placed in the tree next
Throws:
NegativeWeightEdgeException - the algorithm cannot guarantee a correct result due to a negative weight edge.

weightedShortestPaths

public InTree<V,E> weightedShortestPaths(V s)
                                                          throws NegativeWeightEdgeException
Description copied from interface: WeightedGraph
Uses Dijkstra's shortest path algorithm to compute and return a shortest path tree for the given source vertex. It throws a NegativeWeightEdgeException when the graph has a negative weight edge reachable from the source.

Specified by:
weightedShortestPaths in interface WeightedGraph<V,E extends WeightedEdge<V>>
Parameters:
s - the source vertex
Throws:
NegativeWeightEdgeException - the graph has a negative weight edge reachable from s

primMST

public Set<E> primMST()
                                       throws NegativeWeightEdgeException,
                                              DisconnectedGraphException
Description copied from interface: WeightedGraph
Uses Prim's minimum spanning tree to return a set of edges that forms a minimum spanning tree for this graph. It throws a DisconnectedGraphException when the graph is not connected, a NegativeWeightEdgeException when a negative weight edge is encountered, and an IllegalArgumentException when the graph is directed.

Specified by:
primMST in interface WeightedGraph<V,E extends WeightedEdge<V>>
Returns:
a set of edges that is a minimum spanning tree for this graph
Throws:
DisconnectedGraphException - the graph is not connected
NegativeWeightEdgeException - a negative edge weight is encountered
GraphException - the graph is directed

kruskalMST

public Set<E> kruskalMST()
                                          throws NegativeWeightEdgeException,
                                                 DisconnectedGraphException
Description copied from interface: WeightedGraph
Uses Kruskal's minimum spanning tree to return a set of edges that form a minimum spanning tree for this graph. It throws a DisconnectedGraphException when the graph is not connected, a NegativeWeightEdgeException when a negative weight edge is encountered, and a GraphException when the graph is directed.

Specified by:
kruskalMST in interface WeightedGraph<V,E extends WeightedEdge<V>>
Returns:
a set of edges that is a minimum spanning tree for this graph
Throws:
DisconnectedGraphException - the graph is not connected
NegativeWeightEdgeException - a negative edge weight is encountered
GraphException - the graph is directed

generalShortestPathFromSource

public InTree<V,E> generalShortestPathFromSource(V source)
This method implements the Bellman-Ford single-source shortest path algorithm

Specified by:
generalShortestPathFromSource in interface WeightedGraph<V,E extends WeightedEdge<V>>
Parameters:
source - the source vertex
Returns:
a shortest path tree for the provided source

allPairsShortestPaths

public ShortestPathMatrix<V,E> allPairsShortestPaths()
Description copied from interface: WeightedGraph
Uses the Floyd-Warshall all-pairs shortest path algorithm to compute and return a shortest path matrix.

Specified by:
allPairsShortestPaths in interface WeightedGraph<V,E extends WeightedEdge<V>>
Returns:
a shortest path matrix.

maximumFlow

public AbstractWeightedGraph.FlowGraph maximumFlow(V s,
                                                   V t)
Description copied from interface: WeightedGraph
Uses the Edmonds-Karp implementation of the basic Ford-Fulkerson augmenting path method to find a maximum flow (and a minimum cut) for the flow network defined by the provided source and sink.

Specified by:
maximumFlow in interface WeightedGraph<V,E extends WeightedEdge<V>>
Parameters:
s - the source vertex
t - the sink vertex
Returns:
a flow graph with the maximum flow from s to t, for which only edges with non-zero flow are included.