Posted By

josepino on 05/26/11


Tagged

graph edge dijkstra vertex grafos nodos vertices


Versions (?)

Operaciones con Grafos - Operating with Graphs


 / Published in: Java
 

  1. ////////////////////////////////////////////////////////////////////////////////////////////////////////////
  2. /*
  3.  * JOSE PINO - SANTIAGO TORTORA
  4.  *
  5.  *
  6.  *
  7.  * 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
  8.  * conexión entre el vértice i y el vértice j y con d(i) el grado del vértice i.
  9.  *
  10.  * Definimos las siguientes operaciones:
  11.  * - borrarArista(i,j): borrar de G la arista (i,j).
  12.  * - borrarAristasIncidentes(i): borrar de G todas las d(i) aristas incidentes en el referido vértice.
  13.  *
  14.  * Implemente ambas funciones en el código fuente de libro de Weiss y mencione un preciso análisis del costo de
  15.  * ejecución de ambos métodos. El código fuente estará disponible en Educa
  16.  *
  17.  * Incluya todos los archivos necesarios para las pruebas de funcionamiento.
  18.  *
  19.  * 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
  20.  *
  21.  */
  22.  
  23.  
  24.  
  25.  
  26.  
  27. ////////////////////////////////////////////////////////////////////////////////////////////////////////////
  28.  
  29.  
  30.  
  31.  
  32.  
  33. import DataStructures.*;
  34. import Supporting.*;
  35. import Exceptions.*;
  36.  
  37. import java.util.StringTokenizer;
  38. import Supporting.Comparable;
  39. import java.io.*;
  40.  
  41. // Graph class interface: evaluate shortest paths
  42. //
  43. // CONSTRUCTION: with no initializer
  44. //
  45. // ******************PUBLIC OPERATIONS**********************
  46. // void addEdges( String source, String dest, int cost )
  47. // --> Add additional edge
  48. // boolean processRequest( BufferedReader in )
  49. // --> Run a bunch of shortest path algs
  50. // ******************ERRORS*********************************
  51. // Some error checking is performed to make sure graph is ok,
  52. // parameters to processRequest represent vertices in the graph,
  53. // and to make sure graph satisfies properties needed by each algorithm
  54.  
  55. /**
  56.  * This class represents the basic
  57.  * item in the adjacency list.
  58.  */
  59. class Edge
  60. {
  61. // First vertex in edge is implicit
  62. public int dest; // Second vertex in edge
  63. public int cost; // Edge cost
  64.  
  65. public Edge( int d, int c )
  66. {
  67. dest = d;
  68. cost = c;
  69. }
  70. }
  71.  
  72.  
  73. /**
  74.  * This class represents the basic item
  75.  * stored for each vertex.
  76.  */
  77. class Vertex
  78. {
  79. String name; // The real name
  80. List adj; // The adjacency list
  81.  
  82. int dist; // Cost (after running algorithm)
  83. int prev; // Previous vertex on shortest path
  84. int scratch; // Extra variable for use in algorithm
  85. int grado; //El grado de entrada del nodo.
  86. Vertex( String nm )
  87. {
  88. name = nm; // Share name in hash table
  89. adj = new LinkedList( ); // Make a new list
  90. }
  91. }
  92.  
  93.  
  94. /**
  95.  * This class represents the basic entry
  96.  * in the vertex dictionary.
  97.  * It implements the Hashable interface by providing
  98.  * hash and equals.
  99.  */
  100. class HashItem implements Hashable
  101. {
  102. public String name; /* The real name */
  103. public int rank; /* The assigned number */
  104.  
  105. public HashItem( )
  106. {
  107. this( null );
  108. }
  109.  
  110. public HashItem( String nm )
  111. {
  112. name = nm;
  113. }
  114.  
  115. public int hash( int tableSize )
  116. {
  117. return ProbingHashTable.hash( name, tableSize );
  118. }
  119.  
  120. public boolean equals( Object rhs )
  121. {
  122. return name.equals( ((HashItem) rhs).name );
  123. }
  124. }
  125.  
  126.  
  127. /**
  128.  * Object stored in the priority queue
  129.  * for Dijkstra's algorithm
  130.  */
  131. class Path implements Comparable
  132. {
  133. int dest; // W
  134. int cost; // D(W)
  135.  
  136. static Path negInf = new Path( ); // Sentinel
  137.  
  138. Path( )
  139. {
  140. this( 0 );
  141. }
  142.  
  143. Path( int d )
  144. {
  145. this( d, 0 );
  146. }
  147.  
  148. Path( int d, int c )
  149. {
  150. dest = d;
  151. cost = c;
  152. }
  153.  
  154. public boolean lessThan( Comparable rhs )
  155. {
  156. return cost < ( (Path) rhs ).cost;
  157. }
  158.  
  159. public int compares( Comparable rhs )
  160. {
  161. return cost < ( (Path) rhs ).cost ? -1 :
  162. cost > ( (Path) rhs ).cost ? 1 : 0;
  163. }
  164. }
  165.  
  166. /**
  167.  * Graph class: evaluate shortest paths.
  168.  */
  169. public class Graph
  170. {
  171. public Graph( )
  172. {
  173. numVertices = 0;
  174. table = new Vertex[ INIT_TABLE_SIZE ];
  175. vertexMap = new QuadraticProbingTable( );
  176. }
  177.  
  178. /**
  179.   * Add the edge ( source, dest, cost ) to the graph.
  180.   */
  181. public void addEdge( String source, String dest, int cost )
  182. {
  183. addInternalEdge( addNode( source ), addNode( dest ), cost );
  184. }
  185.  
  186. /**
  187.   * Process a request; return false if end of file.
  188.   */
  189. public boolean processRequest( BufferedReader in )
  190. {
  191. String sourceName, destName;
  192. HashItem source = new HashItem( );
  193. HashItem dest = new HashItem( );
  194.  
  195. try
  196. {
  197. System.out.println( "Enter start node:" );
  198. if( ( sourceName = in.readLine( ) ) == null )
  199. return false;
  200. System.out.println( "Enter destination node:" );
  201. if( ( destName = in.readLine( ) ) == null )
  202. return false;
  203. }
  204. catch( IOException e )
  205. {
  206. System.out.println( "Error: " + e );
  207. return false;
  208. }
  209.  
  210. try
  211. {
  212. source.name = sourceName;
  213. source = (HashItem) ( vertexMap.find( source ) );
  214. dest.name = destName;
  215. dest = (HashItem) ( vertexMap.find( dest ) );
  216.  
  217. unweighted( source.rank );
  218. printPath( dest.rank );
  219.  
  220. if( dijkstra( source.rank ) )
  221. printPath( dest.rank );
  222. else
  223. System.out.println( "Dijkstra fails - neg edge" );
  224.  
  225. if( dijkstraPair( source.rank ) )
  226. printPath( dest.rank );
  227. else
  228. System.out.println( "Dijkstra fails - neg edge" );
  229.  
  230. if( negative( source.rank ) )
  231. printPath( dest.rank );
  232. else
  233. System.out.println( "Negative fails - neg cycle" );
  234.  
  235. if( acyclic( source.rank ) )
  236. printPath( dest.rank );
  237. else
  238. System.out.println( "Acyclic fails - cycle" );
  239. }
  240. catch( ItemNotFound e )
  241. { System.err.println( "Vertex not in graph" ); }
  242. return true;
  243. }
  244.  
  245.  
  246. /**
  247.   * Metodo para imprimir la est. de datos tabla que se utiliza
  248.   * para representar el grafo.
  249.   * Muestra el nodo de la tabla y sus adyacentes.
  250.   */
  251. public void imprimirGrafoTabla(){
  252. int i = 0;
  253. ListItr theList;
  254. Edge theEdge;
  255.  
  256. System.out.println( "Nodo\tAdyacentes");
  257.  
  258. //Recorremos la tabla mientras que no sea null
  259. while( this.table[ i ] != null ) //Analizamos cada nodo en la tabla
  260. {
  261.  
  262. System.out.print( " " + this.table[ i ].name + " --> "); //Imprimimos el nodo actual
  263.  
  264. //Una vez impreso el nodo actual, tenemos que revisar su lista de adyacencias
  265. theList = new LinkedListItr( this.table[ i ].adj );
  266. theList.first();
  267. theEdge = (Edge)theList.retrieve();
  268. while( theEdge != null )
  269. {
  270. System.out.print( this.table[ theEdge.dest ].name + " "); //Imprimimos
  271. theList.advance(); //Avanzamos la lista
  272.  
  273. theEdge = (Edge)theList.retrieve();
  274. }
  275.  
  276. System.out.print("\n");
  277.  
  278. i++;
  279. }
  280. }
  281.  
  282.  
  283.  
  284.  
  285.  
  286.  
  287.  
  288.  
  289.  
  290.  
  291.  
  292.  
  293.  
  294.  
  295.  
  296.  
  297.  
  298. /**
  299.   * Metodo para borrar una arista de un nodo X a un nodo Y
  300.   * La idea es ir hasta X luego ver si existe Y en la lista de X,
  301.   * si existe ir hasta Y y remover en la lista de Y la ocurrencia de X,
  302.   * por ultimo remover de la lista de X la ocurrencia de Y
  303.   * @param X
  304.   * @param Y
  305.   * Costo:
  306.   * -Encontrar los vertices por sus nombres: O(1) gracias a la tabla hash
  307.   * -Encontrar arista en la lista de adyacencia (2 veces): O(|E|)
  308.   * -Borrar las aristas de las listas de adyacencia: O(1)
  309.   * -Costo total: O(|E|)
  310.   * @throws ItemNotFound
  311.   */
  312.  
  313. private void borrarArista(String X, String Y) throws ItemNotFound{
  314. LinkedListItr AdjX = new LinkedListItr(table[addNode(X)].adj);
  315. AdjX.first();
  316. LinkedListItr AdjY = new LinkedListItr(table[addNode(Y)].adj);
  317. AdjY.first();
  318. for( ;AdjX.isInList(); AdjX.advance() ) {
  319. Edge actual = ((Edge)(AdjX.retrieve()));
  320. if( actual.dest == addNode(Y) ) {
  321. AdjX.remove(actual);
  322. }
  323. }
  324. for( ;AdjY.isInList(); AdjY.advance() ) {
  325. Edge actual = ((Edge)(AdjY.retrieve()));
  326. if( actual.dest == addNode(X) ) {
  327. AdjY.remove(actual);
  328. }
  329. }
  330. }
  331. public void borrarAristaviejo(String X, String Y) throws ItemNotFound{
  332. int i = 0;
  333. int j = 0;
  334. ListItr theListi;
  335. Edge theEdge;
  336. ListItr theListj;
  337. Edge theEdge2;
  338. boolean continuar=true;
  339.  
  340.  
  341.  
  342. //Recorremos la tabla
  343. while( this.table[ i ] != null && !continuar ){ //Analizamos secuencialmente cada nodo en la tabla
  344. if (this.table[i].name.equals(X)) { //Comparamos hasta encontrar X
  345.  
  346. //Una vez encontrado el nodo X, tenemos que revisar su lista de adyacencias e ir hasta Y
  347. theListi = new LinkedListItr( this.table[ i ].adj );
  348. theListi.first();
  349. theEdge = (Edge)theListi.retrieve();
  350. // continuar = true;
  351.  
  352. while( theEdge != null ) { //Recorremos para buscar Y en la lista de X
  353.  
  354. //Buscamos en la lista de X el nodo Y para desconectar
  355. if ( this.table[theEdge.dest].name.equals(Y) ){ //Verificamos si Y figura en la lista de adyacencias de X
  356. theListi.remove(theEdge);
  357. continuar=false;
  358. break;}
  359. else{
  360. theListi.advance();
  361. theEdge = (Edge)theListi.retrieve();}
  362.  
  363.  
  364. }
  365.  
  366. }
  367. i++;
  368. }
  369.  
  370. int posY=findPosEdge(Y);
  371. theListj = new LinkedListItr(table[posY].adj);
  372. theListj.first();
  373. for( ;theListj.retrieve()==null; theListj.advance()){
  374. Edge actual = ((Edge)(theListj.retrieve()));
  375. if( actual.dest == (posY))
  376. theListj.remove(actual);
  377. }
  378. }
  379.  
  380.  
  381. private int findPosEdge(String edgeName){
  382. for(int i=0; i<numVertices; i++){
  383. if(table[i].name.equals(edgeName))
  384. return i;
  385. }
  386. return -1;
  387. }
  388.  
  389.  
  390.  
  391. /**
  392.   * Metodo para borrar las aristas incidentes en un nodo Z
  393.   * @param Z
  394.   * La idea es ir hasta Z en la tabla[], luego ver sus adyacentes
  395.   * primero ir sucesivamente a cada nodo adyacentes en la tabla[] del nodo Z y desconectar en donde figure Z
  396.   * por ultimo eliminar todos los enlaces que figuran en la lista de adyacencia del nodo Z
  397.   * Costo:
  398.   * -Encontrar Z: O(|V|)
  399.   * -Recorrer la lista de adyacencia, por cada elemento recorrer la otra lista de adyacencia, buscar
  400.   * la arista adyacente y eliminar: O(|E|^2)
  401.   * -Costo total: O(|V| + |E|^2)
  402.   * @throws ItemNotFound
  403.   */
  404. /* Z es el nodo que queremos dejar libre, o sea borrar todas sus incidencias
  405.   * J llamamos al nodo adyacente a Z */
  406. public void borrarAristasIncidentes(String Z) throws ItemNotFound {
  407. int i = 0;
  408. int j = 0;
  409. boolean continuar;
  410. ListItr theList;
  411. ListItr theList2;
  412. Edge theEdge;
  413. Edge theEdge2;
  414.  
  415. //Recorremos la tabla
  416. while( this.table[ i ] != null ){ //Analizamos secuencialmente cada nodo en la tabla
  417.  
  418.  
  419. if (this.table[i].name.equals(Z)) { //Comparamos hasta encontrar
  420.  
  421. System.out.println ("Nodo " + Z + " encontrado " + "en indice: " + i);
  422.  
  423. //Una vez encontrado el nodo Z, tenemos que revisar su lista de adyacencias
  424. theList = new LinkedListItr( this.table[ i ].adj );
  425. theList.first();
  426. theEdge = (Edge)theList.retrieve();
  427. while( theEdge != null )
  428. {
  429. System.out.print( this.table[ theEdge.dest ].name + " "); //Imprimimos nombre del adyacente a Z
  430.  
  431. j = 0;
  432. while (this.table[j] != null) {
  433. if (this.table[j].name.equals(this.table[ theEdge.dest ].name)) { //Buscamos la posicion del adyacente a Z
  434.  
  435. System.out.println (" Adyacente encontrado en indice " + j); //j contiene la posicion del adyacente a Z
  436.  
  437.  
  438. //Como el grafo es no dirigido, ahora tenemos que buscar en la posicion del nodo J y eliminar la referencia al nodo Z
  439. //Una vez encontrado el nodo J, tenemos que revisar su lista de adyacencias y desconectar Z
  440. theList2 = new LinkedListItr( this.table[ j ].adj );
  441. theList2.first();
  442. theEdge2 = (Edge)theList2.retrieve();
  443. continuar = true;
  444. while( theEdge2 != null && continuar == true) { //Recorremos la lista del nodo J, la idea es buscar el nodo Z y desconectarlo
  445. //Buscamos en la lista de J el nodo Z para desconectar
  446. 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
  447. continuar = false;
  448. theList2.remove(theEdge2); //Eliminamos Z de la lista de J
  449. }
  450.  
  451.  
  452. theList2.advance(); //Avanzamos la lista
  453. theEdge2 = (Edge)theList2.retrieve();
  454. }
  455.  
  456. }
  457.  
  458. j++;
  459. }
  460.  
  461.  
  462.  
  463. theList.advance(); //Avanzamos la lista
  464.  
  465. theEdge = (Edge)theList.retrieve();
  466. }
  467.  
  468. System.out.print("\n");
  469.  
  470. //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
  471. theList.first(); //Nos colocamos nuevamente en la posicion primera de la lista de Z
  472. theEdge = (Edge)theList.retrieve();
  473. while( theEdge != null ) { //Avanzamos y vamos limpiando la lista de Z
  474. theList.remove(theEdge); //Eliminamos el nodo
  475. theList.advance(); //Avanzamos la lista
  476. theEdge = (Edge)theList.retrieve();
  477. }
  478. }
  479.  
  480.  
  481. i++;
  482.  
  483. }
  484. }
  485.  
  486. private LinkedList findCycle () throws ItemNotFound {
  487. boolean hay_ciclo = false;
  488. LinkedList Cycle = new LinkedList();
  489. for( int i=0; i<this.numVertices && !hay_ciclo; i++ ) {
  490. ListItr adyacentes = new LinkedListItr(table[i].adj);
  491. for( ;adyacentes.isInList(); adyacentes.advance() ) {
  492. this.unweighted(i);
  493. //Si hay un camino entre un vertice adyacente y el propio vertice
  494. if( table[i].dist != INFINITY ) {
  495. //entonces hay un ciclo
  496. hay_ciclo=true;
  497. //System.out.println("Hay un ciclo: ");
  498. pathToList( ((Edge)(adyacentes.retrieve())).dest, Cycle);
  499. LinkedListItr aux = new LinkedListItr(Cycle);
  500. aux.first();
  501. aux.insert( table[((Edge)(adyacentes.retrieve())).dest].name );
  502. break;
  503. }
  504. }
  505. }
  506. return Cycle;
  507. }
  508.  
  509. private LinkedList pathToList(int destino, LinkedList Path) throws ItemNotFound {
  510. Path.makeEmpty();
  511. LinkedListItr Itr = new LinkedListItr(Path);
  512. Itr.zeroth();
  513. int actual = destino;
  514. while( actual!=NULL_VERTEX ) {
  515. Itr.insert(table[actual].name);
  516. actual = table[actual].prev;
  517. }
  518. return Path;
  519. }
  520.  
  521.  
  522.  
  523.  
  524.  
  525.  
  526.  
  527.  
  528.  
  529. /**
  530.   * Main modificado con llamada a los metodos de impresion, borrado de aristas y borrado de incidentes
  531.   * A main routine that:
  532.   * 1. Prompts for a file containing edges;
  533.   * 2. Forms the graph;
  534.   * 3. Repeatedly prompts for two vertices and
  535.   * runs shortest path algorithms.
  536.   * The data file is a sequence of lines of the format
  537.   * source destination cost.
  538.   * @throws ItemNotFound
  539.   */
  540. public static void main( String [ ] args ) throws ItemNotFound
  541. {
  542. System.out.println( "ALGORITMOS Y EST. DE DATOS III - TAREA 7 - GRAFOS" );
  543. System.out.println( "Ingrese la ruta completa y el nombre del archivo graph1.txt:" );
  544. System.out.println( "Ejemplo -> C:\\graph1.txt" );
  545. System.out.println();
  546.  
  547. // Get the file
  548. String fileName= "";
  549.  
  550. try
  551. {
  552. fileName = in.readLine( );
  553. fin = new FileReader( fileName );
  554. }
  555. catch( Exception e )
  556. {
  557. System.err.println( e );
  558. return;
  559. }
  560.  
  561.  
  562. BufferedReader graphFile = new BufferedReader( fin );
  563. Graph g = new Graph( );
  564.  
  565. // Read the edges and insert
  566. try
  567. {
  568. String line;
  569. while( ( line = graphFile.readLine( ) ) != null )
  570. {
  571. StringTokenizer st = new StringTokenizer( line );
  572.  
  573. try
  574. {
  575. if( st.countTokens( ) != 3 )
  576. throw new Exception( );
  577. String source = st.nextToken( );
  578. String dest = st.nextToken( );
  579. int cost = Integer.parseInt( st.nextToken( ) );
  580. g.addEdge( source, dest, cost );
  581. }
  582. catch( Exception e )
  583. { System.err.println( "Error: " + line ); }
  584. }
  585. }
  586. catch( Exception e )
  587. { System.err.println( "Error: " + e ); }
  588.  
  589. /*Llamada original
  590.   while( g.processRequest( in ) )
  591.   ;
  592.   */
  593.  
  594. /////////////////////////////// METODOS AGREGADOS y PRUEBAS //////////////////////////////////
  595. /* OJO: Ya que es un grafo no dirigido, en el archivo donde estan los nodos y sus costos deben estar
  596.   * en ambos sentidos Ejemplo, para un Edge con costo 10 entre A y B:
  597.   * A B 10
  598.   * B A 10
  599.   * Se podria optimizar agregando metodos, pero como WEISS ya implementa este tipo de caso, simplemente
  600.   * modificar como el ejemplo hara que funcione bien para un grafo no dirigido.
  601.   */
  602. System.out.println( "\n---------------------\n" );
  603. System.out.println( "\nEstado de la tabla:\n" );
  604. g.imprimirGrafoTabla(); //Imprimimos el estado actual
  605. System.out.println( "\n---------------------\n" );
  606. LinkedList ciclo = g.findCycle();
  607. LinkedListItr cicloITR = new LinkedListItr(ciclo);
  608. if(ciclo.isEmpty())
  609. System.out.println("El grafo es acíclico");
  610. else{
  611. System.out.println("El grafo tiene un ciclo:");
  612. for( ;cicloITR.isInList(); cicloITR.advance()){
  613. System.out.print( (String)(cicloITR.retrieve()) + " " );
  614. }
  615. System.out.println();
  616. }
  617.  
  618. System.out.println( "\nBorramos la arista A-D a modo de ejemplo:\n" );
  619. g.borrarArista( "A", "D"); //Borramos la arista de A a D
  620.  
  621. System.out.println( "\nEstado de la tabla despues de borrar la arista A-D:\n" );
  622. g.imprimirGrafoTabla(); //Imprimimos el estado actual
  623.  
  624. System.out.println( "\nBorramos las aristas incidentes en un nodo A a modo de ejemplo:\n" );
  625. g.borrarAristasIncidentes( "A" ); //Borramos las aristas incidentes
  626.  
  627. System.out.println( "\nEstado de la tabla despues de los metodos llamados:\n" );
  628. g.imprimirGrafoTabla(); //Imprimimos nuevamente el estado
  629.  
  630. System.out.println( "\nLista de sitios web ordenados segun la cantidad de enlaces que llegan a él:\n" );
  631. g.imprimirOrdenado();
  632. ///////////////////////////////////////////////////////////////////////////////////////////////
  633.  
  634.  
  635.  
  636.  
  637.  
  638.  
  639.  
  640.  
  641.  
  642.  
  643.  
  644.  
  645. }
  646.  
  647. private static final int INIT_TABLE_SIZE = 50;
  648. private static final int NULL_VERTEX = -1;
  649. private static final int INFINITY = 2147483647 / 3;
  650.  
  651. private HashTable vertexMap; // Gets internal #
  652. private Vertex [ ] table; // The table array
  653. private int numVertices; // Current # vertices read
  654.  
  655. /**
  656.   * Double the table array; usual stuff.
  657.   */
  658. private void doubleTableArray( )
  659. {
  660. Vertex[ ] oldArray = table;
  661. table = new Vertex[ oldArray.length * 2 ];
  662. for( int i = 0; i < oldArray.length; i++ )
  663. table[ i ] = oldArray[ i ];
  664. }
  665.  
  666. /**
  667.   * If vertexName is an already seen vertex, return its
  668.   * internal number. Otherwise add it as a new vertex,
  669.   * and return its new internal number.
  670.   */
  671. private int addNode( String vertexName )
  672. {
  673. HashItem hashV = new HashItem( vertexName );
  674. HashItem result;
  675.  
  676. try
  677. {
  678. result = (HashItem) vertexMap.find( hashV );
  679. return result.rank;
  680. }
  681. catch( ItemNotFound e )
  682. {
  683. // Newly seen vertex
  684. hashV.rank = numVertices;
  685. hashV.name = new String( vertexName );
  686. vertexMap.insert( hashV );
  687.  
  688. if( numVertices == table.length )
  689. doubleTableArray( );
  690. table[ numVertices ] = new Vertex( hashV.name );
  691. return numVertices++;
  692. }
  693. }
  694.  
  695. /**
  696.   * Add an edge given internal numbers of its vertices.
  697.   */
  698. private void addInternalEdge( int source, int dest, int cost )
  699. {
  700. ListItr p = new LinkedListItr( table[ source ].adj );
  701. try
  702. { p.insert( new Edge( dest, cost ) );
  703. table[dest].grado ++;}
  704. catch( ItemNotFound e ) { } // Cannot happen
  705. }
  706.  
  707. /**
  708.   * Initialize the table.
  709.   */
  710. private void clearData( )
  711. {
  712. for( int i = 0; i < numVertices; i++ )
  713. {
  714. table[ i ].dist = INFINITY;
  715. table[ i ].prev = NULL_VERTEX;
  716. table[ i ].scratch = 0;
  717. }
  718. }
  719.  
  720. /**
  721.   * Recursively print the shortest path to DestNode
  722.   * (specified by its internal number)
  723.   * printPath is the driver routine
  724.   */
  725. private void printPathRec( int destNode )
  726. {
  727. if( table[ destNode ].prev != NULL_VERTEX )
  728. {
  729. printPathRec( table[ destNode ].prev );
  730. System.out.print( " to " );
  731. }
  732. System.out.print( table[ destNode ].name );
  733. }
  734.  
  735. /**
  736.   * Driver routine to handle unreachables and print total
  737.   * cost. It calls recursive routine to print shortest path
  738.   * to destNode after a shortest path algorithm has run.
  739.   */
  740. private void printPath( int destNode )
  741. {
  742. if( table[ destNode ].dist == INFINITY )
  743. System.out.println( table[ destNode ].name +
  744. " is unreachable" );
  745. else
  746. {
  747. printPathRec( destNode );
  748. System.out.println( " (cost is " +
  749. table[ destNode ].dist + ")" );
  750. }
  751. System.out.println( );
  752. }
  753.  
  754.  
  755. // Various short)est path algorithms that
  756. // require an internal number for start-up
  757.  
  758. /**
  759.   * Compute the unweighted shortest path.
  760.   */
  761. private void unweighted( int startNode )
  762. {
  763. int v, w;
  764. Queue q = new QueueAr( );
  765.  
  766. clearData( );
  767. table[ startNode ].dist = 0;
  768. q.enqueue( new Integer( startNode ) );
  769.  
  770. try
  771. {
  772. while( !q.isEmpty( ) )
  773. {
  774. v = ( (Integer) q.dequeue( ) ).intValue( );
  775. ListItr p = new LinkedListItr( table[ v ].adj );
  776. for( ; p.isInList( ); p.advance( ) )
  777. {
  778. w = ( (Edge) p.retrieve( ) ).dest;
  779. if( table[ w ].dist == INFINITY )
  780. {
  781. table[ w ].dist = table[ v ].dist + 1;
  782. table[ w ].prev = v;
  783. q.enqueue( new Integer( w ) );
  784. }
  785. }
  786. }
  787. }
  788. catch( Underflow e ) { } // Cannot happen
  789. }
  790.  
  791. /**
  792.   * Dijkstra's Algorithm using binary heap.
  793.   * Return false if negative edge detected.
  794.   */
  795. private boolean dijkstra( int startNode )
  796. {
  797. int v, w;
  798. PriorityQueue pq = new BinaryHeap( Path.negInf );
  799. Path vrec;
  800.  
  801. clearData( );
  802. table[ startNode ].dist = 0;
  803. pq.insert( new Path( startNode, 0 ) );
  804.  
  805. try
  806. {
  807. for( int nodesSeen = 0; nodesSeen < numVertices; nodesSeen++ )
  808. {
  809. do
  810. {
  811. if( pq.isEmpty( ) )
  812. return true;
  813. vrec = (Path) pq.deleteMin( );
  814. } while( table[ vrec.dest ].scratch != 0 );
  815.  
  816. v = vrec.dest;
  817. table[ v ].scratch = 1;
  818.  
  819. ListItr p = new LinkedListItr( table[ v ].adj );
  820. for( ; p.isInList( ); p.advance( ) )
  821. {
  822. w = ( (Edge) p.retrieve( ) ).dest;
  823. int cvw = ( (Edge) p.retrieve( ) ).cost;
  824.  
  825. if( cvw < 0 )
  826. return false;
  827.  
  828. if( table[ w ].dist > table[ v ].dist + cvw )
  829. {
  830. table[ w ].dist = table[ v ].dist + cvw;
  831. table[ w ].prev = v;
  832. pq.insert( new Path( w, table[ w ].dist ) );
  833. }
  834. }
  835. }
  836. }
  837. catch( Underflow e ) { } // This cannot happen
  838.  
  839. return true;
  840. }
  841.  
  842. /**
  843.   * Dijkstra's Algorithm using pairing heap
  844.   * Return false if negative edges detected.
  845.   */
  846. private boolean dijkstraPair( int startNode )
  847. {
  848. int v, w;
  849. PairHeap pq = new PairHeap( );
  850. Path vrec;
  851. PairNode [ ] heapPositions = new PairNode[ numVertices ];
  852.  
  853. clearData( );
  854. for( int i = 0; i < numVertices; i++ )
  855. heapPositions[ i ] = null;
  856.  
  857. table[ startNode ].dist = 0;
  858. pq.insert( new Path( startNode, 0 ) );
  859.  
  860. try
  861. {
  862. while( !pq.isEmpty( ) )
  863. {
  864. vrec = (Path) pq.deleteMin( );
  865. v = vrec.dest;
  866.  
  867. ListItr p = new LinkedListItr( table[ v ].adj );
  868. for( ; p.isInList( ); p.advance( ) )
  869. {
  870. w = ( (Edge) p.retrieve( ) ).dest;
  871. int cvw = ( (Edge) p.retrieve( ) ).cost;
  872.  
  873. if( cvw < 0 )
  874. return false;
  875.  
  876. if( table[ w ].dist > table[ v ].dist + cvw )
  877. {
  878. table[ w ].dist = table[ v ].dist + cvw;
  879. table[ w ].prev = v;
  880.  
  881. Path newVal = new Path( w, table[ w ].dist );
  882. if( heapPositions[ w ] == null )
  883. heapPositions[ w ] = pq.addItem( newVal );
  884. else
  885. pq.decreaseKey( heapPositions[ w ], newVal );
  886. }
  887. }
  888. }
  889. }
  890. catch( Exception e ) { } // This cannot happen
  891.  
  892. return true;
  893. }
  894.  
  895. /**
  896.   * Run shortest path algorithm;
  897.   * Negative edge weights are allowed.
  898.   * Return false if negative cycle is detected
  899.   */
  900. private boolean negative( int startNode )
  901. {
  902. int v, w;
  903. Queue q = new QueueAr( );
  904. int cvw;
  905.  
  906. clearData( );
  907. table[ startNode ].dist = 0;
  908. q.enqueue( new Integer( startNode ) );
  909. table[ startNode ].scratch++;
  910.  
  911. try
  912. {
  913. while( !q.isEmpty( ) )
  914. {
  915. v = ( (Integer) q.dequeue( ) ).intValue( );
  916.  
  917. if( table[ v ].scratch++ > 2 * numVertices )
  918. return false;
  919.  
  920. ListItr p = new LinkedListItr( table[ v ].adj );
  921. for( ; p.isInList( ); p.advance( ) )
  922. {
  923. w = ( (Edge) p.retrieve( ) ).dest;
  924. cvw = ( (Edge) p.retrieve( ) ).cost;
  925. if( table[ w ].dist > table[ v ].dist + cvw )
  926. {
  927. table[ w ].dist = table[ v ].dist + cvw;
  928. table[ w ].prev = v;
  929.  
  930. // Enqueue only if not already on queue
  931. if( table[ w ].scratch++ % 2 == 0 )
  932. q.enqueue( new Integer( w ) );
  933. else
  934. table[ w ].scratch++; // In effect, adds 2
  935. }
  936. }
  937. }
  938. }
  939. catch( Underflow e ) { } // Cannot happen
  940.  
  941. return true;
  942. }
  943.  
  944.  
  945. /**
  946.   * Run shortest path algorithm;
  947.   * Linear-time algorithm, works only for acyclic graphs.
  948.   * Return false if cycle is detected
  949.   */
  950. private boolean acyclic( int startNode )
  951. {
  952. int v, w, iterations = 0;
  953. Queue q = new QueueAr( );
  954.  
  955. clearData( );
  956. table[ startNode ].dist = 0;
  957.  
  958. try
  959. {
  960. // Compute the indegrees
  961. for( v = 0; v < numVertices; v++ )
  962. {
  963. ListItr p = new LinkedListItr( table[ v ].adj );
  964. for( ; p.isInList( ); p.advance( ) )
  965. table[ ( (Edge) p.retrieve( ) ).dest ].scratch++;
  966. }
  967.  
  968. // Enqueue vertices of indegree zero
  969. for( v = 0; v < numVertices; v++ )
  970. if( table[ v ].scratch == 0 )
  971. q.enqueue( new Integer( v ) );
  972.  
  973. for( iterations = 0; !q.isEmpty( ); iterations++ )
  974. {
  975. v = ( (Integer) q.dequeue( ) ).intValue( );
  976.  
  977. ListItr p = new LinkedListItr( table[ v ].adj );
  978. for( ; p.isInList( ); p.advance( ) )
  979. {
  980. w = ( (Edge) p.retrieve( ) ).dest;
  981. if( --table[ w ].scratch == 0 )
  982. q.enqueue( new Integer( w ) );
  983.  
  984. if( table[ v ].dist == INFINITY )
  985. continue;
  986.  
  987. int cvw = ( (Edge) p.retrieve( ) ).cost;
  988. if( table[ w ].dist > table[ v ].dist + cvw )
  989. {
  990. table[ w ].dist = table[ v ].dist + cvw;
  991. table[ w ].prev = v;
  992. }
  993. }
  994. }
  995. }
  996. catch( Underflow e ) { } // Cannot happen
  997.  
  998. return iterations == numVertices;
  999. }
  1000. private void imprimirOrdenado (){
  1001. clearData();
  1002. int posMayor;
  1003. int mayor;
  1004. for( int i=0; i<this.numVertices; i++){
  1005. int j;
  1006. for(j=0; j<this.numVertices; j++){
  1007. if( table[j].scratch == 0 ){
  1008. break;
  1009. }
  1010. }
  1011. mayor=table[j].grado;
  1012. posMayor=j;
  1013. for(; j<numVertices; j++) {
  1014. if(table[j].scratch==0 && table[j].grado>mayor ){
  1015. posMayor = j;
  1016. mayor = table[j].grado;
  1017. }
  1018. }
  1019. table[posMayor].scratch = 1;
  1020. System.out.println(table[posMayor].name + "\t" + table[posMayor].grado);
  1021. }
  1022. }
  1023. }

Report this snippet  

You need to login to post a comment.