grafo.java

Easy implementation of PRIM and DIJKSTRA algorims for graph sorting. It also permit comparison of ti

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.util.LinkedList;
import java.util.Random;
import java.util.Scanner;

public abstract class Grafo implements Cloneable {
  protected boolean Dirigido;
  public    int     NumVertices;
  public    int     NumAristas;
  private   int     PosiblesAristas[][] = null;
  private   int     AristasColumna[]    = null;
  private   Random  Rand                = new Random();
  
  public static int VerticesArchivo(String File) {
  	try {
			Scanner sc = new Scanner(new FileInputStream(File));
			return sc.nextInt();
		} catch (FileNotFoundException e) {}
		return 0;
  }
  
  public void LoadFromFile(String File) {
		try {
			Scanner sc = new Scanner(new FileInputStream(File));

			sc.nextInt();
			sc.nextInt();
			sc.nextBoolean();

			for(int i = 0; i < NumAristas; i++) {
				int v1   = sc.nextInt();
				int v2   = sc.nextInt();
				int peso = sc.nextInt();

				InsertarArista(v1, v2, peso);
				if(Dirigido) InsertarArista(v2, v1, peso);
			}
		} catch (FileNotFoundException e) {}
  }
  
  public void SaveToFile(String File) {
		try {
			FileOutputStream oe = new FileOutputStream(File);
			oe.write(new String(NumVertices + "\t" + NumAristas + "\t" + ((Dirigido) ? "true" : "false") + "\r\n").getBytes());

			for(int i = 0; i < NumVertices; i++) {
				for(int v = 0; v < NumVertices; v++) {
					Arista a = ObtenerArista(i, v);
					if(a == null) continue;
					oe.write(new String(a.vertex1 + "\t" + a.vertex2 + "\t" + a.weight + "\r\n").getBytes());
				}
			}
		} catch(Exception e) {}
  }

  private void IniciarPosiblesAristas() {
    if(PosiblesAristas == null) {
    	PosiblesAristas = new int[NumVertices][NumVertices];
    	AristasColumna  = new int[NumVertices];
    	for(int a = 0; a < NumVertices; a++) {
    		for(int b = 0; b < NumVertices; b++) {
      		PosiblesAristas[a][b] = Rand.nextInt(1000) + 1; 
    		}
    		AristasColumna[a] = NumVertices;
    	}
    }	
  }
  
  private void IniciarGrafoConexo() {
  	if(NumAristas == 0) {
  		for(int n = 0; n < NumVertices - 1; n++) {
  			int Peso = Rand.nextInt(1000) + 1;
  			InsertarArista(n, n + 1, Peso);
  		}
  	}
  }
  
  private int ObtenerColumnaConAristas() {
    int Columna = Rand.nextInt(NumVertices);
    for(int c = 0; c < NumVertices; c++) {
		  if(AristasColumna[Columna] > 0) return Columna;
      Columna = (Columna + 1) % NumVertices;
    }
    return -1;
  }
  
  private int ObtenerFila(int Columna) {
    int Fila = Rand.nextInt(NumVertices);
    for(int c = 0; c < NumVertices; c++) {
		  if(PosiblesAristas[Columna][Fila] > 0) return Fila;
      Fila = (Fila + 1) % NumVertices;
    }
    return -1;
  }
  
  public void GenerateRandom(int aristas) {
   	IniciarGrafoConexo();
  	IniciarPosiblesAristas();
    
  	while(NumAristas < aristas) {
    	int Columna = ObtenerColumnaConAristas();
    	int Fila    = ObtenerFila(Columna);
    	int Peso    = PosiblesAristas[Columna][Fila];
    	PosiblesAristas[Columna][Fila] = 0;
    	AristasColumna[Columna]--;
  		InsertarArista(Columna, Fila, Peso);
  	}
  }
  
  public Grafo(boolean dirigido) {
  	Dirigido    = dirigido;
    NumVertices = 0;
    NumAristas  = 0;
  }
  public abstract Arista  ObtenerArista(int Vertice, int NumArista);
	public abstract void    InsertarArista(int origen, int destino, int peso);
	public abstract void    ActualizarPeso(int origen, int destino, int peso);
	public abstract boolean EstaConectado(int origen, int destino);
}

class GrafoMatriz extends Grafo implements Cloneable {
  private int Matriz[][];
  
	public void ActualizarPeso(int origen, int destino, int peso) {
    Matriz[origen][destino] = peso;
	}
  
  public Arista ObtenerArista(int origen, int indice) {
  	if(origen == indice) return new Arista(origen, indice, 0);
		if(!EstaConectado(origen, indice)) return null;
  	return new Arista(origen, indice, ObtenerPeso(origen, indice));
	}
	
  public GrafoMatriz(int vertices, boolean dirigido) {
  	super(dirigido);
    NumVertices = vertices;
  	Matriz = new int[vertices][vertices];
  	for(int n = 0; n < vertices; n++)
  		for(int m = 0; m < vertices; m++)
  			Matriz[n][m] = (n == m) ? 0 : Integer.MAX_VALUE;
  }

	public boolean EstaConectado(int origen, int destino) {
		if(origen == destino) return true;
		return (Matriz[origen][destino] == Integer.MAX_VALUE) ? false : true;
	}

	public void InsertarArista(int origen, int destino, int peso) {
		if(origen == destino) return;
		if(EstaConectado(origen, destino)) return;
		Matriz[origen][destino] = peso;
		if(!Dirigido) Matriz[destino][origen] = peso;
		NumAristas++;
	}

	public int ObtenerPeso(int origen, int destino) {
		return Matriz[origen][destino];
	}
	
	public int ObtenerNumeroVertices() {
		return Matriz[0].length;
	}
}

@SuppressWarnings("unchecked")
class GrafoLista extends Grafo implements Cloneable {
	class Vertex {
		int  Num;
		int  Peso;
	}
  private LinkedList Lista[];
  
	public void ActualizarPeso(int origen, int destino, int peso) {
		if(!EstaConectado(origen, destino)) {
			if(origen == destino) return;
			Vertex Vertice = new Vertex();
			Vertice.Num = destino;
			Vertice.Peso = peso;
			Lista[origen].add(Vertice);
	  } else {
	    for(int n = 0; n < Lista[origen].size(); n++) {
	    	Vertex Vertice = (Vertex)Lista[origen].get(n);
	    	if(Vertice.Num == destino) Vertice.Peso = peso;
	    }
	  }
	}

	public Arista ObtenerArista(int origen, int index) {
		if(origen == index) return new Arista(origen, index, 0);
    for(int n = 0; n < Lista[origen].size(); n++) {
    	Vertex Vertice = (Vertex)Lista[origen].get(n);
    	if(Vertice.Num == index) return new Arista(origen, index, Vertice.Peso);
    }
		return null;
	}
	
	public GrafoLista(int vertices, boolean dirigido) {
  	super(dirigido);
  	Lista = new LinkedList[vertices];
  	for(int n = 0; n < vertices; n++) Lista[n] = new LinkedList<Arista>();
  	NumVertices = vertices;
  }

	public boolean EstaConectado(int origen, int destino) {
		if(origen == destino) return true;
    for(int n = 0; n < Lista[origen].size(); n++) {
    	Vertex Vertice = (Vertex)Lista[origen].get(n);
    	if(Vertice.Num == destino) return true;
    }
		return false;
	}

	public void InsertarArista(int origen, int destino, int peso) {
		if(origen == destino) return;
		if(EstaConectado(origen, destino)) return;
		Vertex Vertice = new Vertex();
		Vertice.Num = destino;
		Vertice.Peso = peso;
		Lista[origen].add(Vertice);
		if(!Dirigido) {
			Vertex Vertice2 = new Vertex();
			Vertice2.Num = origen;
			Vertice2.Peso = peso;
			Lista[destino].add(Vertice2);
		}
		NumAristas++;
	}
}

class Arista {
  public int vertex1, vertex2, weight;

  public Arista(int v1, int v2, int wt) {
    vertex1 = v1;
    vertex2 = v2;
    weight  = wt;
  }
}