Revision: 46841
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at May 26, 2011 14:25 by josepino
Initial Code
////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
* 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);
}
}
}
Initial URL
Initial Description
Initial Title
Operaciones con Grafos - Operating with Graphs
Initial Tags
Initial Language
Java