import java.util.Set; // ----------------------------------------------------------------------------- // This file specifies the Interface for a graph library. It consists of four // interfaces: // -- IGraph for directed graphs // // and three interfaces needed to specify the graph and its interface: // // -- IEdge for directed transition edges // -- INode for nodes in the graph // -- IPath for a series of edges leading from some point to another // // plus one basic convention: // // -- A Cost is a positive double. // // NOTE: in the real world, a cost comes with a unit and deserves a proper // representation, say an immutable class with two fields. // ----------------------------------------------------------------------------- // The library is expected to be located at graph. *** .com. // ----------------------------------------------------------------------------- // Specifies an imperative graph class: // // the Graph constructor should consume two positive Costs: low, high // where low <= high. The interval [low, high] specifies the range of // transition costs on edges. // interface IGraph { // the set of nodes of this graph Set nodes(); // the set of edges of this graph Set edges(); // the acceptable low cost for edges in this graph double lowCost(); // the acceptable high cost for edges in this graph double highCost(); // add e to this graph, IF: // this.lowCost() <= e.cost() && e.cost() <= this.highCost() // the addition of e may not violate the triangle inequality for this graph void addEdge(IEdge e); // join the nodes and edges of g to this graph, IF: // this.lowCost() == g.lowCost() && this.highCost() == g.highCost() && // the nodes of g and the nodes of this are disjoint sets void join(IGraph g); // is there a series of edges that start at from and end in to? boolean pathExists(INode from, INode to); // the series of edges that start at from and end in to, IF: // pathExists(from,to) IPath path(INode from, INode to); } // ----------------------------------------------------------------------------- // the underlying "terminology" (see ontology) // the Edge constructor should consume two INodes and a Cost interface IEdge { // the origination point INode from(); // the destination point INode to(); // the transition cost double cost(); } // the Node constructor should consume a String interface INode { // the name of the node String label(); } // no constrcutor is assumed to be exported interface IPath { // what is the cost for taking this path double totalCost(); // what is the next step to be taken along this path IEdge next(); // is this path empty? boolean empty(); }