Clase Graph en Java con Algoritmos de Grafos
Implementación da clase Graph en Java
public class Graph<T> {
double INFINITO = Double.POSITIVE_INFINITY;private T [] nodes; // Array dos nodosprivate boolean [][] edges; // Array de eixesprivate double [][] weights; // Array de pesosint numNodes;private double[][] A; // Matriz de custos que xera Floydprivate T[][] P; // Matriz de predecesores que xera Floydint[] visitados; // Para o percorrido en profundidadeprivate 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 nodoedges[i][numNodes-1] = false;// Non hai eixes saíntes tampoucoedges[numNodes-1][i] = false;// Non hai pesosweights[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";elsecadena += "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 nodosboolean[] s = new boolean[numNodes]; // Nodos visitadosint[] path = new int[numNodes];int pos = getNode(nodoOrigen);int a = 0;
// Inicializaciónfor(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];}elsereturn 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;}}}}}}