goldman.graph
Interface WeightedGraph<V,E extends WeightedEdge<V>>

All Superinterfaces:
Graph<V,E>, Iterable<V>
All Known Implementing Classes:
AbstractWeightedGraph, AbstractWeightedGraph.FlowGraph, WeightedAdjacencyList, WeightedAdjacencyMatrix

public interface WeightedGraph<V,E extends WeightedEdge<V>>
extends Graph<V,E>

The weighted graph algorithms we present do not depend on a particular graph implementation. Instead, they are implemented entirely in terms of the WeightedGraph ADT. One advantage of this approach is that it allows the presentation and implementation of the weighted graph algorithms to be expressed independent of the underlying weighted graph representation. The WeightedGraph interface that provides the methods required to create and modify a weighted graph, and methods to perform commonly needed computation on the graph.


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)
          Uses the Bellman-Ford shortest path algorithm to compute and return a shortest path tree for the given source vertex.
 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 source, V sink)
          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 source)
          Uses Dijkstra's shortest path algorithm to compute and return a shortest path tree for the given source vertex.
 
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
 

Method Detail

allPairsShortestPaths

ShortestPathMatrix<V,E> allPairsShortestPaths()
Uses the Floyd-Warshall all-pairs shortest path algorithm to compute and return a shortest path matrix.


generalShortestPathFromSource

InTree<V,E> generalShortestPathFromSource(V source)
Uses the Bellman-Ford shortest path algorithm to compute and return a shortest path tree for the given source vertex. This algorithm will yield the correct answer if there are negative weight edges, provided that there is no negative weight cycle.


kruskalMST

Set<E> kruskalMST()
                                          throws NegativeWeightEdgeException,
                                                 DisconnectedGraphException
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.

Throws:
NegativeWeightEdgeException
DisconnectedGraphException

maximumFlow

AbstractWeightedGraph.FlowGraph maximumFlow(V source,
                                            V sink)
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.


primMST

Set<E> primMST()
                                       throws NegativeWeightEdgeException,
                                              DisconnectedGraphException
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.

Throws:
NegativeWeightEdgeException
DisconnectedGraphException

weightedShortestPaths

InTree<V,E> weightedShortestPaths(V source)
                                                          throws NegativeWeightEdgeException,
                                                                 DisconnectedGraphException
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.

Throws:
NegativeWeightEdgeException
DisconnectedGraphException