package rpi.goldsd.graph;

import java.util.Enumeration;
import java.util.Stack;
import rpi.goldsd.container.*;

/**
 * The <tt>Graph</tt> class is used to represent a single directed or
 * undirected graph consisting of zero or more vertices and edges.
 *
 * @see Vertex
 * @see Edge
 * @see GraphBase
 * @version 2.1, 5/12/98
 * @author David Goldschmidt
 */
public class Graph extends GraphBase
{
  /* ******************  CONSTRUCTOR METHODS  ****************** */

  /**
   * Constructs an empty graph with the specified name, initial
   * vertex hashtable size, and initial edge hashtable size.
   * @param name the user-defined name of this graph.
   * @param vertexTableSize the initial hashtable size for the hashtable
   *                        used to contain the set of vertices.
   * @param edgeTableSize the initial hashtable size for the
   *                      hashtable used to contain the set of edges.
   */
  public Graph( String name, int vertexTableSize, int edgeTableSize )
  {
    super( name, vertexTableSize, edgeTableSize );
  }


  /**
   * Constructs an empty graph with the specified initial vertex
   * hashtable size and initial edge hashtable size.
   * @param vertexTableSize the initial hashtable size for the hashtable
   *                        used to contain the set of vertices.
   * @param edgeTableSize the initial hashtable size for the
   *                      hashtable used to contain the set of edges.
   */
  public Graph( int vertexTableSize, int edgeTableSize )
  {
    super( vertexTableSize, edgeTableSize );
  }


  /**
   * Constructs an empty graph with the specified name.
   * @param name the user-defined name of this graph.
   */
  public Graph( String name )  { super( name ); }


  /**
   * Constructs a graph by copying another graph.
   * @param G the graph to copy.
   */
  public Graph( GraphBase G )  { super( G ); }


  /**
   * Clones this graph.
   * @return a new graph that is a clone of this graph.
   */
  public Object clone()
  {
    Graph G = new Graph( "Clone of " + name, vertices.getTableSize(),
                         edges.getTableSize() );

    super.graphCopyHelper( G, this );
    return G;
  }


  /** Constructs an unnamed empty graph. */
  public Graph()  { super(); }


  /**
   * Constructs a random graph with the specified name, the number of
   * vertices to create, and the probability of an undirected edge existing
   * between each distinct pair of vertices.  When the <tt>weighted</tt> flag
   * is <tt>true</tt>, each edge is assigned a random weight in the range
   * specified by the <tt>minWeight</tt> and <tt>maxWeight</tt> arguments.
   * Two <tt>Sequence</tt> arguments provide an enumeration of unique key
   * values for both the vertices and the edges of this graph.
   * <p>
   * Note that all other random-graph constructor methods call this method.
   * @param name the name of the constructed graph.
   * @param numVertices the number of vertices to add to this graph.
   * @param probabilityOfEdge the probability of an edge existing
   *                          between a given pair of distinct vertices.
   * @param weighted a <tt>boolean</tt> flag specifying whether the edges
   *                 of the generated graph are to be weighted.
   * @param minWeight the minimum weight assigned to an edge.
   * @param maxWeight the maximum weight assigned to an edge.
   * @param vertexSequence used to generate unique <tt>Hashable</tt> objects
   *                       to be associated with each generated vertex.
   * @param edgeSequence used to generate unique <tt>Hashable</tt> objects to
   *                     be associated with each generated edge.
   */
  public Graph( String name, int numVertices, double probabilityOfEdge,
                boolean weighted, double minWeight, double maxWeight,
                Sequence vertexSequence, Sequence edgeSequence )
  {
    this( name, Table.DEFAULT_SIZE, Table.DEFAULT_SIZE );

    Enumeration keys = null;

    if ( vertexSequence == null )
    {
      for ( int i = 0 ; i < numVertices ; i++ )
        this.add( new Vertex() );
    }
    else
    {
      keys = vertexSequence.sequence();
      for ( int i = 0 ; i < numVertices ; i++ )
        this.add( new Vertex( (Hashable)keys.nextElement() ) );
    }

    if ( edgeSequence != null ) keys = edgeSequence.sequence();
    Stack stack = new Stack();
    Enumeration p = this.vertices();
    while ( p.hasMoreElements() )
    {
      Vertex v = (Vertex)p.nextElement();
      stack.push(v);
      Enumeration q = this.vertices();
      while ( q.hasMoreElements() )
      {
        Vertex w = (Vertex)q.nextElement();
        if ( Math.random() < probabilityOfEdge && v != w && ! stack.contains(w) )
        {
          if ( weighted )
          {
            double weight = Math.random() * (maxWeight-minWeight) + minWeight;

            if ( edgeSequence == null )
              this.add( new Edge( v, w, weight ) );
            else
              this.add( new Edge( v, w, (Hashable)keys.nextElement(), weight ) );
          }
          else
          {
            if ( edgeSequence == null )
              this.add( new Edge( v, w ) );
            else
              this.add( new Edge( v, w, (Hashable)keys.nextElement() ) );
          }
        }
      }
    }
  }


  /**
   * Constructs a random graph with the specified number of vertices and
   * the probability of an edge existing between each distinct pair of
   * vertices.  Two <tt>Sequence</tt> arguments provide an enumeration of
   * unique key values for both the vertices and the edges of this graph.
   * @param name the name of the constructed graph.
   * @param numVertices the number of vertices to add to this graph.
   * @param probabilityOfEdge the probability of an edge existing between a
   *                          given pair of distinct vertices.
   * @param vertexSequence used to generate unique <tt>Hashable</tt> objects
   *                       to be associated with each generated vertex.
   * @param edgeSequence used to generate unique <tt>Hashable</tt> objects to
   *                     be associated with each generated edge.
   */
  public Graph( String name, int numVertices, double probabilityOfEdge,
                Sequence vertexSequence, Sequence edgeSequence )
  {
    this( DEFAULT_NAME, numVertices, probabilityOfEdge, false, 0.0, 0.0,
          vertexSequence, edgeSequence );
  }


  /**
   * Constructs a random unnamed graph with the specified number of vertices
   * and the probability of an edge existing between each distinct pair of
   * vertices.  Two <tt>Sequence</tt> arguments provide an enumeration of
   * unique key values for both the vertices and the edges of this graph.
   * @param numVertices the number of vertices to add to this graph.
   * @param probabilityOfEdge the probability of an edge existing between a
   *                          given pair of distinct vertices.
   * @param vertexSequence used to generate unique <tt>Hashable</tt> objects
   *                       to be associated with each generated vertex.
   * @param edgeSequence used to generate unique <tt>Hashable</tt> objects to
   *                     be associated with each generated edge.
   */
  public Graph( int numVertices, double probabilityOfEdge,
                Sequence vertexSequence, Sequence edgeSequence )
  {
    this( DEFAULT_NAME, numVertices, probabilityOfEdge, vertexSequence,
          edgeSequence );
  }


  /**
   * Constructs a random graph with the specified number of vertices and
   * the probability of an edge existing between each distinct pair of
   * vertices.  Each edge is assigned a random weight in the range specified
   * by the <tt>minWeight</tt> and <tt>maxWeight</tt> arguments.
   * @param name the name of the constructed graph.
   * @param numVertices the number of vertices to add to this graph.
   * @param probabilityOfEdge the probability of an edge existing between a
   *                          given pair of distinct vertices.
   * @param minWeight the minimum weight assigned to an edge.
   * @param maxWeight the maximum weight assigned to an edge.
   */
  public Graph( String name, int numVertices, double probabilityOfEdge,
                double minWeight, double maxWeight )
  {
    this( name, numVertices, probabilityOfEdge, true, minWeight, maxWeight,
          null, null );
  }


  /**
   * Constructs a random unnamed graph with the specified number of vertices
   * and the probability of an edge existing between each distinct pair of
   * vertices.  Each edge is assigned a random weight in the range specified
   * by the <tt>minWeight</tt> and <tt>maxWeight</tt> arguments.
   * @param numVertices the number of vertices to add to this graph.
   * @param probabilityOfEdge the probability of an edge existing between a
   *                          given pair of distinct vertices.
   * @param minWeight the minimum weight assigned to an edge.
   * @param maxWeight the maximum weight assigned to an edge.
   */
  public Graph( int numVertices, double probabilityOfEdge, double minWeight,
                double maxWeight )
  {
    this( DEFAULT_NAME, numVertices, probabilityOfEdge, minWeight, maxWeight );
  }


  /**
   * Constructs a random graph with the specified number of vertices and
   * the probability of an edge existing between each distinct pair of
   * vertices.
   * @param name the name of the constructed graph.
   * @param numVertices the number of vertices to add to this graph.
   * @param probabilityOfEdge the probability of an edge existing between a
   *                          given pair of distinct vertices.
   */
  public Graph( String name, int numVertices, double probabilityOfEdge )
  {
    this( name, numVertices, probabilityOfEdge, false, 0.0, 0.0, null, null );
  }


  /**
   * Constructs a random unnamed graph with the specified number of vertices
   * and the probability of an edge existing between each distinct pair of
   * vertices.
   * @param numVertices the number of vertices to add to this graph.
   * @param probabilityOfEdge the probability of an edge existing between a
   *                          given pair of distinct vertices.
   */
  public Graph( int numVertices, double probabilityOfEdge )
  {
    this( DEFAULT_NAME, numVertices, probabilityOfEdge );
  }



  /* ******************  ACCESSOR METHODS  ****************** */

  /**
   * Tests if this graph is a clique (a complete graph).
   * @return <TT>true</TT> if this graph is a clique;
   *         <TT>false</TT> otherwise.
   */
  public boolean isClique()
  {
    Graph G = Algorithms.complement( this );
    return ( G.numEdges() == 0 );
  }


  /**
   * Tests if this graph is a complete graph.
   * @return <TT>true</TT> if this graph is complete;
   *         <TT>false</TT> otherwise.
   */
  public boolean isComplete()  { return isClique(); }


  /**
   * Tests if this graph is a connected graph.
   * @return <TT>true</TT> if this graph is connected;
   *         <TT>false</TT> otherwise.
   */
  public boolean isConnected()
  {
    Tree T = Algorithms.depthFirstTraversal( this );
    return ( numVertices() == T.numVertices() );
  }



  /* ******************  MUTATOR METHODS  ****************** */

  /**
   * Adds the given edge to this graph if it is not already
   * in this graph.  The two endpoint vertices associated with
   * the given edge must already be in this graph.
   * @param E the edge to be added to this graph.
   * @exception rpi.goldsd.container.DuplicateElementException if
   *            the key is already present in the set of vertices.
   * @exception rpi.goldsd.graph.InAnotherGraphException if the
   *            edge is already in a different graph.
   * @exception rpi.goldsd.graph.VertexNotFoundException if either
   *            of the endpoint vertices of the edge are not in
   *            this graph.
   */
  public synchronized void add( Edge E )
    throws rpi.goldsd.container.DuplicateElementException,
           InAnotherGraphException, VertexNotFoundException
  {
    addBase( E );
  }


  /**
   * Adds the given vertex to this graph if it is not already in
   * this graph.
   * @param V the vertex to be added to this graph.
   * @exception rpi.goldsd.container.DuplicateElementException if
   *            the key is already present in the set of vertices.
   * @exception rpi.goldsd.graph.InAnotherGraphException if the
   *            vertex is already in a different graph.
   */
  public synchronized void add( Vertex V )
    throws rpi.goldsd.container.DuplicateElementException,
           InAnotherGraphException
  {
    addBase( V );
  }


  /**
   * Removes the given edge from this graph.
   * @param E the edge to remove.
   * @exception rpi.goldsd.graph.EdgeNotFoundException if the
   *            edge is not in this graph.
   * @exception rpi.goldsd.graph.VertexNotFoundException if either
   *            of the endpoint vertices of the edge are not in
   *            this graph.
   */
  public synchronized void remove( Edge E )
    throws EdgeNotFoundException, VertexNotFoundException
  {
    if ( ! E.isInGraph( this ) ) throw
      new EdgeNotFoundException( "Edge " + E + " not in graph " + this + "." );

    Vertex startVertex = E.startVertex();
    Vertex endVertex = E.endVertex();

    if ( ! contains( startVertex ) ) throw new
      VertexNotFoundException( "Vertex " + startVertex + " not in graph " + this + "." );
    else if ( ! contains( endVertex ) ) throw new
      VertexNotFoundException( "Vertex " + endVertex + " not in graph " + this + "." );

    edges.remove( E.data() );
    E.setInGraph( null );
    startVertex.removeIncidentEdge( E );

    if ( ! E.isSelfLoop() && ! ( E instanceof DirectedEdge ) )
      endVertex.removeIncidentEdge( E );

    if ( E instanceof DirectedEdge )
      endVertex.removeIncomingEdge( (DirectedEdge)E );
  }


  /**
   * Removes the given vertex from this graph.
   * <p>
   * <b>NOT YET IMPLEMENTED.</b>
   * @param V the vertex to remove.
   */
  public synchronized void remove( Vertex V ) throws VertexNotFoundException
  {
    if ( ! V.isInGraph( this ) ) throw new
      VertexNotFoundException( "Vertex " + V + " not in graph " + this + "." );

    Vertex removed = (Vertex)vertices.remove( V.data() );
    if ( removed != V ) throw
      new InternalGraphError( "Removed vertex does not match argument." );

    V.setInGraph( null );

    
  }


  /** Removes all edges from this graph. */
  public synchronized void removeAllEdges()
  {
    Enumeration e = edges();
    while ( e.hasMoreElements() )
      ((Edge)e.nextElement()).setInGraph( null );

    edges = new Table( edges.getTableSize() );

    e = vertices();
    while ( e.hasMoreElements() )
    {
      Vertex V = (Vertex)e.nextElement();
      V.removeAllIncidentEdges();
      V.removeAllIncomingEdges();
    }
  }
}