Clase Graph en Java con Algoritmos de Grafos

Electricidad y Electrónica12,76 KB

Implementación da clase Graph en Java

public class Graph<T> {

double INFINITO = Double.POSITIVE_INFINITY;
private T [] nodes; // Array dos nodos
private boolean [][] edges; // Array de eixes
private double [][] weights; // Array de pesos
int numNodes;
private double[][] A; // Matriz de custos que xera Floyd
private T[][] P; // Matriz de predecesores que xera Floyd
int[] visitados; // Para o percorrido en profundidade
private int Pe[][];
boolean marcados[] = new boolean[100];

Graph(int n) {
nodes = (T[])new Object[n];
edges = new boolean[n][n];
weights = new double[n][n];
numNodes = 0;
A = new double [n][n];
P = (T[][]) new Object[n][n];
}

public boolean existNode(T node) {
if(getNode(node) == -1)
return false;
return true;
}

private int getNode(T node) {
for(int i = 0; i < numNodes; i++){
if(nodes[i].equals(node))
return i;
}
return -1;
}

public int addNode(T node){
if(numNodes == nodes.length)
return -1;
if(existNode(node))
return -1;
if (getNode(node) == -1 && numNodes < nodes.length)
{
nodes[numNodes] = node;
for(int i = 0; i < numNodes; i++){
// Non hai eixes entrantes co novo nodo
edges[i][numNodes-1] = false;
// Non hai eixes saíntes tampouco
edges[numNodes-1][i] = false;
// Non hai pesos
weights[i][numNodes-1] = INFINITO;
weights[numNodes-1][i] = INFINITO;
}
numNodes++;
}
inicializaA();
inicializaP();
return 0;
}

public int removeNode(T node) {
int i = getNode(node);
if(i >= 0) {
--numNodes;
if(i != numNodes+1) {
nodes[i] = nodes[numNodes];
for (int j = 0; j <= numNodes; j++) {
edges[j][i] = edges[j][numNodes];
edges[i][j] = edges[numNodes][j];
weights[i][j] = weights[numNodes][j];
weights[j][i] = weights[j][numNodes];
}
edges[i][i] = edges[numNodes][numNodes];
weights[i][i] = weights[numNodes][numNodes];
inicializaA();
inicializaP();
return 0;}
}
return -1;
}

public boolean existEdge(T source, T target) {
if(existNode(source) && existNode(target)
&& edges[getNode(source)][getNode(target)]) {
return true;
}
return false;
}

public double getEdge(T source, T target) {
if(existNode(target) && existNode(source) &&
edges[getNode(source)][getNode(target)]){
return weights[getNode(source)][getNode(target)];
}
return -1;
}

public int addEdge(T source, T target, double edgeWeight) {
if(existNode(target) && existNode(source)
&& !edges[getNode(source)][getNode(target)]
&& edgeWeight > 0) {
edges[getNode(source)][getNode(target)] = true;
weights[getNode(source)][getNode(target)] = edgeWeight;
inicializaA();
inicializaP();
return 0;
}
return -1;
}

public int removeEdge(T source, T target) {
if(existNode(target) && existNode(source)
&& edges[getNode(target)][getNode(source)]){
edges[getNode(source)][getNode(target)] = false;
weights[getNode(source)][getNode(target)] = INFINITO;
inicializaA();
inicializaP();
return 0;
}
return -1;
}

public String toString() {
DecimalFormat df = new DecimalFormat("#.##");
String cadena = "";
cadena += "VECTOR NODOS\n";
for (int i = 0; i < numNodes; i++) {
cadena += nodes[i].toString() + "\t";
}
cadena += "\n\nMATRIZ ARISTAS\n";
for (int i = 0; i < numNodes; i++) {
for (int j = 0; j < numNodes; j++) {
if (edges[i][j])
cadena += "T\t";
else
cadena += "F\t";
}
cadena += "\n";
}
cadena += "\nMATRIZ PESOS\n";
for (int i = 0; i < numNodes; i++) {
for (int j = 0; j < numNodes; j++) {
cadena += df.format(weights[i][j]) + "\t";
}
cadena += "\n";
}
return cadena;
}

Algoritmos de Camiño Mínimo e Percorrido

public double[] dijkstra(T nodoOrigen) {
double[] d = new double[numNodes]; // Pesos desde nodoOrigen ata os demais nodos
boolean[] s = new boolean[numNodes]; // Nodos visitados
int[] path = new int[numNodes];
int pos = getNode(nodoOrigen);
int a = 0;

// Inicialización
for(int i = 0; i < numNodes; i++){
s[i] = false;
if(!edges[pos][i]){
d[i] = Double.POSITIVE_INFINITY;
path[i] = -1;
}
else if(pos == i){
d[i] = 0;
path[i] = -1;
}
else{
d[i] = weights[pos][i];
path[i] = pos;
}
}
s[pos] = true;
path[pos] = 0;
for (int i = 0; i < numNodes; i++) {
int w = minCostPath(d, s);
if (w != -1) {
s[w] = true;
for (int j = 0; j < numNodes; j++) {
if (edges[w][j]) {
if (d[w] + weights[w][j] < d[j]) {
d[j] = d[w] + weights[w][j];
path[j] = w;
d[getNode(nodoOrigen)] = Double.POSITIVE_INFINITY;
}
}
}
}
}
return d;
}

private int minCostPath(double[] dist, boolean[] v) {
double minimo = Double.POSITIVE_INFINITY;
int pos = -1;
for (int i = 0; i < dist.length; i++) {
if (dist[i] < minimo && v[i] == false) {
minimo = dist[i];
pos = i;
}
}
return pos;
}

public double path(T origen, T destino) {
int OrigenPos = getNode(origen);
int DestinoPos = getNode(destino);
if(OrigenPos != -1 && DestinoPos != -1){
double [][] A = floyd();
if (Pe[OrigenPos][DestinoPos] > 0 || edges[OrigenPos][DestinoPos]){
}
}
int posOrigen = getNode(origen);
int posDestino = getNode(destino);
if(posOrigen != -1 && posDestino != -1){
double[][] A = floyd();
if(Pe[posOrigen][posDestino] > 0 || edges[posOrigen][posDestino]){
System.out.print(nodes[posOrigen]);
path2(posOrigen, posDestino);
System.out.println("\t" + A[posOrigen][posDestino] + "\t" + nodes[posDestino]);
return A[posOrigen][posDestino];
}
else
return Double.POSITIVE_INFINITY;
}
else{
System.out.println("Error.");
return -1;
}
}

private void path2(int i, int j){
int k = Pe[i][j];
if(k > 0){
path2(i, k);
path2(k, j);
System.out.print("\t" + A[i][k] + "\t" + nodes[k]);
}
}

public int recorridoProfundidad1(T nodo) {
boolean[] visitados = new boolean[numNodes];
recorridoPronfRec(nodo, visitados);
for (int i = 0; i < numNodes; i++) {
if (!visitados[i]) {
return -1;
}
}
return 0;
}

public T[] recorridoProfundidad(T nodo) {
T[] vector = (T[]) new Object[numNodes];
vector[0] = nodo;
for (int i = 0; i < numNodes; i++) {
marcados[i] = false;
}
for (int i = getNode(nodo); i < numNodes; i++)
if (!marcados[i]) {
visitado(i, vector);
System.out.println(nodes[i]);
}
return vector;
}

private void visitado(int i, T[] vector) {
marcados[i] = true;
for (int j = 0; j < numNodes; j++) {
if (edges[i][j] == true) {
if (!marcados[j])
vector[vector.length] = nodes[j];
visitado(j, vector);
}
}
}

private void recorridoPronfRec(T nodo, boolean[] visitados) {
int pos = getNode(nodo);
if (existNode(nodo)) {
visitados[pos] = true;
for (int i = 0; i < numNodes; i++) {
if (!visitados[i] && existEdge(nodo, nodes[i])) {
recorridoPronfRec(nodes[i], visitados);
}
}
}
}

Métodos Auxiliares e Algoritmo de Floyd

private void inicializaA() {
for(int i = 0; i < numNodes; i++) {
for(int j = 0; j < numNodes; j++) {
A[i][j] = Float.POSITIVE_INFINITY;
}
}
}

private void inicializaP() {
for(int i = 0; i < numNodes; i++) {
for(int j = 0; j < numNodes; j++) {
P[i][j] = null;
}
}
}

private void initsFloyd() {
for (int i = 0; i < numNodes; i++) {
for (int j = 0; j < numNodes; j++) {
if (edges[i][j]) {
A[i][j] = weights[i][j];
} else {
A[i][j] = INFINITO;
}
if (i == j) {
A[i][j] = 0;
}
P[i][j] = null;
}
}
}

public void floyd(int numero) throws Exception {
if (!(numero <= nodes.length)) {
throw new Exception("O número é demasiado grande.");
}
initsFloyd();
for (int k = 0; k < numero; k++) {
for (int i = 0; i < numero; i++) {
for (int j = 0; j < numero; j++) {
if (A[i][k] + A[k][j] < A[i][j]) {
A[i][j] = A[i][k] + A[k][j];
P[i][j] = k;
}
}
}
}
}
}

Descargar

PDF Word HTML