|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectgoldman.graph.AbstractGraph<V,E>
goldman.graph.AbstractWeightedGraph<V,E>
public abstract class AbstractWeightedGraph<V,E extends WeightedEdge<V>>
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 |
---|
public AbstractWeightedGraph(GraphRepresentation<V,E> rep, boolean multigraph)
rep
- the graph representation to usemultigraph
- which indicates if the graph is a multigraphMethod Detail |
---|
public void greedyTreeBuilder(InTree<V,E> tree, double seedCost, Comparator<Double> comp) throws NegativeWeightEdgeException
tree
- an (initially empty) in-tree to be constructedseedCost
- the cost that should be associated with the first vertex
placed in the treecomp
- 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
NegativeWeightEdgeException
- the algorithm cannot guarantee a
correct result due to a negative weight edge.public InTree<V,E> weightedShortestPaths(V s) throws NegativeWeightEdgeException
WeightedGraph
NegativeWeightEdgeException
when the
graph has a negative weight edge reachable from the source.
weightedShortestPaths
in interface WeightedGraph<V,E extends WeightedEdge<V>>
s
- the
source vertex
NegativeWeightEdgeException
- the
graph has a negative weight edge reachable from spublic Set<E> primMST() throws NegativeWeightEdgeException, DisconnectedGraphException
WeightedGraph
DisconnectedGraphException
when the graph is not connected,
a NegativeWeightEdgeException
when a negative weight edge
is encountered, and an IllegalArgumentException
when the graph is directed.
primMST
in interface WeightedGraph<V,E extends WeightedEdge<V>>
DisconnectedGraphException
- the
graph is not connected
NegativeWeightEdgeException
- a negative
edge weight is encountered
GraphException
- the
graph is directedpublic Set<E> kruskalMST() throws NegativeWeightEdgeException, DisconnectedGraphException
WeightedGraph
DisconnectedGraphException
when the graph is not connected,
a NegativeWeightEdgeException
when a negative weight edge
is encountered, and a GraphException
when the graph is directed.
kruskalMST
in interface WeightedGraph<V,E extends WeightedEdge<V>>
DisconnectedGraphException
- the
graph is not connected
NegativeWeightEdgeException
- a negative
edge weight is encountered
GraphException
- the
graph is directedpublic InTree<V,E> generalShortestPathFromSource(V source)
generalShortestPathFromSource
in interface WeightedGraph<V,E extends WeightedEdge<V>>
source
- the source
vertex
public ShortestPathMatrix<V,E> allPairsShortestPaths()
WeightedGraph
allPairsShortestPaths
in interface WeightedGraph<V,E extends WeightedEdge<V>>
public AbstractWeightedGraph.FlowGraph maximumFlow(V s, V t)
WeightedGraph
maximumFlow
in interface WeightedGraph<V,E extends WeightedEdge<V>>
s
- the source vertext
- the sink vertex
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |