1: package GraphPackage;
2: import ADTPackage.*; // Classes that implement various ADTs
3: /**
4: An interface of methods that process an existing graph.
5: @author Frank M. Carrano
6: @author Timothy M. Henry
7: @version 5.0
8: */
9: public interface GraphAlgorithmsInterface<T>
10: {
11: /** Performs a breadth-first traversal of this graph.
12: @param origin An object that labels the origin vertex of the traversal.
13: @return A queue of labels of the vertices in the traversal, with
14: the label of the origin vertex at the queue's front. */
15: public QueueInterface<T> getBreadthFirstTraversal(T origin);
17: /** Performs a depth-first traversal of this graph.
18: @param origin An object that labels the origin vertex of the traversal.
19: @return A queue of labels of the vertices in the traversal, with
20: the label of the origin vertex at the queue's front. */
21: public QueueInterface<T> getDepthFirstTraversal(T origin);
23: /** Performs a topological sort of the vertices in this graph without cycles.
24: @return A stack of vertex labels in topological order, beginning
25: with the stack's top. */
26: public StackInterface<T> getTopologicalOrder();
28: /** Finds the shortest-length path between two given vertices in this graph.
29: @param begin An object that labels the path's origin vertex.
30: @param end An object that labels the path's destination vertex.
31: @param path A stack of labels that is empty initially;
32: at the completion of the method, this stack contains
33: the labels of the vertices along the shortest path;
34: the label of the origin vertex is at the top, and
35: the label of the destination vertex is at the bottom
36: @return The length of the shortest path. */
37: public int getShortestPath(T begin, T end, StackInterface<T> path);
39: /** Finds the least-cost path between two given vertices in this graph.
40: @param begin An object that labels the path's origin vertex.
41: @param end An object that labels the path's destination vertex.
42: @param path A stack of labels that is empty initially;
43: at the completion of the method, this stack contains
44: the labels of the vertices along the cheapest path;
45: the label of the origin vertex is at the top, and
46: the label of the destination vertex is at the bottom
47: @return The cost of the cheapest path. */
48: public double getCheapestPath(T begin, T end, StackInterface<T> path);
49: } // end GraphAlgorithmsInterface