import java.util.Iterator;

/**
   The interface SimpleGraph specifies graph without parallel edges 
   and self-loops.
  
   @author      Franck van Breugel
   @version     1.4    August 1, 2001
*/
public interface SimpleGraph extends PositionalContainer 
{
    /**
       Returns the number of vertices of this graph.
      
       @returns The number of vertices of this graph.
    */
    public int numVertices();

    /**
       Returns the number of edges of this graph.
      
       @returns The number of edges of this graph.
    */
    public int numEdges();

    /**
       Returns the collection of the vertices of this graph.
      
       @return The collection of the vertices of this graph.
    */
    public Iterator vertices();

    /**
       Returns the collection of the edges of this graph.
      
       @return The collection of the edges of this graph.
    */
    public Iterator edges();

    /**
       Returns a vertex of the graph.
      
       @return A vertex of the graph.
       @exception EmptyContainerException if the graph is empty.
    */
    public Vertex aVertex() throws EmptyContainerException;

    /**
       Returns the degree of the specified vertex.
      
       @param vertex The vertex of which the degree is return.
       @return The degree of the specified vertex.
    */
    public int degree(Vertex vertex);

    /**
       Returns the collection of the vertices adjacent to the specified
       vertex.
      
       @param vertex The vertex of which the collection of the vertices 
       adjacent to it is returned.
       @return The collection of the vertices adjacent to the specified
       vertex.
    */
    public Iterator adjacentVertices(Vertex vertex);

    /**
       Returns the collection of the edges incident on the specified vertex.
      
       @param vertex The vertex of which the collection of the edges incident 
       on it is returned.
       @return An enumeration of the edges incident on the specified vertex.
    */
    public Iterator incidentEdges(Vertex vertex);

    /**
       Returns the end vertices of the specified edge.
     
       @param edge The edge of which the end vertices are returned.
       @return The end vertices of the specified edge.
    */
    public Vertex[] endVertices(Edge edge);

    /**
       Returns the end vertex of the specified edge different from the
       specified vertex.

       @param vertex The other end vertex of the specified edge.
       @param edge The edge of which the end vertex different from the
       specified vertex is return.
       @return The end vertex of the specified edge different from the
       specified vertex.
       @exception InvalidPositionException if the specified vertex is not 
       an endpoint of the specified edge.
    */
    public Vertex opposite(Vertex vertex, Edge edge) throws InvalidPositionException;

    /**
       Tests if the specified vertices are adjacent.

       @param first The vertex to be tested to be adjacent to the other
       specified vertex.
       @param second The vertex to be tested to be adjacent to the other
       specified vertex.
       @return true if the specified vertices are adjacent, false otherwise.
    */
    public boolean areAdjacent(Vertex first, Vertex second);

    /**
       Returns the collection of the directed edges of this graph.

       @return the collection of the directed edges of this graph.
    */
    public Iterator directedEdges();

    /**
       Returns the collection of the undirected edges of this graph.

       @return the collection of the undirected edges of this graph.
    */
    public Iterator undirectedEdges();

    /**
       Returns the destination of the specified edge.

       @param edge The edge the destination of which is to be returned.
       @return The destination of the specified edge.
       @exception InvalidPositionException if the specified edge is undirected.
    */
    public Vertex destination(Edge edge) throws InvalidPositionException; 

    /**
       Returns the origin of the specified edge.

       @param edge The edge the origin of which is to be returned.
       @return The origin of the specified edge.
       @exception InvalidPositionException if the specified edge is undirected.
    */
    public Vertex origin(Edge edge) throws InvalidPositionException; 

    /**
       Tests if the specified edge is directed.
       
       @param edge The edge to be tested to be directed.
       @return true if the specified edge is directed, false otherwise.
    */
    public boolean isDirected(Edge edge);

    /**
       Returns the in-degree of the specified vertex.

       @param vertex The vertex of which the in-degree is to be returned.
       @return The in-degree of the specified vertex.
    */
    public int indegree(Vertex vertex);

    /**
       Returns the out-degree of the specified vertex.
       
       @param vertex The vertex of which the out-degree is to be returned.
       @return The out-degree of the specified vertex.
    */
    public int outdegree(Vertex vertex);

    /**
       Returns the collection of the incoming edges of the specified vertex.
       
       @param vertex The vertex of which the collection of the incoming
       edges is to be returned.
       @return the collection of the incoming edges of the specified vertex.
    */
    public Iterator inIncidentEdges(Vertex vertex);

    /**
       Returns the collection of the outgoing edges of the specified vertex.
       
       @param vertex The vertex of which the collection of the outgoing
       edges is to be returned.
       @return the collection of the outgoing edges of the specified vertex.
    */
    public Iterator outIncidentEdges(Vertex vertex);

    /**
       Returns the collection of the vertices adjacent to the specified vertex
       along incoming edges to the specified vertex.
       
       @param vertex The vertex of which the collection of the vertices 
       adjacent to the specified vertex along incoming edges to the 
       specified vertex is to be returned.
       @return the collection of the vertices adjacent to the specified vertex
       along incoming edges to the specified vertex.
    */
    public Iterator inAdjacentVertices(Vertex vertex);

    /**
       Returns the collection of the vertices adjacent to the specified vertex
       along outgoing edges from the specified vertex.
       
       @param vertex The vertex of which the collection of the vertices 
       adjacent to the specified vertex along outgoing edges from the 
       specified vertex is to be returned.
       @return the collection of the vertices adjacent to the specified vertex
       along outgoing edges from the specified vertex.
    */
    public Iterator outAdjacentVertices(Vertex vertex);

    /**
       Inserts an edge between the specified vertices with the specified 
       element and returns it.

       @param first End vertex of edge the to be inserted.
       @param second End vertex of the edge to be inserted.
       @param element The element of the to be inserted edge.
       @return The inserted edge.
       @exception InvalidPositionException if there is already an edge 
       between the specified vertices or the specified vertices are equal.
    */
    public Edge insertEdge(Vertex first, Vertex second, Object element) throws InvalidPositionException;

    /**
       Inserts an edge from the first specified vertex to the second
       specified vertex with the specified element and returns it.

       @param first Origin of the edge to be inserted.
       @param second Destination of the edge to be inserted.
       @param element The element of the edge to be inserted.
       @return The inserted edge.
       @exception InvalidPositionException if there is already an edge 
       between the specified vertices or the specified vertices are equal.
    */
    public Edge insertDirectedEdge(Vertex first, Vertex second, Object element) throws InvalidPositionException;

    /**
       Inserts a vertex with the specified element and returns it.

       @param element The element of the vertex to be inserted.
       @return The inserted vertex.
    */
    public Vertex insertVertex(Object element);

    /**
       Removes the specified vertex from this graph.
       
       @param vertex Vertex to be removed.
    */
    public void removeVertex(Vertex vertex);

    /**
       Removes the specified edge from this graph.
       
       @param edge Edge to be removed.
    */
    public void removeEdge(Edge edge);

    /**
       Makes the specified edge undirected.

       @param edge The edge to be made undirected.
    */
    public void makeUndirected(Edge edge);

    /**
       Reverses the direction of the specified edge.

       @param edge The edge the direction of which is to be reversed.
       @exception InvalidPositionException if the specified edge is not directed.
    */
    public void reverseDirection(Edge edge) throws InvalidPositionException;

    /**
       Make the specified edge directed away from the specified vertex.

       @param edge The edge the direction of which is to be set.
       @param vertex The vertex from which the specified edge is to be directed.
       @exception InvalidPositionException if the vertex is not an endpoint 
       of the edge.
    */
    public void setDirectionFrom(Edge edge, Vertex vertex) throws InvalidPositionException;

    /**
       Make the specified edge directed to the specified vertex.

       @param edge The edge the direction of which is to be set.
       @param vertex The vertex to which the specified edge is to be directed.
       @exception InvalidPositionException if the vertex is not an endpoint 
       of the edge.
    */
    public void setDirectionTo(Edge edge, Vertex vertex) throws InvalidPositionException;
}