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