import java.util.Iterator; /** * A common Java interface for the Graph ADT, encompassing graphs both * unweighted and weighted, undirected and directed. Note that an object of * Graph type can't add edges to itself; the sub-interfaces UnweightedGraph and * WeightedGraph contain the necessary methods for adding edges.
* Note that this particular interface explicitly refers to vertices by a * consecutive set of integral vertex IDs, from 0 to N-1 (where N is the number * of vertices), and conceives of edges only in terms of their endpoints. * This is the canonical conception of a graph for standard graph algorithms, * but lacks common features for modeling, e.g., a road network.
* To represent metadata like vertex labels, it is recommended that the user * maintain their own dictionaries mapping between vertex IDs (or pairs thereof, * for edges) and the desired values.
* Any method that takes one or more vertex IDs as arguments may throw an
* IndexOutOfBoundsException if any input ID is out of bounds.
*
* @author Jadrian Miles
*/
public interface Graph {
/** Adds a new vertex.
* @return the ID of the added vertex.
*/
public int addVertex();
/** Returns whether an edge exists between two vertices.
* In an undirected graph, this returns the same as hasEdge(end, begin).
*/
public boolean hasEdge(int begin, int end);
/** Returns the out-degree of the specified vertex. */
public int getDegree(int v);
/** Returns the in-degree of the specified vertex. */
public int getInDegree(int v);
/** Returns an iterable object that allows iteration over the neighbors of
* the specified vertex. In particular, the vertex u is included in the
* sequence if and only if there is an edge from v to u in the graph.
*/
public Iterable