////////////////////////////////////////////////////////////////////////////////////////////////////////////
/* 
 * JOSE PINO - SANTIAGO TORTORA
 * 
 *  
 *
 * Dado un grafo no dirigido G con el conjunto de vértices {0,1,..,V-1} y con E aristas. Denotamos con (i,j) la  
 * conexión entre el vértice i y el vértice j y con d(i) el grado del vértice i. 
 *
 * Definimos las siguientes operaciones: 
 * - borrarArista(i,j): borrar de G la arista (i,j). 
 * - borrarAristasIncidentes(i): borrar de G todas las d(i) aristas incidentes en el referido vértice. 
 *
 * Implemente ambas funciones en el código fuente de libro de Weiss y mencione un preciso análisis del costo de  
 * ejecución de ambos métodos. El código fuente estará disponible en Educa 
 *
 * Incluya todos los archivos necesarios para las pruebas de funcionamiento. 
 * 
 * Para tener una mejor idea de cómo está almacenado el grafo y su diseño       * consultar el libro Algoritmos y Estructuras de Datos en Java, Mark A. Weiss *Pag. 357 Addison Wesley
 * 
 */
 
 
 
 
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
 
 
 
 
import DataStructures.*;
import Supporting.*;
import Exceptions.*;
 
import java.util.StringTokenizer;
import Supporting.Comparable;
import java.io.*;
 
// Graph class interface: evaluate shortest paths
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS**********************
// void addEdges( String source, String dest, int cost )
//                      --> Add additional edge
// boolean processRequest( BufferedReader in )
//                      --> Run a bunch of shortest path algs
// ******************ERRORS*********************************
// Some error checking is performed to make sure graph is ok,
// parameters to processRequest represent vertices in the graph,
// and to make sure graph satisfies properties needed by each algorithm
 
/**
 * This class represents the basic
 * item in the adjacency list.
 */
class Edge
{
                      // First vertex in edge is implicit
    public int dest;  // Second vertex in edge
    public int cost;  // Edge cost
 
    public Edge( int d, int c )
    {
        dest = d;
        cost = c;
    }
}
 
 
/**
 * This class represents the basic item
 * stored for each vertex.
 */
class Vertex
{
    String name;   // The real name
    List   adj;    // The adjacency list
 
    int dist;      // Cost (after running algorithm)
    int prev;      // Previous vertex on shortest path
    int scratch;   // Extra variable for use in algorithm
    int grado;		//El grado de entrada del nodo.
    Vertex( String nm )
    {
        name = nm;                // Share name in hash table
        adj  = new LinkedList( ); // Make a new list
    }
}
 
 
/**
 * This class represents the basic entry
 * in the vertex dictionary.
 * It implements the Hashable interface by providing
 * hash and equals.
 */
class HashItem implements Hashable
{
    public String name;   /* The real name */
    public int    rank;   /* The assigned number */
 
    public HashItem( )
    {
        this( null );
    }
 
    public HashItem( String nm )
    {
        name = nm;
    }
 
    public int hash( int tableSize )
    {
        return ProbingHashTable.hash( name, tableSize );
    }
 
    public boolean equals( Object rhs )
    {
        return name.equals( ((HashItem) rhs).name );
    }
}
 
 
/**
 * Object stored in the priority queue
 * for Dijkstra's algorithm
 */
class Path implements Comparable
{
    int dest;    // W
    int cost;    // D(W)
 
    static Path negInf = new Path( );  // Sentinel
 
    Path( )
    {
        this( 0 );
    }
 
    Path( int d )
    {
        this( d, 0 );
    }
 
    Path( int d, int c )
    {
        dest = d;
        cost = c;
    }
 
    public boolean lessThan( Comparable rhs )
    {
        return cost < ( (Path) rhs ).cost;
    }
 
    public int compares( Comparable rhs )
    {
        return cost < ( (Path) rhs ).cost ? -1 :
               cost > ( (Path) rhs ).cost ? 1 : 0;
    }
}
 
/**
 * Graph class: evaluate shortest paths.
 */
public class Graph
{
    public Graph( )
    {
        numVertices = 0;
        table       = new Vertex[ INIT_TABLE_SIZE ];
        vertexMap   = new QuadraticProbingTable( );
    }
 
    /**
     * Add the edge ( source, dest, cost ) to the graph.
     */
    public void addEdge( String source, String dest, int cost )
    {
        addInternalEdge( addNode( source ), addNode( dest ), cost );
    }
 
    /**
     * Process a request; return false if end of file.
     */
    public boolean processRequest( BufferedReader in )
    {
        String sourceName, destName;
        HashItem source = new HashItem( );
        HashItem dest   = new HashItem( );
 
        try
        {
            System.out.println( "Enter start node:" );
            if( ( sourceName = in.readLine( ) ) == null )
                return false;
            System.out.println( "Enter destination node:" );
            if( ( destName = in.readLine( ) ) == null )
                return false;
        }
        catch( IOException e )
        {
            System.out.println( "Error: " + e  );
            return false;
        }
 
        try
        {
            source.name = sourceName;
            source = (HashItem) ( vertexMap.find( source ) );
            dest.name = destName;
            dest = (HashItem) ( vertexMap.find( dest ) );
 
            unweighted( source.rank );
            printPath( dest.rank );
 
            if( dijkstra( source.rank ) )
                printPath( dest.rank );
            else
                System.out.println( "Dijkstra fails - neg edge" );
 
            if( dijkstraPair( source.rank ) )
                printPath( dest.rank );
            else
                System.out.println( "Dijkstra fails - neg edge" );
 
            if( negative( source.rank ) )
                printPath( dest.rank );
            else
                System.out.println( "Negative fails - neg cycle" );
 
            if( acyclic( source.rank ) )
                printPath( dest.rank );
            else
                System.out.println( "Acyclic fails - cycle" );
        }
        catch( ItemNotFound e )
          { System.err.println( "Vertex not in graph" ); }
        return true;
    }
 
 
    /**
     * Metodo para imprimir la est. de datos tabla que se utiliza
     * para representar el grafo.
     * Muestra el nodo de la tabla y sus adyacentes.
     */
    public void imprimirGrafoTabla(){
    	int i = 0;
    	ListItr theList;
    	Edge theEdge;
 
        System.out.println( "Nodo\tAdyacentes");
 
        //Recorremos la tabla mientras que no sea null
    	while( this.table[ i ] != null )	//Analizamos cada nodo en la tabla
        {
 
             System.out.print( " " +  this.table[ i ].name + "  -->  ");	//Imprimimos el nodo actual
 
             //Una vez impreso el nodo actual, tenemos que revisar su lista de adyacencias
             theList = new LinkedListItr( this.table[ i ].adj );
             theList.first();
             theEdge = (Edge)theList.retrieve();
             while( theEdge != null )
             {
                 System.out.print( this.table[ theEdge.dest ].name + " ");	//Imprimimos
                 theList.advance();											//Avanzamos la lista
 
                 theEdge = (Edge)theList.retrieve();
             }
 
             System.out.print("\n");
 
            i++;
        }
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    /**
     * Metodo para borrar una arista de un nodo X a un nodo Y
     * La idea es ir hasta X luego ver si existe Y en la lista de X, 
     * si existe ir hasta Y y remover en la lista de Y la ocurrencia de X,
     * por ultimo remover de la lista de X la ocurrencia de Y
     * @param X
     * @param Y
     * Costo: 
     * 	-Encontrar los vertices por sus nombres: O(1) gracias a la tabla hash
     *  -Encontrar arista en la lista de adyacencia (2 veces): O(|E|)
     *  -Borrar las aristas de las listas de adyacencia: O(1)
     *  -Costo total: O(|E|)
     * @throws ItemNotFound 
     */
 
    private void borrarArista(String X, String Y) throws ItemNotFound{
    	LinkedListItr AdjX = new LinkedListItr(table[addNode(X)].adj);
    	AdjX.first();
    	LinkedListItr AdjY = new LinkedListItr(table[addNode(Y)].adj);
    	AdjY.first();
    	for( ;AdjX.isInList(); AdjX.advance() ) {
    		Edge actual = ((Edge)(AdjX.retrieve())); 
    		if( actual.dest == addNode(Y) ) {
    			AdjX.remove(actual);
    		}
    	}
    	for( ;AdjY.isInList(); AdjY.advance() ) {
    		Edge actual = ((Edge)(AdjY.retrieve())); 
    		if( actual.dest == addNode(X) ) {
    			AdjY.remove(actual);
    		}
    	}
    }
    public void borrarAristaviejo(String X, String Y) throws ItemNotFound{
      int i = 0;
      int j = 0;
      ListItr theListi;
      Edge theEdge;
      ListItr theListj;
      Edge theEdge2;
      boolean continuar=true;
 
 
 
    	//Recorremos la tabla
    	while( this.table[ i ] != null && !continuar ){	//Analizamos secuencialmente cada nodo en la tabla 
    		if (this.table[i].name.equals(X)) {			//Comparamos hasta encontrar X
 
    			//Una vez encontrado el nodo X, tenemos que revisar su lista de adyacencias e ir hasta Y
                theListi = new LinkedListItr( this.table[ i ].adj );
                theListi.first();
                theEdge = (Edge)theListi.retrieve();
  //              continuar = true;
 
                while( theEdge != null ) { 	//Recorremos para buscar Y en la lista de X
 
                	//Buscamos en la lista de X el nodo Y para desconectar
                	if ( this.table[theEdge.dest].name.equals(Y) ){	//Verificamos si Y figura en la lista de adyacencias de X
                		theListi.remove(theEdge);
                		continuar=false;
                		break;}
                	else{
                		theListi.advance();
                		theEdge = (Edge)theListi.retrieve();}
 
 
                }
 
    		}
    		i++;
    	}
 
                int posY=findPosEdge(Y);
                theListj = new LinkedListItr(table[posY].adj);
                theListj.first();
                for( ;theListj.retrieve()==null; theListj.advance()){
                	Edge actual = ((Edge)(theListj.retrieve()));
                	if(  actual.dest == (posY)) 
                		theListj.remove(actual);               	
                }
    }
 
 
    private int findPosEdge(String edgeName){
    	for(int i=0; i<numVertices; i++){
    		if(table[i].name.equals(edgeName))
    			return i;
    	}
    	return -1;
    }
 
 
 
    /**
     * Metodo para borrar las aristas incidentes en un nodo Z
     * @param Z
     * La idea es ir hasta Z en la tabla[], luego ver sus adyacentes
     * primero ir sucesivamente a cada nodo adyacentes en la tabla[] del nodo Z y desconectar en donde figure Z
     * por ultimo eliminar todos los enlaces que figuran en la lista de adyacencia del nodo Z
     * Costo:
     * 	-Encontrar Z: O(|V|)
     *  -Recorrer la lista de adyacencia, por cada elemento recorrer la otra lista de adyacencia, buscar
     * la arista adyacente y eliminar: O(|E|^2)
     * 	-Costo total: O(|V| + |E|^2)
     * @throws ItemNotFound 
     */
    /* Z es el nodo que queremos dejar libre, o sea borrar todas sus incidencias
     * J llamamos al nodo adyacente a Z */
    public void borrarAristasIncidentes(String Z) throws ItemNotFound {  
    	int i = 0; 
    	int j = 0;
    	boolean continuar;
    	ListItr theList;
    	ListItr theList2;
    	Edge theEdge;
    	Edge theEdge2;
 
    	//Recorremos la tabla
    	while( this.table[ i ] != null ){	//Analizamos secuencialmente cada nodo en la tabla 
 
 
    		if (this.table[i].name.equals(Z)) {			//Comparamos hasta encontrar
 
    			System.out.println ("Nodo " + Z + " encontrado " + "en indice: " + i);
 
    			//Una vez encontrado el nodo Z, tenemos que revisar su lista de adyacencias
                theList = new LinkedListItr( this.table[ i ].adj );
                theList.first();
                theEdge = (Edge)theList.retrieve();
                while( theEdge != null )
                {
                    System.out.print( this.table[ theEdge.dest ].name + " ");	//Imprimimos nombre del adyacente a Z 
 
                    j = 0;
                    while (this.table[j] != null) {
                      if (this.table[j].name.equals(this.table[ theEdge.dest ].name)) {  //Buscamos la posicion del adyacente a Z
 
                    	System.out.println (" Adyacente encontrado en indice " + j);		//j contiene la posicion del adyacente a Z
 
 
                    	//Como el grafo es no dirigido, ahora tenemos que buscar en la posicion del nodo J y eliminar la referencia al nodo Z
                    	//Una vez encontrado el nodo J, tenemos que revisar su lista de adyacencias y desconectar Z
                        theList2 = new LinkedListItr( this.table[ j ].adj );
                        theList2.first();
                        theEdge2 = (Edge)theList2.retrieve();
                        continuar = true;
                        while( theEdge2 != null  && continuar == true) { //Recorremos la lista del nodo J, la idea es buscar el nodo Z y desconectarlo
                        	//Buscamos en la lista de J el nodo Z para desconectar
                        	if ( this.table[i].name.equals(this.table[theEdge2.dest].name) ){	//Si Z figura en la lista de adyacencias de J eliminamos la referencia a Z
                        		continuar = false;
                        		theList2.remove(theEdge2);			//Eliminamos Z de la lista de J
                        	}
 
 
                        	theList2.advance();											//Avanzamos la lista
                            theEdge2 = (Edge)theList2.retrieve();
                        }
 
                      }
 
                      j++;
                    }
 
 
 
                    theList.advance();											//Avanzamos la lista
 
                    theEdge = (Edge)theList.retrieve();
                }
 
                System.out.print("\n");
 
                //Una vez que se ha desconectado todos los nodos que apuntaban a Z, ahora limpiar la lista de Z para que Z apunte a ninguno 
                theList.first();  //Nos colocamos nuevamente en la posicion primera de la lista de Z
                theEdge = (Edge)theList.retrieve();
                while( theEdge != null ) {				//Avanzamos y vamos limpiando la lista de Z
                	theList.remove(theEdge);			//Eliminamos el nodo
                	theList.advance();					//Avanzamos la lista
                    theEdge = (Edge)theList.retrieve();
                }
    		}
 
 
    		i++;
 
    	}
    }
 
    private LinkedList findCycle () throws ItemNotFound {
        boolean hay_ciclo = false;
        LinkedList Cycle = new LinkedList();
        for( int i=0; i<this.numVertices && !hay_ciclo; i++ ) {
            ListItr adyacentes = new LinkedListItr(table[i].adj);
            for( ;adyacentes.isInList(); adyacentes.advance() ) {
                this.unweighted(i);
                //Si hay un camino entre un vertice adyacente y el propio vertice
                if( table[i].dist != INFINITY ) {
                    //entonces hay un ciclo
                    hay_ciclo=true;
                    //System.out.println("Hay un ciclo: ");
                    pathToList( ((Edge)(adyacentes.retrieve())).dest, Cycle);
                    LinkedListItr aux = new LinkedListItr(Cycle);
                    aux.first();
                    aux.insert( table[((Edge)(adyacentes.retrieve())).dest].name );
                    break;
                }
            }
        }
        return Cycle;
    }
 
    private LinkedList pathToList(int destino, LinkedList Path) throws ItemNotFound {
    	Path.makeEmpty();
    	LinkedListItr Itr = new LinkedListItr(Path);
    	Itr.zeroth();
    	int actual = destino;
    	while( actual!=NULL_VERTEX ) {
    		Itr.insert(table[actual].name);
    		actual = table[actual].prev;
    	}
    	return Path;
    }
 
 
 
 
 
 
 
 
 
    /**
     * Main modificado con llamada a los metodos de impresion, borrado de aristas y borrado de incidentes
     * A main routine that:
     * 1. Prompts for a file containing edges;
     * 2. Forms the graph;
     * 3. Repeatedly prompts for two vertices and
     *    runs shortest path algorithms.
     * The data file is a sequence of lines of the format
     *    source destination cost.
     * @throws ItemNotFound 
     */
    public static void main( String [ ] args ) throws ItemNotFound
    {
    	System.out.println( "ALGORITMOS Y EST. DE DATOS III - TAREA 7 - GRAFOS" );
        System.out.println( "Ingrese la ruta completa y el nombre del archivo graph1.txt:" );
        System.out.println( "Ejemplo -> C:\\graph1.txt" );
        System.out.println();
 
        // Get the file
        BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) );
        FileReader fin;
        String fileName= "";
 
        try
        {
            fileName = in.readLine( );
            fin = new FileReader( fileName );
        }
        catch( Exception e )
        {
            System.err.println( e );
            return;
        }
 
 
        BufferedReader graphFile = new BufferedReader( fin );
        Graph g = new Graph( );
 
            // Read the edges and insert
        try
        {
            String line;
            while( ( line = graphFile.readLine( ) ) != null )
            {
                StringTokenizer st = new StringTokenizer( line );
 
                try
                {
                    if( st.countTokens( ) != 3 )
                        throw new Exception( );
                    String source  = st.nextToken( );
                    String dest    = st.nextToken( );
                    int cost = Integer.parseInt( st.nextToken( ) );
                    g.addEdge( source, dest, cost );
                }
                catch( Exception e )
                  { System.err.println( "Error: " + line ); }
             }
         }
         catch( Exception e )
           { System.err.println( "Error: " + e ); }
 
         /*Llamada original 
         while( g.processRequest( in ) )
             ;
          */
 
         /////////////////////////////// METODOS AGREGADOS y PRUEBAS //////////////////////////////////
         /* OJO: Ya que es un grafo no dirigido, en el archivo donde estan los nodos y sus costos deben estar
          * en ambos sentidos Ejemplo, para un Edge con costo 10 entre A y B:
          * A B 10
          * B A 10
          * Se podria optimizar agregando metodos, pero como WEISS ya implementa este tipo de caso, simplemente
          * modificar como el ejemplo hara que funcione bien para un grafo no dirigido.
          */
         System.out.println( "\n---------------------\n" );
         System.out.println( "\nEstado de la tabla:\n" );
         g.imprimirGrafoTabla();					//Imprimimos el estado actual
         System.out.println( "\n---------------------\n" );
         LinkedList ciclo = g.findCycle();
         LinkedListItr cicloITR = new LinkedListItr(ciclo);
         if(ciclo.isEmpty())
        	 System.out.println("El grafo es acíclico");
         else{
        	 System.out.println("El grafo tiene un ciclo:");        	 
	         for( ;cicloITR.isInList(); cicloITR.advance()){
	        	 System.out.print( (String)(cicloITR.retrieve()) + " " );
	         }
	         System.out.println();
         } 
 
         System.out.println( "\nBorramos la arista A-D a modo de ejemplo:\n" );
         g.borrarArista( "A", "D");					//Borramos la arista de A a D
 
         System.out.println( "\nEstado de la tabla despues de borrar la arista A-D:\n" );
         g.imprimirGrafoTabla();					//Imprimimos el estado actual
 
         System.out.println( "\nBorramos las aristas incidentes en un nodo A a modo de ejemplo:\n" );
         g.borrarAristasIncidentes( "A" );			//Borramos las aristas incidentes 
 
         System.out.println( "\nEstado de la tabla despues de los metodos llamados:\n" );
         g.imprimirGrafoTabla();					//Imprimimos nuevamente el estado
 
         System.out.println( "\nLista de sitios web ordenados segun la cantidad de enlaces que llegan a él:\n" );
         g.imprimirOrdenado();
         ///////////////////////////////////////////////////////////////////////////////////////////////
 
 
 
 
 
 
 
 
 
 
 
 
    }
 
    private static final int INIT_TABLE_SIZE = 50;
    private static final int NULL_VERTEX     = -1;
    private static final int INFINITY        = 2147483647 / 3;
 
    private HashTable vertexMap;    // Gets internal #
    private Vertex [ ] table;       // The table array
    private int       numVertices;  // Current # vertices read
 
    /**
     * Double the table array; usual stuff.
     */
    private void doubleTableArray( )
    {
        Vertex[ ] oldArray = table;
        table = new Vertex[ oldArray.length * 2 ];
        for( int i = 0; i < oldArray.length; i++ )
            table[ i ] = oldArray[ i ];
    }
 
    /**
     * If vertexName is an already seen vertex, return its
     * internal number. Otherwise add it as a new vertex,
     * and return its new internal number.
     */
    private int addNode( String vertexName )
    {
        HashItem hashV = new HashItem( vertexName );
        HashItem result;
 
        try
        {
            result = (HashItem) vertexMap.find( hashV );
            return result.rank;
        }
        catch( ItemNotFound e )
        {
            // Newly seen vertex
            hashV.rank = numVertices;
            hashV.name = new String( vertexName );
            vertexMap.insert( hashV );
 
            if( numVertices == table.length )
                doubleTableArray( );
            table[ numVertices ] = new Vertex( hashV.name );
            return numVertices++;
        }
    }
 
    /**
     * Add an edge given internal numbers of its vertices.
     */
    private void addInternalEdge( int source, int dest, int cost )
    {
        ListItr p = new LinkedListItr( table[ source ].adj );
        try
          { p.insert( new Edge( dest, cost ) );
          	table[dest].grado ++;}
        catch( ItemNotFound e ) { }   // Cannot happen
    }
 
    /**
     * Initialize the table.
     */
    private void clearData( )
    {
        for( int i = 0; i < numVertices; i++ )
        {
            table[ i ].dist = INFINITY;
            table[ i ].prev = NULL_VERTEX;
            table[ i ].scratch = 0;
        }
    }
 
    /**
     * Recursively print the shortest path to DestNode
     * (specified by its internal number)
     * printPath is the driver routine
     */
    private void printPathRec( int destNode )
    {
        if( table[ destNode ].prev != NULL_VERTEX )
        {
            printPathRec( table[ destNode ].prev );
            System.out.print( " to " );
        }
        System.out.print( table[ destNode ].name );
    }
 
    /**
     * Driver routine to handle unreachables and print total
     * cost. It calls recursive routine to print shortest path
     * to destNode after a shortest path algorithm has run.
     */
    private void printPath( int destNode )
    {
        if( table[ destNode ].dist == INFINITY )
            System.out.println( table[ destNode ].name +
                                " is unreachable" );
        else
        {
            printPathRec( destNode );
            System.out.println( " (cost is " +
                                table[ destNode ].dist + ")" );
        }
        System.out.println( );
    }
 
 
        // Various short)est path algorithms that
        // require an internal number for start-up
 
    /**
     * Compute the unweighted shortest path.
     */
    private void unweighted( int startNode )
    {
        int v, w;
        Queue q = new QueueAr( );
 
        clearData( );
        table[ startNode ].dist = 0;
        q.enqueue( new Integer( startNode ) );
 
        try
        {
            while( !q.isEmpty( ) )
            {
                v = ( (Integer) q.dequeue( ) ).intValue( );
                ListItr p = new LinkedListItr( table[ v ].adj );
                for( ; p.isInList( ); p.advance( ) )
                {
                    w = ( (Edge) p.retrieve( ) ).dest;
                    if( table[ w ].dist == INFINITY )
                    {
                        table[ w ].dist = table[ v ].dist + 1;
                        table[ w ].prev = v;
                        q.enqueue( new Integer( w ) );
                    }
                }
            }
        }
        catch( Underflow e ) { }   // Cannot happen
    }
 
    /**
     * Dijkstra's Algorithm using binary heap.
     * Return false if negative edge detected.
     */
    private boolean dijkstra( int startNode )
    {
        int v, w;
        PriorityQueue pq = new BinaryHeap( Path.negInf );
        Path vrec;
 
        clearData( );
        table[ startNode ].dist = 0;
        pq.insert( new Path( startNode, 0 ) );
 
        try
        {
            for( int nodesSeen = 0; nodesSeen < numVertices; nodesSeen++ )
            {
                do
                {
                    if( pq.isEmpty( ) )
                        return true;
                    vrec = (Path) pq.deleteMin( );
                } while( table[ vrec.dest ].scratch != 0 );
 
                v = vrec.dest;
                table[ v ].scratch = 1;
 
                ListItr p = new LinkedListItr( table[ v ].adj );
                for( ; p.isInList( ); p.advance( ) )
                {
                    w = ( (Edge) p.retrieve( ) ).dest;
                    int cvw = ( (Edge) p.retrieve( ) ).cost;
 
                    if( cvw < 0 )
                        return false;
 
                    if( table[ w ].dist > table[ v ].dist + cvw )
                    {
                        table[ w ].dist = table[ v ].dist + cvw;
                        table[ w ].prev = v;
                        pq.insert( new Path( w, table[ w ].dist ) );
                    }
                }
            }
        }
        catch( Underflow e ) { }   // This cannot happen
 
        return true;
    }
 
    /**
     * Dijkstra's Algorithm using pairing heap
     * Return false if negative edges detected.
     */
    private boolean dijkstraPair( int startNode )
    {
        int v, w;
        PairHeap pq = new PairHeap( );
        Path vrec;
        PairNode [ ] heapPositions = new PairNode[ numVertices ];
 
        clearData( );
        for( int i = 0; i < numVertices; i++ )
            heapPositions[ i ] = null;
 
        table[ startNode ].dist = 0;
        pq.insert( new Path( startNode, 0 ) );
 
        try
        {
            while( !pq.isEmpty( ) )
            {
                vrec = (Path) pq.deleteMin( );
                v = vrec.dest;
 
                ListItr p = new LinkedListItr( table[ v ].adj );
                for( ; p.isInList( ); p.advance( ) )
                {
                    w = ( (Edge) p.retrieve( ) ).dest;
                    int cvw = ( (Edge) p.retrieve( ) ).cost;
 
                    if( cvw < 0 )
                        return false;
 
                    if( table[ w ].dist > table[ v ].dist + cvw )
                    {
                        table[ w ].dist = table[ v ].dist + cvw;
                        table[ w ].prev = v;
 
                        Path newVal = new Path( w, table[ w ].dist );
                        if( heapPositions[ w ] == null )
                            heapPositions[ w ] = pq.addItem( newVal );
                        else
                            pq.decreaseKey( heapPositions[ w ], newVal );
                    }
                }
            }
        }
        catch( Exception e ) { }   // This cannot happen 
 
        return true;
    }
 
    /**
     * Run shortest path algorithm;
     * Negative edge weights are allowed.
     * Return false if negative cycle is detected
     */
    private boolean negative( int startNode )
    {
        int v, w;
        Queue q = new QueueAr( );
        int cvw;
 
        clearData( );
        table[ startNode ].dist = 0;
        q.enqueue( new Integer( startNode ) );
        table[ startNode ].scratch++;
 
        try
        {
            while( !q.isEmpty( ) )
            {
                v = ( (Integer) q.dequeue( ) ).intValue( );
 
                if( table[ v ].scratch++ > 2 * numVertices )
                    return false;
 
                ListItr p = new LinkedListItr( table[ v ].adj );
                for( ; p.isInList( ); p.advance( ) )
                {
                    w = ( (Edge) p.retrieve( ) ).dest;
                    cvw = ( (Edge) p.retrieve( ) ).cost;
                    if( table[ w ].dist > table[ v ].dist + cvw )
                    {
                        table[ w ].dist = table[ v ].dist + cvw;
                        table[ w ].prev = v;
 
                        // Enqueue only if not already on queue
                        if( table[ w ].scratch++ % 2 == 0 )
                            q.enqueue( new Integer( w ) );
                        else
                            table[ w ].scratch++;  // In effect, adds 2
                    }
                }
            }
        }
        catch( Underflow e ) { }   // Cannot happen
 
        return true;
    }
 
 
    /**
     * Run shortest path algorithm;
     * Linear-time algorithm, works only for acyclic graphs.
     * Return false if cycle is detected
     */
    private boolean acyclic( int startNode )
    {
        int v, w, iterations = 0;
        Queue q = new QueueAr( );
 
        clearData( );
        table[ startNode ].dist = 0;
 
        try
        {
            // Compute the indegrees
            for( v = 0; v < numVertices; v++ )
            {
                ListItr p = new LinkedListItr( table[ v ].adj );
                for( ; p.isInList( ); p.advance( ) )
                    table[ ( (Edge) p.retrieve( ) ).dest ].scratch++;
            }
 
            // Enqueue vertices of indegree zero
            for( v = 0; v < numVertices; v++ )
                if( table[ v ].scratch == 0 )
                    q.enqueue( new Integer( v ) );
 
            for( iterations = 0; !q.isEmpty( ); iterations++ )
            {
                v = ( (Integer) q.dequeue( ) ).intValue( );
 
                ListItr p = new LinkedListItr( table[ v ].adj );
                for( ; p.isInList( ); p.advance( ) )
                {
                    w = ( (Edge) p.retrieve( ) ).dest;
                    if( --table[ w ].scratch == 0 )
                        q.enqueue( new Integer( w ) );
 
                    if( table[ v ].dist == INFINITY )
                        continue;
 
                    int cvw = ( (Edge) p.retrieve( ) ).cost;
                    if( table[ w ].dist > table[ v ].dist + cvw )
                    {
                        table[ w ].dist = table[ v ].dist + cvw;
                        table[ w ].prev = v;
                    }
                }
            }
        }
        catch( Underflow e ) { }    // Cannot happen
 
        return iterations == numVertices;
    }
    private void imprimirOrdenado (){
    	clearData();
    	int posMayor;
    	int mayor;
    	for( int i=0; i<this.numVertices; i++){
    		int j;
    		for(j=0; j<this.numVertices; j++){
    			if( table[j].scratch == 0 ){
    				break;
    			}
    		}
    		mayor=table[j].grado;
    		posMayor=j;
    		for(; j<numVertices; j++) {
    			if(table[j].scratch==0 && table[j].grado>mayor ){
    				posMayor = j;
    				mayor = table[j].grado;
    			}
    		}
    		table[posMayor].scratch = 1;
    		System.out.println(table[posMayor].name + "\t" + table[posMayor].grado);
    	}
    }
}