|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--dataStructures.Graph | +--dataStructures.AdjacencyWDigraph
Constructor Summary | |
AdjacencyWDigraph()
|
|
AdjacencyWDigraph(int theVertices)
|
Method Summary | |
void |
allPairs(Operable[][] c,
int[][] kay)
dynamic programming all pairs shortest paths algorithm compute c[i][j] and kay[i][j] for all i and j |
java.lang.Object |
btSalesperson(int[] bestTour,
Operable theZero)
traveling salesperson by backtracking |
int |
degree(int i)
this method is undefined for directed graphs |
int |
edges()
|
boolean |
existsEdge(int i,
int j)
|
int |
inDegree(int i)
|
java.util.Iterator |
iterator(int i)
create and return an iterator for vertex i |
java.lang.Object |
leastCostBBSalesperson(int[] bestTour,
Operable theZero)
least-cost branch-and-bound code to find a shortest tour |
static void |
main(java.lang.String[] args)
test program for Graph methods |
int |
outDegree(int i)
|
void |
output()
output the adjacency matrix |
void |
putEdge(java.lang.Object theEdge)
put edge e into the digraph; if the edge is already there, update its weight to e.weight |
void |
removeEdge(int i,
int j)
remove the edge (i,j) |
void |
shortestPaths(int sourceVertex,
Operable[] distanceFromSource,
int[] predecessor)
find shortest paths from sourceVertex |
int |
vertices()
|
Methods inherited from class dataStructures.Graph |
bellmanFord,
bfs,
bipartiteCover,
connected,
dfs,
findPath,
kruskal,
labelComponents,
topologicalOrder,
verifyDirected,
verifyUndirected,
verifyWeighted,
verifyWeightedUndirected |
Methods inherited from class java.lang.Object |
clone,
equals,
finalize,
getClass,
hashCode,
notify,
notifyAll,
toString,
wait,
wait,
wait |
Constructor Detail |
public AdjacencyWDigraph(int theVertices)
public AdjacencyWDigraph()
Method Detail |
public int vertices()
public int edges()
public boolean existsEdge(int i, int j)
public void putEdge(java.lang.Object theEdge)
public void removeEdge(int i, int j)
public int degree(int i)
public int outDegree(int i)
public int inDegree(int i)
public void output()
public java.util.Iterator iterator(int i)
public void shortestPaths(int sourceVertex, Operable[] distanceFromSource, int[] predecessor)
public void allPairs(Operable[][] c, int[][] kay)
public java.lang.Object btSalesperson(int[] bestTour, Operable theZero)
theZero
- zero weightbestTour
- bestTour[1:n] is set to best tourpublic java.lang.Object leastCostBBSalesperson(int[] bestTour, Operable theZero)
theZero
- zero weightbestTour
- bestTour[i] set to i'th vertex on shortest tourpublic static void main(java.lang.String[] args)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |