Graph class, dijkstra, etc
Publicado: 12 Oct 2015, 21:34
por sanko
La tarea es tarea y se me pidio hacer nuestra propia implementación de una clase Grafo, a la que iriamos añadiendo métodos como Dijkstra, floyd, dfprint, ...
De momento he implementado Dijkstra:[Enlace externo eliminado para invitados], basicamente sirve para calcular la ruta de coste mínimo entre dos nodos (A,B).
y Aqui dejo las JUNIT de todos los métodos, si se os ocurren más casos sois bienvenidos a dejar un comentario y eso que me ayudais a completar del todo las pruebas, a más exhaustivas pues mejor vaya.
Ejemplo:
[Enlace externo eliminado para invitados]
Me pase a postearlo por si a alguien le interesaba (hace tiempo no que no me logueo!) y nada, según vaya añadiendole algoritmos pues iré comentando el snipet, que perteneceria a la propia clase Graph.
Saludos
De momento he implementado Dijkstra:[Enlace externo eliminado para invitados], basicamente sirve para calcular la ruta de coste mínimo entre dos nodos (A,B).
package grafos;
import java.text.DecimalFormat;
/**
* @author Esteban
*
*/
public class Graph <T>{
private T[] nodes; // Vector de nodos
private boolean[][] edges; // matriz de aristas
private double[][] weights; // matriz de pesos
private int numNodes; // número de elementos en un momento dado
public static void main(String[] args) {
Graph<String> g = new Graph<String>(4);
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addEdge("A", "B", 1);
g.addEdge("A", "C", 5);
g.addEdge("B", "C", 2);
g.addEdge("B", "D", 3);
g.addEdge("D", "A", 4);
System.out.println(g.toString());
double[] v = g.dijkstra("A");
for(int i=0; i<v.length; i++){
System.out.print(""+v[i]+", ");
}
}
/**
*
* @param tam Número máximo de nodos del grafo
*/
public Graph(int tam) {
nodes = (T[])new Object[tam];
edges = new boolean[tam][tam];
weights = new double[tam][tam];
}
/**
* Obtiene el índice de un nodo en el vector de nodos
*
* ¡¡¡ OJO que es privado porque depende de la implementación !!!
*
* @param node el nodo que se busca
* @return la posición del nodo en el vector ó -1 si no lo encuentra
*/
private int getNode(T node) {
if(node==null) return -1;
for(int i=0; i<numNodes; i++){
if(nodes[i].equals(node))
return i;
}
return -1;
}
/**
* Inserta un nuevo nodo que se le pasa como parámetro, en el vector de
* nodos, si existe no lo inserta
*
* @param node
* el nodo que se quiere insertar
* @return 0 si lo inserta, -1 si no puede insertarlo
*/
public int addNode(T node) {
if( (node!=null) && (numNodes < nodes.length) && (!existNode(node))){
nodes[numNodes] = node;
//adding void edges
for(int i=0; i<=numNodes; i++){
edges[numNodes][i] = false;
edges[i][numNodes] = false;
weights[numNodes][i] = 0;
weights[i][numNodes] = 0;
}
numNodes++;
return 0;
}
return -1;
}
/**
* Borra el nodo deseado del vector de nodos así como las aristas de las que
* forma parte
*
* @param node
* que se quiere borrar
* @return 0 si lo borra o -1 si no lo hace
*/
public int removeNode(T node) {
int i = getNode(node);
if(i>=0){
numNodes--;
//if its not the last node...
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[i][numNodes];
weights[j][i] = weights[j][numNodes];
weights[i][j] = weights[i][numNodes];
}
// diagonal
edges[i][i] = edges[numNodes][numNodes];
weights[i][i] = weights[numNodes][numNodes];
}
return 0;
}
return -1;
}
/**
* @param node Nodo que se quiere consultar
* @return si existe o no el nodo
*/
public boolean existNode(T node) {
return (getNode(node) != -1);
}
/**
* Comprueba si existe una arista entre dos nodos que se pasan como parámetro
*
* @param source
* nodo origen
* @param target
* nodo destino
* @return verdadero o falso si existe o no, si alguno de los nodos no
* existe también falso
*/
public boolean existEdge(T source, T target) {
int i=getNode(source);
int j=getNode(target);
if(!existNode(source) && !existNode(target))
return false;
if(i>=0 && j>=0)
return(edges[i][j]);
else
return false;
}
/**
* Inserta una arista con el peso indicado (> 0) entre dos nodos, uno origen y
* otro destino.
* Si la arista existe, le cambia el peso.
* Devuelve 0 si la inserta (o cambia el peso) y -1 si no lo hace
*
* @param source
* nodo origen
* @param target
* nodo destino
* @param edgeWeight
* peso de la arista, debe ser > 0
* @return 0 si lo hace y -1 si no lo hace (también si el peso es < 0)
*/
public int addEdge(T source, T target, double edgeWeight) {
// precondition: the edge must not exist already .
if(!existEdge(source, target) && (existNode(source)) && (existNode(target))){
int i = getNode(source);
int j = getNode(target);
edges[i][j]=true;
weights[i][j]=edgeWeight;
return 0;
}else{
return -1;
}
}
/**
* Borra una arista del grafo que conecta dos nodos
*
* @param source
* nodo origen
* @param target
* nodo destino
* @return 0 si la borra o -1 si no lo hace (también si no existe alguno de sus nodos)
*/
public int removeEdge(T source, T target) {
// precondition: the edge must exist.
if(existEdge(source, target)){
int i=getNode(source);
int j=getNode(target);
edges[i][j] = false;
weights[i][j] = 0.0;
return 0;
}else
return -1;
}
/**
* Devuelve el peso de la arista que conecta dos nodos, si no existe la
* arista, devuelve -1 (también si no existe alguno de los nodos)
*
* @param source
* @param target
* @return El peso de la arista o -1 si no existe
*/
public double getEdge(T source, T target) {
if(existEdge(source, target)){
int i = getNode(source);
int j= getNode(target);
return weights[i][j];
}else
return -1;
}
/**
* Algoritmo de Dijkstra para encontrar el camino de coste mínimo desde nodoOrigen
* hasta el resto de nodos
*
* @param nodoOrigen
* @return vector D de dijkstra para comprobar funcionamiento
*/
public double[] dijkstra(T nodoOrigen) {
//for(int w=minCost(d,s); w!=-1; w=minCost(d,s)){}
double[] error = {-1.0};
int initNode = getNode(nodoOrigen);
//preconditions: origin node must exist and cant be any negative edge
if( ((nodoOrigen == null) | (initNode == -1)) || (isAnyNegativeEdge()) )
return error; //return null;
//Initializing neccesary vectors
double[] d = new double[nodes.length]; //min cost vector | distance
int[] p = new int[nodes.length]; //pointer
boolean[] s = new boolean[nodes.length]; //state
for(int i=0; i<numNodes; i++){
if(!edges[initNode][i]){
d[i] = Double.POSITIVE_INFINITY;
p[i] = -1;
}else{
d[i] = weights[initNode][i];
p[i] = 0;
}
}
s[initNode] = true;
d[initNode] = 0;
//algorithm body
int nextPos = minCost(d, s);
while(nextPos != -1){
s[nextPos]=true;
for(int i=0; i<nodes.length; i++){
if(edges[nextPos][i]){
if(d[nextPos] + weights[nextPos][i] < d[i]){
d[i] = d[nextPos] + weights[nextPos][i];
p[i] = nextPos;
}
}
}
nextPos = minCost(d, s);
}
return d;
}
/**
* Metodo para comprobar si existen aristas con peso negativo ya que por definicion
* dijkstra no puede funcionar con pesos negativos.
* @return true si encuentra al menos una arista negativa y false en caso contrario
*/
private boolean isAnyNegativeEdge(){
boolean flag = false;
for(int i=0; i<numNodes; i++)
for(int j=0; j<numNodes; j++)
if(weights[i][j] < 0)
flag = true;
return flag;
}
/**
* Busca el nodo con distancia mínima en D al resto de nodos
* @param dist vector d
* @param v vector con visitados (conjunto S)
* @return índice del nodo buscado o -1 si el grafo es no conexo o no quedan nodos sin visitar
*/
private int minCost(double[] dist, boolean[] v) { // s==v
int nextPos = -1;
double min = Double.MAX_VALUE;
for(int i=0; i<v.length; i++){
if(!v[i]){
if(dist[i] <= min){
min = dist[i];
nextPos = i;
}
}
}
return nextPos;
}
/********************************************************************/
/**
* Devuelve un String con la información del grafo
*/
@Override
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;
}
}package grafos;
import static org.junit.Assert.*;
import org.junit.Test;
public class GraphTest {
public <T> GraphTest(){
T[] nodes = (T[])new Object[10];
}
@Test
public void testAddNode() {
Graph<Integer> g = new Graph<Integer>(10);
// Casos positivos:
// Caso 1: Añadir un nodo a una lista de nodos
for(int i=0; i<=5; i++)
assertEquals(0, g.addNode(i));
// Casos Negativos:
// Caso 1: Añadir un nodo nulo
assertEquals(-1, g.addNode(null));
// Caso 2: Añadir un nodo ya existente
assertEquals(-1, g.addNode(1));
// Caso 3: Añadir un nodo en una lista de nodos llena
for(int i=6; i<10; i++)
g.addNode(i); // rellenamos hasta llenar ek vector de nodos
assertEquals(-1, g.addNode(10));
}
@Test
public void testRemoveNode() {
Graph<Integer> g = new Graph<Integer>(4);
//Rellenamos el vetor de nodos
for(int i=0; i<4; i++)
g.addNode(i);
//Pruebas Positivas
for(int i=0; i<4; i++)
assertEquals(0, g.removeNode(i));
//Pruebas Negativas
//Caso 1: Intentamos eliminar un nodo que no existe en el vector de nodos
assertEquals(-1, g.removeNode(5));
//Caso 2: Intentamos eliminar un nulo (Aunque podemos deducir que como no se pueden añadir
// nulos tampoco deberiamos encontrarnos con un nulo)
assertEquals(-1, g.removeNode(null));
}
@Test
public void testExistNode() {
Graph<Integer> g = new Graph<Integer>(4);
for(int i=0; i<4; i++)
g.addNode(i);
//Pruebas Positivas
//Caso 1: Si un nodo existe
for(int i=0; i<4; i++)
assertEquals(true, g.existNode(i));
//Pruebas Negativas
//Caso 1: Si un nodo no existe
assertEquals(false, g.existNode(5));
//Caso 2: Si un nulo no existe
assertEquals(false, g.existNode(null));
}
@Test
public void testExistEdge() {
Graph<Integer> g = new Graph<Integer>(4);
g.addNode(1);
g.addNode(2);
//Pruebas Positivas
//Caso 1: existe la arista [x, y]
g.addEdge(1, 2, 10);
assertEquals(true, g.existEdge(1, 2));
//Pruebas Negativas
//Caso 1: No existe la arista
assertEquals(false, g.existEdge(2, 3));
//Caso 2: No existe arista desde null hasta y [null, y]
assertEquals(false, g.existEdge(null, 2));
//Caso 3: No existe arista desde x hasta null [x, null]
assertEquals(false, g.existEdge(1, null));
//Caso 4: No existe arista desde null hasta null [null, null]
assertEquals(false, g.existEdge(null, null));
}
@Test
public void testAddEdge() {
Graph<Integer> g = new Graph<Integer>(4);
g.addNode(1);
g.addNode(2);
//Pruebas Positivas:
//Caso 1: Se añade una arista desde x hasta y
assertEquals(0, g.addEdge(1, 2, 10));
//Pruebas Negativas:
//Caso 2: Se añade una arista desde un nodo que no existe a un nodo existente
assertEquals(-1, g.addEdge(3, 1, 10));
//Caso 3: Se añade una arista desde un nodo existente a uno inexistente
assertEquals(-1, g.addEdge(1, 3, 10));
//Caso 4: Se añade una arista desde un nodo inexistente a otro inexistente
assertEquals(-1, g.addEdge(3, 5, 10));
//Caso 5: Se añade una arista desde null hasta un nodo existente
assertEquals(-1, g.addEdge(null, 1, 10));
//Caso 6: Se añade una arista desde un nodo existente hasta null
assertEquals(-1, g.addEdge(1, null, 10));
//Caso 7: Se añade una arista desde un null hasta un nodo inexistente
assertEquals(-1, g.addEdge(null, 3, 10));
//Caso 8: Se añade una arista desde un nodo inexistente hasta un null
assertEquals(-1, g.addEdge(3, null, 10));
//Caso 9: Se añade una arista desde un nodo nulo hasta otro null
assertEquals(-1, g.addEdge(null, null, 10));
}
@Test
public void testRemoveEdge() {
Graph<Integer> g = new Graph<Integer>(10);
g.addNode(1);
g.addNode(2);
g.addEdge(1, 2, 10);
//Pruebas Positivas:
//Caso 1: Se borra la arista desde x hasta y
assertEquals(0, g.removeEdge(1, 2));
//Pruebas Negativas:
//Caso 1: Se intenta borrar una arista desde un nodo inexistente a otro existente
assertEquals(-1, g.removeEdge(3, 1));
//Caso 2: Se intenta borrar una arista desde un nodo existente a otro inexistente
assertEquals(-1, g.removeEdge(1, 3));
//Caso 3: Se intenta borrar una arista desde un nodo inexistente a otro inexistente
assertEquals(-1, g.removeEdge(3, 5));
//Caso 4: Se intenta borrar una arista desde un nodo existente a otro nulo
assertEquals(-1, g.removeEdge(1, null));
//Caso 5: Se intenta borrar una arista desde un nulo a un nodo existente
assertEquals(-1, g.removeEdge(null, 1));
//Caso 6: Se intenta borrar una arista desde un nodo inexistente a un nulo
assertEquals(-1, g.removeEdge(3, null));
//Caso 7: Se intenta borrar una arista desde un nulo a un nodo inexistente
assertEquals(-1, g.removeEdge(null, 3));
//Caso 8: Se intenta borrar una arista desde un nulo hasta otro nulo
assertEquals(-1, g.removeEdge(null, null));
}
@Test
public void testGetEdge() {
Graph<Integer> g = new Graph<Integer>(3);
g.addNode(1);
g.addNode(2);
g.addNode(3);
g.addEdge(1, 2, 10);
g.addEdge(1, 3, 5);
//Pruebas Positivas
//Caso 1: Devuelve el peso que tiene asociado una arista
assertEquals(10, g.getEdge(1, 2), 0.0);
assertEquals(5, g.getEdge(1, 3), 0.0);
//Pruebas Negativas
//Caso 1: Intenta devolver el peso de una arista que no existe
assertEquals(-1.0, g.getEdge(2, 1), 0.0);
}
@Test
public void testDijsktra(){
//building the graph
Graph<String> g = new Graph<String>(4);
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addEdge("A", "B", 1);
g.addEdge("A", "C", 5);
g.addEdge("B", "C", 2);
g.addEdge("B", "D", 3);
g.addEdge("D", "A", 4);
//Pruebas Positivas
//Case 1: Dijkstra works perfectly
double[] result = new double[]{0.0, 1.0, 3.0, 4.0};
double[] dijskCall = g.dijkstra("A");
//assertArrayEquals(new double[]{0.0, 1.0, 3.0, 4.0}, g.dijkstra("A"), 0.01);
for(int i=0; i<result.length; i++){
assertEquals(result[i], dijskCall[i], 0.0);
}
//Pruebas Negativas
//Case 1. Init node doesnt exist
assertArrayEquals(new double[]{-1.0}, g.dijkstra("F"), 0.0);
//Case 2. There are negative edges in the graph
Graph<String> g2 = new Graph<String>(3);
g2.addNode("A");
g2.addNode("B");
g2.addNode("C");
g2.addEdge("A", "B", 10);
g2.addEdge("B", "C", -10.0);
assertArrayEquals(new double[]{-1.0}, g2.dijkstra("A"), 0.0);
}
}[Enlace externo eliminado para invitados]
Me pase a postearlo por si a alguien le interesaba (hace tiempo no que no me logueo!) y nada, según vaya añadiendole algoritmos pues iré comentando el snipet, que perteneceria a la propia clase Graph.
Saludos