package graph;
import container.*;
import java.util.Iterator;

/** This is the simplest useful directed graph interface.  It mainly
 * just has outIncidentEdges().  That is enough to support traversal
 * algorithms like DFS, BFS, and Dijkstra's algorithm.  The interface
 * is missing many graph methods proposed in the textbook's section
 * 12.1.1 -- to start with, inIncidentEdges() -- but it could be
 * extended to have those methods.<p>
 *
 * An implementation of just this simple interface doesn't have to
 * store much data.  For example, it is not necessary to store a list
 * of all vertices.  Many algorithms don't require the class to
 * maintain such a list.  Instead, the algorithm itself may store 
 * one or more of the vertices created and returned by insertVertex();
 * for example, a start vertex may be enough.<p>
 *
 * The name "Digraph" is a common abbreviation for "directed graph."
 */

public interface Digraph {  

  /** Return the order of the graph (number of vertices, n). */
  public int numVertices();

  /** Return the size of the graph (number of edges, m). */
  public int numEdges();
  
  /** Return an iterator over all the directed edges from a vertex. */
  public Iterator outIncidentEdges(Vertex v);

  /** Insert and return a new vertex.  The vertex has no incident edges yet. 
   * @param element the element stored at the vertex.
   */
  public Vertex insertVertex(Object element);

  /** Adds a new directed edge from one vertex to another. 
   * @param element the element stored on the edge.
   * @throws InvalidPositionException if the implementation detects that one
   *    of the vertices is not actually in this graph.  
   */
  public DirectedEdge insertDirectedEdge(Vertex from, Vertex to, Object element) throws InvalidPositionException;

  /** Convenience method: Add the reverse of the given edge, with
   * the same element.
   *
   * Thus, to add a pair of opposing edges, you can do something like
   * <pre>
   *    insertReverseOf(insertDirectedEdge(from, to, element));
   * </pre>
   * This is convenient if from, to, or element is a complicated
   * expression.
   */
  public void insertReverseOf(DirectedEdge e);
}