Guía de estilo de JAVA

A continuación se transcribe, desde la página del curso Curso práctica en ingeniería de software publicado por el Instituto Tecnológico de Massachussets (MIT) en su iniciativa de cursos libres OpenCourseWare  traducidos a su vez al español por el portal Universia, una guía de estilo para programar en java:

Boletín S1: Guía de estilo de Java™

Visión global

El estilo del código constituye una parte crucial en el ejercicio de la buena ingeniería del software. El objetivo se centra en escribir código que sea claro y fácil de entender, y que al mismo tiempo reduzca el esfuerzo que se emplea en hacer ampliaciones o modificaciones futuras.

Hay varios aspectos del código que lo pueden hacer más legible. Algunos de los más importantesson el empleo de nombres descriptivos, así como el uso de una indentación coherente y decomentarios informativos.

En el curso 6.170 no le indicamos que siga un estilo de código detallado. No obstante, esperamos que su código sea claro y fácil de entender. Este boletín le facilita una serie de directrices generales dentro de las cuales usted debería desarrollar un estilo de código propio y logrado.

Nombres descriptivos

Debería usar nombres nemónicos para los paquetes, los tipos, las variables y las etiquetas de ramificación, mediante los cuales se pudiese vislumbrar su uso y/o significado. Esto no significa que
los nombres tengan que ser muy largos. Por ejemplo, nombres como i y j servirían para nombrar los índices de bucles cortos, ya que los programadores conocen por convención los significados y usos de estas variables.

Le aconsejamos que siga una convención común que consiste en poner en mayúsculas los nombres
de las clases y en empezar los nombres de las variables y de los paquetes con letra minúscula. Existen otras convenciones comunes tales como escribir el nombre completo de las constantes en mayúsculas; no le pediremos que siga ninguna convención en concreto, pero debería elegir aquellas que le resultaran útiles y seguirlas de manera coherente.

Indentación coherente

Una indentación coherente del código ayuda al lector a comprender la estructura lógica de mismo,
al facilitarle la tarea de ver dónde acaban las sentencias if y los bucles while, etc. Debería hacer uso de estrategias coherentes; por ejemplo, sea coherente en cuanto a si pone el corchete en la misma línea que el if o en la línea siguiente, o en cuanto a la apariencia de sus bloques try-catch-finally.Examine el código del libro de texto para observar una muestra de estilo; puede desarrollar su propio código con total libertad si le resulta más cómodo.

Emacs proporciona un modo autoindent, que activa la indentación automática. Debería utilizarlo para dar formato a su código al mismo tiempo que lo escribe y volver a darle formato después de
realizar alguna modificación. También puede usar grind para dar a su código un formato decente para la impresión, incluso si el fichero fuente no está bien indentado.

Comentarios informativos

No cometa el error de escribir comentarios por todas partes --un comentario malo o inútil es peor que no poner nada. Si la información está clara en el código, el añadir un comentario simplemente supondrá trabajo de más para el lector.

    i++;    // se incrementa i     ESTE COMENTARIO ES INÚTIL

Los buenos comentarios añaden información al código de manera clara y concisa. Por ejemplo, los comentarios son informativos si:

• Permiten que el lector evite leer el alguna parte del código: el siguiente comentario ahorra al lector el esfuerzo de tener que averiguar el efecto de algunas fórmulas complicadas, y pone de manifiesto la intención del programador, de manera que las fórmulas se puedan revisar más tarde.

  // calcula la desviación estándar de los elementos de la lista que son 
  // menores que el valor límite
  
  for (int i=0; i<n; i++) {
  
      //...
  
  }

  Una aplicación importante de este tipo de comentario consiste en documentar los argumentos y los valores que devuelven las funciones, de modo que los clientes no tengan que leer la implementación para comprender cómo usar la función.
   
• Explican un algoritmo o paso oscuro: esto es particularmente importante cuando los resultados
  de algún paso no quedan claros en ese trozo de código. Debería explicar algoritmos que puedan resultar engañosos, operaciones con efectos secundarios, números mágicos del código, etc.

  // Señal de que una nueva petición de transferencia se ha completado y está lista
  // para ser procesada. El hilo principal comenzará la transferencia del disco
  // la próxima vez que despierte y se dé cuenta de que esta variable ha cambiado.
  
  buffer_manager.active_requests ++;

• Indican supuestos: ¿bajo qué supuestos funciona adecuadamente una parte del código?

  // La memoria intermedia (buffer) contiene al menos un caracter.
  // Si la memoria intermedia está vacía, el gestor de interrupciones vuelve sin
  
  // llamar a esta función.
  
  c = buffer.get_next_character();

• Señalan deficiencias del código y partes de código incompleto: es habitual que la primera versión del código no esté completa; es importante señalar el código que se sabe que es incorrecto. Si se le agota el tiempo de entrega de un ejercicio y presenta un programa que no funciona correctamente en todas las entradas, esperamos que su código muestre que usted es consciente de esas deficiencias.

  if (n > 0) {
  
      average = sum / n;
  
  } else {
  
      // XXX necesita utilizar el promedio de decaimiento de la  iteración anterior.
      // Por ahora, use simplemente un valor arbitrario. 
      average = 15;
  
  }

Consejos:

• No escriba primero el código para luego comentarlo; coméntelo sobre la marcha. Es poco probable que pueda volver y hacerlo más tarde.
• No le exigiremos que escriba comentarios en cada objeto del programa como se hace en algunos cursos de ingeniería del software. Sin embargo, su nota dependerá considerablemente de la claridad del código y puede que alguna parte del programa que esté clara para usted, no resulte tan clara para el lector. Por lo tanto, le conviene añadir comentarios aclaratorios a todas las clases, campos y métodos.

Descargar documentos desde la red

Para descargar un archivo desde la red se utiliza la clase URL para tener acceso al archivo o documento de red y se abren un flujo de entrada y otro de salida para recorrer y copiar dicho documento.

import java.io.*;
import java.net.*;

public class TestDescarga {
    public static void main(String[] args) {
        // Por simplicidad se supondrá que el archivo a descargar y la ruta donde
        // se va a guardar son conocidas.
        String origen = "http://mit.ocw.universia.net/1.00/s02/class-sessions/lecture-31/lecture-31.pdf";
        String destino = "c:/downloads/salida.pdf";
        descargar(origen, destino);
    }

    public static void descargar(String origen, String destino) {
        try {
            // Paso 1: crear el objeto URL para enlazar la dirección del documento
            URL url = new URL(origen);

            // Paso 2: crear un flujo de entrada para leer el contenido del documento
            byte[] data = new byte[1024];
            DataInputStream in = new DataInputStream(url.openStream());

            // Paso 3: crear el archivo de salida
            FileOutputStream out = new FileOutputStream(destino);

            // Paso 4: recorrer el archivo de entrada
            int leidos;
            while(true) {
                leidos = in.read(data);
                if(leidos >= 0) out.write(data, 0, leidos);
                else break;
            } 
            out.flush();
            out.close();
        }
        catch(MalformedURLException x) {
            System.err.println("Error, dirección mal formada, intente más tarde");
        }
        catch(IOException x) {
            System.err.println("Error de IO: " + x.getMessage());
        }
    }
}

Números Primos

Verificación

Teniendo en cuenta que, por definición, un número primo es aquel que es divisible exclusivamente por sí mismo y por la unidad, se puede escribir una función que verifique si un número entero es primo dividiéndolo por todos los números entre 1 y él, y finalmente contar cuántos divisores tuvo. Si la cantidad de divisores es 2, entonces el número es primo, de lo contrario no lo es. Este algoritmo se puede representar como:

// Version inicial.  Cuenta el numero de divisores y si es menor o igual
// que dos entonces es primo.
    public static boolean esPrimoV1(long n) {
        long contador=0;
        for(long i=1; i<=n; i++) {
            if(n%i == 0) contador  ;
        }
        if(contador>=2) return false;
        else return true;
    }

Este algoritmo, si bien identifica si el número es primo, es bastante ineficiente, entre otras por razones tales como la espera para hacer todas las divisiones para decidir que un número no es primo aunque, si se omite la división por uno y por el mismo número, basta con encontrar un solo divisor más para determinar que el número no es primo. De la misma manera, el algoritmo divide el número por todos los pares anteriores a él cuando no es necesario, ya que diviéndolo por dos es suficiente para saber si es múltiplo de un número par.

Una versión optimizada del algoritmo es la siguiente:

// Version seis.  Hace los cálculos de funciones solo cuando es necesario
    public static boolean esPrimoV6(long n) {
        double raiz = Math.sqrt(n);
        if(n==2) return true;
        if(n%2==0) return false;
        for(long i=3; i<=raiz; i+=2) {
            if(n%i == 0) return false;
        }
        return true;
    }

Se sugiere calcular con las dos versiones el tiempo que se tarda en determinar si el número entero más grande que puede manejar java (Long.MAX_VALUE) es primo o no.

Generación

Si se quiere generar un conjunto de números primos, una posible alternativa es utilizar el método de Eratóstenes, en el cual se ubican en un vector todos los posibles números en un rango, e iniciando en el número 2 se marcan como no primos todos los múltiplos de dicho número; el proceso continua para todos los números no marcados.

El siguiente método genera un vector con todos los números enteros entre 1 y 2 a la 31:

// Generación de primos por el método de Eratóstenes
    public static int[] generarPrimos() {
        boolean[] tmp = new boolean[Integer.MAX_VALUE/2];
        for(int i=0; i<tmp.length; i++) tmp[i]=true;
        int contador  = tmp.length;
        int raiz      = (int) Math.sqrt(tmp.length);
        for(int i=2; i<=raiz; i++) {
            if(tmp[i]!=true) continue;
            for(int j=i*i; j<tmp.length;j+=i){
                if(tmp[j]==true) {
                    contador--;
                    tmp[j]=false;
                }
            }
        }
        int   j         = 0;
        int[] respuesta = new int[contador];
        for(int i=0; i<tmp.length; i++) if(tmp[i]==true) respuesta[j++]=i;
        return respuesta;
    }

Nótese que el arreglo tmp podría usarse para determinar de forma inmediata si un número dado es primo o no, pues bastaría con mirar si la posición respectiva de ese número en el arreglo hay un valor de falso o verdadero.

Ruta más corta - Solución por el algoritmo de Dijkstra

Para solucionar el problema de la ruta más corta entre dos nodos de un grafo se puede utilizar el Algoritmo de Dijkstra, el cual sigue el siguiente procedimiento para calcular la ruta más corta desde el nodo origen hasta cada uno de los nodos del grafo:

• Crea una listas de nodos para almacenar los nodos con distancia mínima ya calculada
• Crear una cola de prioridad para los nodos pendientes de evaluar
• Inserta el nodo origen a la cola de prioridad
• Mientras que haya nodos en la cola de prioridad
• Extrae el primer nodo de la cola de prioridad (tmp)
• Agrega el nodo tmp a la lista de nodos ya calculados
• Genera una lista de los nodos conectados al nodo tmp que no estén en la lista de ya calculados
• Para cada nodo de la lista (nod)
• Calcula la distancia al origen con la distancia entre tmp y nod más la distancia calculada entre el origen y tmp.
• Si el nodo nod no está en la cola de prioridad lo agrega
• Si el nodo nod ya está en la cola de prioridad y la distancia con la que está guardado en la cola es menor, lo deja como está y sino, lo actualiza con la distancia calculada
• Fin
• Fin

Al finalizar este procedimiento se tiene una lista con la menor distancia desde el origen a cada nodo.

La clase Grafo descrita en un post anterior se puede modificar para incluir un nuevo método que calcula la menor ruta usando el algoritmo de Dijkstra con dos nuevos métodos: uno para calcular la distancia entre el origen y todos lo nodos, guardando estos resultados en una lista, y el segundo para mostrar la ruta entre el origen y el nodo destino tomando la información de la lista de distancias calculadas.  Se implementa también un método adicional para verificar si un nodo ya está en la lista de terminados:

import java.util.*;

public class Grafo {
    char[]  nodos;  // Letras de identificación de nodo
    int[][] grafo;  // Matriz de distancias entre nodos
    String  rutaMasCorta;                           // distancia más corta
    int     longitudMasCorta = Integer.MAX_VALUE;   // ruta más corta
    List<Nodo>  listos=null;                        // nodos revisados Dijkstra

    // construye el grafo con la serie de identificadores de nodo en una cadena
    Grafo(String serieNodos) {
        nodos = serieNodos.toCharArray();
        grafo = new int[nodos.length][nodos.length];
    }

    // asigna el tamaño de la arista entre dos nodos
    public void agregarRuta(char origen, char destino, int distancia) {
        int n1 = posicionNodo(origen);
        int n2 = posicionNodo(destino);
        grafo[n1][n2]=distancia;
        grafo[n2][n1]=distancia;
    }

    // retorna la posición en el arreglo de un nodo específico
    private int posicionNodo(char nodo) {
        for(int i=0; i<nodos.length; i++) {
            if(nodos[i]==nodo) return i;
        }
        return -1;
    }
    
    // encuentra la ruta más corta desde un nodo origen a un nodo destino
    public String encontrarRutaMinimaDijkstra(char inicio, char fin) {
        // calcula la ruta más corta del inicio a los demás
        encontrarRutaMinimaDijkstra(inicio);
        // recupera el nodo final de la lista de terminados
        Nodo tmp = new Nodo(fin);
        if(!listos.contains(tmp)) {
            System.out.println("Error, nodo no alcanzable");
            return "Bye";
        }
        tmp = listos.get(listos.indexOf(tmp));
        int distancia = tmp.distancia;  
        // crea una pila para almacenar la ruta desde el nodo final al origen
        Stack<Nodo> pila = new Stack<Nodo>();
        while(tmp != null) {
            pila.add(tmp);
            tmp = tmp.procedencia;
        }
        String ruta = "";
        // recorre la pila para armar la ruta en el orden correcto
        while(!pila.isEmpty()) ruta+=(pila.pop().id + " ");
        return distancia + ": " + ruta;
    }

    // encuentra la ruta más corta desde el nodo inicial a todos los demás
    public void encontrarRutaMinimaDijkstra(char inicio) {
        Queue<Nodo>   cola = new PriorityQueue<Nodo>(); // cola de prioridad
        Nodo            ni = new Nodo(inicio);          // nodo inicial
        
        listos = new LinkedList<Nodo>();// lista de nodos ya revisados
        cola.add(ni);                   // Agregar nodo inicial a la cola de prioridad
        while(!cola.isEmpty()) {        // mientras que la cola no esta vacia
            Nodo tmp = cola.poll();     // saca el primer elemento
            listos.add(tmp);            // lo manda a la lista de terminados
            int p = posicionNodo(tmp.id);   
            for(int j=0; j<grafo[p].length; j++) {  // revisa los nodos hijos del nodo tmp
                if(grafo[p][j]==0) continue;        // si no hay conexión no lo evalua
                if(estaTerminado(j)) continue;      // si ya fue agregado a la lista de terminados
                Nodo nod = new Nodo(nodos[j],tmp.distancia+grafo[p][j],tmp);
                // si no está en la cola de prioridad, lo agrega
                if(!cola.contains(nod)) {
                    cola.add(nod);
                    continue;
                }
                // si ya está en la cola de prioridad actualiza la distancia menor
                for(Nodo x: cola) {
                    // si la distancia en la cola es mayor que la distancia calculada
                    if(x.id==nod.id && x.distancia > nod.distancia) {
                        cola.remove(x); // remueve el nodo de la cola
                        cola.add(nod);  // agrega el nodo con la nueva distancia
                        break;          // no sigue revisando
                    }
                }
            }
        }
    }

    // verifica si un nodo ya está en lista de terminados
    public boolean estaTerminado(int j) {
        Nodo tmp = new Nodo(nodos[j]);
        return listos.contains(tmp);
    }

    // encontrar la ruta mínima por fuerza bruta
    public void encontrarRutaMinimaFuerzaBruta(char inicio, char fin) {
        int p1 = posicionNodo(inicio);
        int p2 = posicionNodo(fin);
        // cola para almacenar cada ruta que está siendo evaluada
        Stack<Integer> resultado = new Stack<Integer>();
        resultado.push(p1);
        recorrerRutas(p1, p2, resultado);
    }

    // recorre recursivamente las rutas entre un nodo inicial y un nodo final
    // almacenando en una cola cada nodo visitado
    private void recorrerRutas(int nodoI, int nodoF, Stack<Integer> resultado) {
        // si el nodo inicial es igual al final se evalúa la ruta en revisión
        if(nodoI==nodoF) {
            int respuesta = evaluar(resultado);
            if(respuesta < longitudMasCorta) {
                longitudMasCorta = respuesta;
                rutaMasCorta     = "";
                for(int x: resultado) rutaMasCorta+=(nodos[x]+" ");
            }
            return;
        }
        // Si el nodoInicial no es igual al final se crea una lista con todos los nodos
        // adyacentes al nodo inicial que no estén en la ruta en evaluación
        List<Integer> lista = new Vector<Integer>();
        for(int i=0; i<grafo.length;i++) {
            if(grafo[nodoI][i]!=0 && !resultado.contains(i))lista.add(i);
        }
        // se recorren todas las rutas formadas con los nodos adyacentes al inicial
        for(int nodo: lista) {
            resultado.push(nodo);
            recorrerRutas(nodo, nodoF, resultado);
            resultado.pop();
        }
    }

    // evaluar la longitud de una ruta
    public int evaluar(Stack<Integer> resultado) {
        int  resp = 0;
        int[]   r = new int[resultado.size()];
        int     i = 0;
        for(int x: resultado) r[i++]=x;
        for(i=1; i<r.length; i++) resp+=grafo[r[i]][r[i-1]];
        return resp;
    }

    public static void main(String[] args) {
        Grafo g = new Grafo("abcdef");
        g.agregarRuta('a','b', 3);
        g.agregarRuta('a','e', 6);
        g.agregarRuta('a','f',10);
        g.agregarRuta('b','c', 5);
        g.agregarRuta('b','e', 2);
        g.agregarRuta('c','d', 8);
        g.agregarRuta('c','e', 9);
        g.agregarRuta('c','f', 7);
        g.agregarRuta('d','f', 4);
        g.agregarRuta('e','f', 4);
        char inicio = 'a';
        char fin    = 'd';
        String respuesta = g.encontrarRutaMinimaDijkstra(inicio, fin);
        System.out.println(respuesta);
    }
}

Esta clase requiere del uso adicionalmente de la clase Nodo, que va a servir para la cola de prioridad y para llevar registro de la distancia mínima desde el origen a un nodo, así como la referencia al nodo inmediatamente anterior:

public class Nodo implements Comparable<Nodo> {
    char id;
    int  distancia   = Integer.MAX_VALUE;
    Nodo procedencia = null;
    Nodo(char x, int d, Nodo p) { id=x; distancia=d; procedencia=p; }
    Nodo(char x) { this(x, 0, null); }
    public int compareTo(Nodo tmp) { return this.distancia-tmp.distancia; }
    public boolean equals(Object o) {
        Nodo tmp = (Nodo) o;
        if(tmp.id==this.id) return true;
        return false;
    }
}

Programación Cliente/Servidor básica

Una aplicación cliente servidor requiere básicamente tres elementos: un programa servidor que atiende las peticiones de los clientes; un programa cliente que se conecta al servidor y; un protocolo de comunicaciones que indica la secuencia de mensajes que se pasan un cliente y un servidor.

En el siguiente ejemplo, el servidor será multiusuario, es decir, atenderá simultáneamente varios clientes, y para ello se utilizarán hilos -uno por cada cliente que se conecte- que atenderán en forma exclusiva el proceso de cada cliente. El cliente, por su parte, se conectará al servidor e iniciarán un diálogo (protocolo) en el cual el cliente enviará un número y el servidor devolverá el valor del área del círculo de radio igual al valor envíado por el cliente. El proceso para cada cliente terminará cuando se le envíe al servidor un valor negativo.

Servidor

El proceso del servidor inicia creando un ServerSocket para escuchar peticiones por el puerto 65432 (debe ser un valor entre 1225 y 65535 que no esté siendo utilizado en el equipo donde va a correr). Cada vez que un cliente ingrese se crea un nuevo objeto de la clase Socket y se instancia un nuevo hilo de la clase HiloServidor que se encargará de manejar la interacción con el cliente.

import java.io.*;
import java.net.*;
public class ServidorAreaCirculo {
    final int puerto = 65432;   // puerto sobre el que se esperarán conexiones
    ServerSocket  ss;
    public void proceso() {
        try {
            ss = new ServerSocket(puerto);
            while(true) {                       // ciclo infinito para esperar conexiones
                Socket socket = ss.accept();    // espera hasta que un cliente se conecta
                Thread   hilo = new Thread(new HiloServidor(socket));   // crea hilo hijo
                hilo.start();                   // inicia el hilo hijo que atiende al cliente
            }
        }
        catch(IOException x) {
            System.err.println("Error de conexión: " + x.getMessage());
        }
    }

    class HiloServidor implements Runnable {
        Socket socket;
        HiloServidor(Socket s) { socket = s; }
        public void run() {
            try {
                // crea flujos de entrada y salida
                BufferedReader in = new BufferedReader(
                                    new InputStreamReader(socket.getInputStream()));
                PrintWriter   out = new PrintWriter(socket.getOutputStream());
                // paso 1: envio mensaje de bienvenida
                out.println("Bienvenid@, este servidor calcula áreas de círculos");
                while(true) {
                    // paso 2: solicita envio del radio del círculo
                    out.println("Digite radio del circulo (ó número negativo para terminar): ");
                    out.flush();
                    // paso 3: recibe el radio y genera la salida a enviar
                    String cadena = in.readLine();
                    try {
                        double  radio = Double.parseDouble(cadena);
                        if(radio<0) break;
                        double area = Math.PI*Math.pow(radio,2);
                        cadena = "El área de un círculo de radio " + radio + " es " +
                                String.format("%,.4f", area);
                    }
                    catch(NumberFormatException x) {
                        cadena = "Error, la cadena recibida no es un número válido";
                    }
                    // paso 4: devuelve el mensaje al usuario
                    out.println(cadena);
                    out.flush();
                }
                out.println("Gracias por venir, vuelve pronto");
                out.flush();
                socket.close();
            }
            catch(IOException x) {
                System.err.println(x.getMessage());
            }
        }
    }

    public static void main(String[] args) {
        ServidorAreaCirculo s = new ServidorAreaCirculo();
        s.proceso();
    }
}

Cliente

En este caso, el cliente inicia abriendo un socket con el equipo y puerto donde debe estar esperando el programa servidor. Para la prueba se supone que el servidor debe estar ejecutándose en la misma máquina del cliente (localhost) en el puerto 65432.

import java.io.*;
import java.io.*;
import java.net.*;
import javax.swing.*;
import static javax.swing.JOptionPane.*;

public class ClienteAreaCirculo {
    public void proceso() {
        try {
            // Se crea socket conectado al servidor y puerto conocidos
            Socket     socket = new Socket("localhost",65432);
            // Se crean los flujos de entrada y salida
            PrintWriter   out = new PrintWriter(socket.getOutputStream());
            BufferedReader in = new BufferedReader(
                                new InputStreamReader(socket.getInputStream()));
            // Paso 1: se recibe mensaje de bienvenida del servidor
            String cadena = in.readLine();
            System.out.println(cadena);
            while(true) {
                // Paso 2: se recibe mensaje de solicitud de número
                cadena = in.readLine();
                System.out.println(cadena);
                // Paso 3: se pregunta al usuario el número a enviar
                cadena = showInputDialog(cadena);
                // Paso 4: se envia el número al servidor
                out.println(cadena);
                out.flush();
                // Paso 5: se recibe la respuesta del servidor
                cadena = in.readLine();
                System.out.println(cadena);
                if(cadena.startsWith("Gracias por venir")) break;
            }
        }
        catch(IOException x) {
           System.err.println("Error de conexión: "+x.getMessage());
        }

    }

    public static void main(String[] args) {
        ClienteAreaCirculo c = new ClienteAreaCirculo();
        c.proceso();
    }
}

Complejidad del algoritmo del camino más corto por fuerza bruta

Para probar la eficiencia del algoritmo de búsqueda de la ruta más corta entre dos puntos por fuerza bruta se requieren en primer lugar dos modificaciones a la clase Grafo: la creación de dos atributos (public String rutaMasCorta e int longituRutaMasCorta) donde se almacenarán respectivamente, la ruta más corta de recorrido del grafo en forma de cadena de caracteres y la longitud de dicha ruta; y en segundo lugar, se modifica el método recorrerRutas para que haga la comparación de cada ruta recorrida y guarde la ruta más corta y la distancia de dicha ruta en las variables mencionadas anteriormente, y adicionalmente para que no muestre cada ruta evaluada. El método queda así:

// recorre recursivamente las rutas entre un nodo inicial y un nodo final
    // almacenando en una cola cada nodo visitado
    private void recorrerRutas(int nodoI, int nodoF, Stack<Integer> resultado) {
        // si el nodo inicial es igual al final se evalúa la ruta en revisión
        if(nodoI==nodoF) {
            int respuesta = evaluar(resultado);
            if(respuesta < longitudMasCorta) {
                longitudMasCorta = respuesta;
                rutaMasCorta     = "";
                for(int x: resultado) rutaMasCorta+=(nodos[x]+" ");
            }
            return;
        }
        // Si el nodoInicial no es igual al final se crea una lista con todos los nodos
        // adyacentes al nodo inicial que no estén en la ruta en evaluación
        List<Integer> lista = new Vector<Integer>();
        for(int i=0; i<grafo.length;i++) {
            if(grafo[nodoI][i]!=0 && !resultado.contains(i))lista.add(i);
        }
        // se recorren todas las rutas formadas con los nodos adyacentes al inicial
        for(int nodo: lista) {
            resultado.push(nodo);
            recorrerRutas(nodo, nodoF, resultado);
            resultado.pop();
        }
    }

Una vez realizadas estas modificaciones, se crea una nueva clase de pruebas, TestGrafo, en la cual se van a crear grafos de tamaño 1 en adelante, aprovechando las letras del alfabeto romano, desde el nodo 'a' hasta el nodo 'z' en forma secuencial, se crearán las rutas para estos grafos y se realizará la búsqueda de la ruta más corta entre dos nodos aleatorios. A continuación se presenta el código completo en java de la clase TestGrafo:

import java.util.*;

public class TestGrafo {
    public static void main(String[] args) {
        // variables para cálculo del tiempo
        long      tiempo1;
        long      tiempo2;
        double    tiempo;
        String    cadena="";            // cadena con los posibles nodos
        Random    rnd = new Random();   // generador de números aleatorios
        final int MAX_DIST = 50;        // máxima distancia entre 2 nodos

        for(char letra='a'; letra<='z'; letra++) {
            cadena+=letra;
            // Crea un nuevo grafo con tantos nodos como letras en la cadena
            Grafo g = new Grafo(cadena);
            // Crea rutas de tamaño aleatorio entre todos los nodos
            for(char i='a';i<=letra;i++) {
                for(char j=(char)(i+1);j<=letra; j++) {
                    g.agregarRuta(i, j, rnd.nextInt(MAX_DIST));
                }
            }
            // Selecciona dos nodos aleatorios para buscar la ruta mas corta
            char origen  = cadena.charAt(rnd.nextInt(cadena.length()));
            char destino = cadena.charAt(rnd.nextInt(cadena.length()));
            // Tiempo del sistema antes del proceso
            tiempo1      = System.currentTimeMillis();
            // Busqueda de la ruta más corta entre los dos nodos aleatorios
            g.encontrarRutaMinimaFuerzaBruta(origen, destino);
            // Tiempo del sistema al finalizar el proceso
            tiempo2 = System.currentTimeMillis();
            // Tiempo del proceso
            tiempo  = (tiempo2-tiempo1)/1000.0;
            // Mostrar cantidad de nodos del grafo y tiempo transcurrido
            System.out.printf("%3d %,10.2f %n", cadena.length(), tiempo);
        }
    }
}

La ejecución del anterior programa trae los siguientes resultados para cantidad de nodos desde 1 hasta 13, con tiempos en segundos:

 1       0,01 
 2       0,00 
 3       0,00 
 4       0,00 
 5       0,00 
 6       0,00 
 7       0,02 
 8       0,00 
 9       0,13 
10       1,18 
11       9,92 
12      44,91 
13     564,72 

Siguiendo esta secuencia, se podría pensar que el tiempo de respuesta para 14 nodos podría estar en el orden de varias horas; puede notarse entonces que a partir de un número relativamente pequeño de nodos el tiempo para encontrar la solución se torna inmanejable. La razón de esto estriba en que la cantidad de rutas posibles que conectan los puntos de un grafo es proporcional al factorial del número de nodos en el grafo, por lo que el tiempo de ejecución de cualquier algoritmo que deba recorrer todos los nodos de un grafo será entonces del orden de O(N!).

Evaluador de Funciones con Constantes

En este versión del evaluador de funciones en Java se ha agregado la funcionalidad de usar las constantes definidas en la clase java.lang.Math (PI y E).

En el método main de ejemplo se crea una función que calcula el área de un círculo utilizando el valor de PI:

import java.util.*;
import java.util.regex.*;
import java.lang.reflect.*;

public class Expresion {
    enum TipoToken  {   NUMERO, VARIABLE, FUNCION, ADD, SUB, MUL, DIV,
                        EXP, P_IZQ, P_DER, ERROR };
    class Token {
        TipoToken tipo;
        String    texto;
        Token(TipoToken ti, String te) { tipo=ti; texto=te;}
        Token(TipoToken ti) { tipo = ti; }
    }
    Queue<Token>    colaTokens;
    String          cadenaFuncion;
    double          variableX;

    Expresion(String c) throws Exception {
        cadenaFuncion = c;
    }

    private void generarTokens() throws Exception {
        colaTokens = new LinkedList<Token>();
        StringBuffer entrada   = new StringBuffer(cadenaFuncion);
        Pattern pNumero = Pattern.compile("\\-?\\d+(\\.\\d+)?");
        Pattern pID     = Pattern.compile("\\p{Alpha}\\w+");
        Pattern pFuncion= Pattern.compile("\\p{Alpha}\\w+\\s+\\(");
        while(entrada.length()>0) {
            Matcher      m  = pNumero.matcher(entrada);
            if(m.lookingAt()) {
                colaTokens.add(new Token(TipoToken.NUMERO,m.group()));
                entrada.delete(0, m.end());
                continue;
            }
            if(entrada.charAt(0) == 'x' || entrada.charAt(0) == 'X') {
                colaTokens.add(new Token(TipoToken.VARIABLE,"x"));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '+') {
                colaTokens.add(new Token(TipoToken.ADD));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '-') {
                colaTokens.add(new Token(TipoToken.SUB));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '*') {
                colaTokens.add(new Token(TipoToken.MUL));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '/') {
                colaTokens.add(new Token(TipoToken.DIV));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '(') {
                colaTokens.add(new Token(TipoToken.P_IZQ));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == ')') {
                colaTokens.add(new Token(TipoToken.P_DER));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '^') {
                colaTokens.add(new Token(TipoToken.EXP));
                entrada.deleteCharAt(0);
                continue;
            }
            m = pFuncion.matcher(entrada);
            if(m.lookingAt()) {
                String cadena = m.group();
                cadena = cadena.split("\\s+\\(")[0].trim();
                colaTokens.add(new Token(TipoToken.FUNCION, cadena));
                continue;
            }
            m = pID.matcher(entrada);
            if(m.lookingAt()) {
                colaTokens.add(new Token(TipoToken.VARIABLE, m.group()));
                entrada.delete(0, m.end());
                continue;
            }
            throw new Exception("Elemento no reconocido en la entrada: "
                                + entrada.charAt(0));
        }
    }

    private double evaluar(double x) throws Exception {
        generarTokens();
        variableX = x;
        return expresion();
    }

    private double expresion() {
        double respuesta=termino();
        while(!colaTokens.isEmpty() ) {
            switch(colaTokens.element().tipo) {
                case ADD:   colaTokens.remove();
                            respuesta+=termino();
                            continue;
                case SUB:   colaTokens.remove();
                            respuesta-=termino();
                            continue;
            }
            break;
        }
        return respuesta;
    }

    private double termino() {
        double respuesta=factor();
        while(!colaTokens.isEmpty() ) {
            switch(colaTokens.element().tipo) {
                case MUL:   colaTokens.remove();
                            respuesta*=factor();
                            continue;
                case DIV:   colaTokens.remove();
                            respuesta/=factor();
                            continue;
                default:
            }
            break;
        }
        return respuesta;
    }

    private double factor() {
        double respuesta=valor();
        while(!colaTokens.isEmpty() ) {
            switch(colaTokens.element().tipo) {
                case EXP:   colaTokens.remove();
                            respuesta=Math.pow(respuesta,valor());
                            continue;
            }
            break;
        }
        return respuesta;
    }

    private double valor() {
        Token token;
        try {
            double respuesta = 0;
            token     = colaTokens.poll();
            switch(token.tipo) {
                case P_IZQ:     respuesta = expresion();
                                leaToken(TipoToken.P_DER);
                                return respuesta;
                case NUMERO:    return Double.parseDouble(token.texto);
                case VARIABLE:  if(token.texto.toLowerCase().equals("x")) {
                                    return variableX;
                                }
                                Field f = java.lang.Math.class.
                                        getField(token.texto);
                                return f.getDouble(null);
                case FUNCION:   double argumento=expresion();
                                leaToken(TipoToken.P_DER);
                                Method m = java.lang.Math.class.
                                           getMethod(token.texto, Double.TYPE);
                                return (Double) m.invoke(null, argumento);
            }
            return respuesta;
        }
        catch(Exception ex) {
            System.err.println("Error: " + ex.getMessage());
            System.exit(0);
        }
        return 0;
    }

    private boolean leaToken(TipoToken t) {
        Token token = colaTokens.poll();
        if(token.tipo.equals(t)) {
            return true;
        }
        else {
            System.err.println("Error: elemento no permitido " + token.texto );
            return false;
        }
    }

    public static void main(String[] args) throws Exception {
        String funcion = "PI*x^2" ;
        Expresion  exp = new Expresion(funcion);
        for(int x=0; x<=10; x++) {
            System.out.println(x + " -> " + exp.evaluar(x));
        }
    }
}