|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
public interface WeightedGraph<V,E extends WeightedEdge<V>>
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 |
---|
ShortestPathMatrix<V,E> allPairsShortestPaths()
InTree<V,E> generalShortestPathFromSource(V source)
Set<E> kruskalMST() throws NegativeWeightEdgeException, DisconnectedGraphException
DisconnectedGraphException
when the graph is not connected,
a NegativeWeightEdgeException
when a negative weight edge
is encountered, and a GraphException
when the graph is directed.
NegativeWeightEdgeException
DisconnectedGraphException
AbstractWeightedGraph.FlowGraph maximumFlow(V source, V sink)
Set<E> primMST() throws NegativeWeightEdgeException, DisconnectedGraphException
DisconnectedGraphException
when the graph is not connected,
a NegativeWeightEdgeException
when a negative weight edge
is encountered, and an IllegalArgumentException
when the graph is directed.
NegativeWeightEdgeException
DisconnectedGraphException
InTree<V,E> weightedShortestPaths(V source) throws NegativeWeightEdgeException, DisconnectedGraphException
NegativeWeightEdgeException
when the
graph has a negative weight edge reachable from the source.
NegativeWeightEdgeException
DisconnectedGraphException
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |