|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--dataStructures.Graph
Constructor Summary | |
Graph()
|
Method Summary | |
void |
bellmanFord(int s,
Operable[] d,
int[] p,
Operable theZero)
Bellman and Ford algorithm to find the shortest paths from vertex s. |
void |
bfs(int v,
int[] reach,
int label)
breadth-first search reach[i] is set to label for all vertices reachable from vertex v |
int |
bipartiteCover(int[] theLabel,
int[] theCover)
|
boolean |
connected()
|
abstract int |
degree(int i)
|
void |
dfs(int v,
int[] reach,
int label)
depth-first search reach[i] is set to label for all vertices reachable from vertex v |
abstract int |
edges()
|
abstract boolean |
existsEdge(int i,
int j)
|
int[] |
findPath(int s,
int d)
find a path from s to d |
abstract int |
inDegree(int i)
|
abstract java.util.Iterator |
iterator(int i)
|
boolean |
kruskal(WeightedEdge[] spanningTreeEdges)
find a min cost spanning tree using Kruskal's method |
int |
labelComponents(int[] c)
label the components of an undirected graph |
abstract int |
outDegree(int i)
|
abstract void |
putEdge(java.lang.Object theEdge)
|
abstract void |
removeEdge(int i,
int j)
|
boolean |
topologicalOrder(int[] theOrder)
|
void |
verifyDirected(java.lang.String theMethodName)
verify that the graph is a directed graph |
void |
verifyUndirected(java.lang.String theMethodName)
verify that the graph is an undirected graph |
void |
verifyWeighted(java.lang.String theMethodName)
verify that the graph is a weighted graph |
void |
verifyWeightedUndirected(java.lang.String theMethodName)
verify that the graph is a weighted undirected graph |
abstract int |
vertices()
|
Methods inherited from class java.lang.Object |
clone,
equals,
finalize,
getClass,
hashCode,
notify,
notifyAll,
toString,
wait,
wait,
wait |
Constructor Detail |
public Graph()
Method Detail |
public abstract int vertices()
public abstract int edges()
public abstract boolean existsEdge(int i, int j)
public abstract void putEdge(java.lang.Object theEdge)
public abstract void removeEdge(int i, int j)
public abstract int degree(int i)
public abstract int inDegree(int i)
public abstract int outDegree(int i)
public abstract java.util.Iterator iterator(int i)
public void bfs(int v, int[] reach, int label)
public void dfs(int v, int[] reach, int label)
public int[] findPath(int s, int d)
public void verifyUndirected(java.lang.String theMethodName)
public void verifyDirected(java.lang.String theMethodName)
public void verifyWeightedUndirected(java.lang.String theMethodName)
public void verifyWeighted(java.lang.String theMethodName)
public boolean connected()
public int labelComponents(int[] c)
public boolean topologicalOrder(int[] theOrder)
theOrder[0:n-1]
- is set to a topological order when
such an order existspublic int bipartiteCover(int[] theLabel, int[] theCover)
theLabel
- is bipartite labeling, theLabel[i] = 1 iff i is in AtheCover
- theCover[i], i >= 0 is set to
the cover (if there is one)public boolean kruskal(WeightedEdge[] spanningTreeEdges)
spanningTreeEdges[0:n-2]
- has the min-cost-tree edges when donepublic void bellmanFord(int s, Operable[] d, int[] p, Operable theZero)
theZero
- equals zero weight
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |