Grafos

Solo disponible en BuenasTareas
  • Páginas : 6 (1264 palabras )
  • Descarga(s) : 0
  • Publicado : 17 de mayo de 2011
Leer documento completo
Vista previa del texto
package grafos;

import java.util.*;
import java.io.*;

/**
* Grafo.java
* Un elemento de esta clase corresponde a un grafo representado
* en su Matriz de adyacencia
*
* @author Diana Cardona
* @author Alejandro Saldarriaga
* @version 1.0 24/05/2008
*/
public class Grafo{
/**
* Matriz que representa el grafo.
*/
int[][] matriz;

/**
* Matriz de costos para viajarentre los vértices del grafo;
* Las filas indican la cola del grafo, y las columnas la cabeza.
*/
int[][] costo;

/**
* Objeto que controla la creación de números aleatorios para
* asignar los costos de viaje entre vértices del grafo.
*/
Random r = new Random();

/**
* Booleano que indica si el grafo es dirigido o no.
*/
boolean dirigido = true;

/**
* Número querepresentará el valor infinito del grafo
*/
static int INFINITO = 999999999;
/**
* Crea un nuevo grafo sin lados con el número de vértices
* recibido.
* @param nroVert Número de vértices que tendrá el grafo.
*/
public Grafo(int nroVert){
if (nroVert > 0){
this.dirigido = false;
matriz = new int[nroVert][nroVert];
costo = new int[nroVert][nroVert];
resetCosto();
}}

/**
* Crea un nuevo grafo con un número de vértices aleatorio entre 4 y 8
* y un número aleatorio de lados.
*/
public Grafo(){
int nVert = Math.abs(r.nextInt()%16);
if (nVert < 4){
nVert = nVert + 4;
}
matriz = new int[nVert][nVert];
costo = new int[nVert][nVert];
resetCosto();

int lados = Math.abs(r.nextInt()% (nVert*(nVert - 1) + 1));
//if(!dirigido){
// lados = lados /2;
//}
dirigido = false;
lados = lados/2;

int i = 0;
while (i < lados){
int co = Math.abs(r.nextInt()% nVert);
int ca = Math.abs(r.nextInt()% nVert);
if (!contiene(co,ca)){ // si el lado aún no está en el grafo
if (conecta(co, ca)){
i = i+1;
}
}
}
}

/**
* Crea un nuevo grafo con el número de vértices y ladosespecificado.
* @param nVert El número de vértices que tendrá el grafo.
* @param lados El número de lados que tendrá el grafo.
*/
public Grafo(int nVert, int lados, boolean dirigido){
this.dirigido = dirigido;
if (nVert < 4){
nVert = nVert + 4;
}
matriz = new int[nVert][nVert];
costo = new int[nVert][nVert];
resetCosto();

int maxLados = nVert*(nVert - 1);
if(!dirigido) {
maxLados = maxLados/2;
}
if (lados >= maxLados){
//lados = maxLados;
for(int i=0; in){
dim = 8;
}
}catch (Exception exc){
//quedará una dimensión de 8 por defecto si se produjo una excepción
}
this.matriz = new int[dim][dim];
this.costo = new int[dim][dim];
this.resetCosto();

int i = 0;
int j = 0;
int numero = 0;while ((n != -1)&&(i < matriz.length)) {
if ((n != 13)&&(n != 10)) { //si no es un retorno de carro o fin de línea,
if (i == j){
n = 48; // en la diagonal deben haber 0, independiente del valor de la matriz
}
if (n!=48){ //48 es el valor en ascii para 0, si el número es 1 u otro, se coloca la arista
conecta(i,j);
}
j++;
if (j == matriz.length){j = 0;
i++;
}
}
n = fis.read();
}

fis.close();

opere.muestraMatriz(this.matriz, "La matriz de conexiones es:");

System.out.println("\nLa matriz de costos es:");
System.out.println(this.toString());

}

/**
* Recibe el nomdre de un archivo de texto, y crea un grafo a partir de él;
* lee los diferentes números de peso del grafodistinguiendo uno de otro al
* estar separados por espacios.
* @param nombreArch El archivo a leer.
* @param pesos Si es verdadero tiene en cuenta el peso indicado, si es falso
* simplemente asigna un peso aleatorio a la arista.
*/
public Grafo(String nombreArch, boolean pesos) throws FileNotFoundException, IOException {
FileInputStream fis = new...
tracking img