A long time ago, in an distance engineer course...

gistfile1.java

package routersoft;

import java.sql.Statement;
import java.sql.Connection;
import java.sql.ResultSet;
import javax.swing.JOptionPane;
import java.sql.SQLException;
import java.util.*;

/**
 * <p>Title: RouterSoft</p>
 *
 * <p>Description: Simulador de roteamento</p>
 *
 * <p>Copyright: Copyright (c) 2004 Arx Henrique</p>
 *
 * <p>Company: RouterSoft</p>
 *
 * @author Arx Henrique
 * @version 1.0
 */
public class ShowResult
{
    private static ShowResult ref = new ShowResult( );
    public ShowResult()
    {

    }

    /**MÈtodo que escreve em uma string a LP que ser· mostrada na tela
     * Est· com um bug que n„o consegui resolver ainda
     * @author Arx Henrique
     * @version 1.2
     * @param vInicial String
     * @param vFinal String
     */
    public static void gerarLp(String vInicial, String vFinal)
    {
        lp = "MIN ";
        for(int i = 0; i < V.size(); i++)
        {
            mAdj[i][i] = 0;
        }
        for(int i = 0; i < V.size(); i++)
        {
            for(int b = 0; b < V.size(); b++)
            {
                if(i == V.size()-1 && b == V.size()-1)
                {
                    lp += mAdj[i][b] + "X" + (i+1) + (b+1) + " ";
                } else {
                    lp += mAdj[i][b] + "X" + (i+1) + (b+1) + "+ ";
                }
            }
            lp += "\n";
        }
        lp += "\n\nSUBJECT TO\n\n";
        for(int i = 0; i < V.size(); i++)
        {
            if(i != V.indexOf(vFinal))
            {
                for (int b = 0; b < V.size(); b++)
                {
                    if (b != V.indexOf(vInicial))
                    {
                        if (b == V.size()-1)
                        {
                            lp += "X" + (i+1) + (b+1);
                        } else {
                            lp += "X" + (i+1) + (b+1) + "+ ";
                        }
                    }
                }
            }
            if(i != V.indexOf(vFinal))
            lp += " = 1\n";
        }
        for(int i = 0; i < V.size(); i++)
        {
            if(i != V.indexOf(vInicial))
            {
                for (int b = 0; b < V.size(); b++)
                {
                    if (b != V.indexOf(vFinal))
                    {
                            lp += "X" + (b+1) + (i+1) + " ";
                    }
                    if((b != V.size()-1 && b != V.indexOf(vFinal)))
                    lp += "+ ";
                }
            }
            if(i != V.indexOf(vInicial))
            lp += " = 1\n";
        }
        lp += "\nEND\n";
    }

    /**FunÁ„o que alimenta a matriz que conter· as rotas
     * @author Arx Henrique
     * @version 1.1
     */
    public static void alimentaLista()
    {
        try
        {
            String sql = "select r1.des_roteador as rorigem, r2.des_roteador";
            sql += " as rdestino, l.tam_link from link as l left outer join ";
            sql += "roteador as r1 on l.id_roteador_origem = r1.id_roteador ";
            sql += "left outer join roteador as r2 on l.id_roteador_destino";
            sql += " = r2.id_roteador";

            Connection ODBConection = ConectionFactory.getConnection();
            Statement stmt = ODBConection.createStatement(ResultSet.TYPE_SCROLL_INSENSITIVE, ResultSet.CONCUR_READ_ONLY);
            ResultSet rs;
            rs = stmt.executeQuery(sql);
            String s = new String();
            s = "";
            while(rs.next())
            {
                s += rs.getString("rorigem")+"-"+rs.getString("rdestino")+"="+rs.getString("tam_link")+"\n";
            }
            parseE(s);

        } catch (NullPointerException e)
        {
            JOptionPane.showMessageDialog(null, "Ocorreu o seguinte erro:\n" + e.getMessage(), "Erro", JOptionPane.OK_OPTION);
        }
        catch (SQLException e)
        {
            JOptionPane.showMessageDialog(null, "Ocorreu o seguinte erro:\n" + e.getMessage(), "Erro", JOptionPane.OK_OPTION);
        }

    }

    /**MÈtodo que pega todos os roteadores cadastrados e joga em um ArrayList
     * @author Arx Henrique
     * @version 1.1
     */
    public static void addRoteadores()
    {
        try
        {
            String sql = "select des_roteador from roteador";

            Connection ODBConection = ConectionFactory.getConnection();
            Statement stmt = ODBConection.createStatement(ResultSet.TYPE_SCROLL_INSENSITIVE, ResultSet.CONCUR_READ_ONLY);
            ResultSet rs;
            rs = stmt.executeQuery(sql);
            V.clear();
            while(rs.next())
            {
                V.add(rs.getString("des_roteador"));
            }
        } catch (NullPointerException e)
        {
            JOptionPane.showMessageDialog(null, "Ocorreu o seguinte erro:\n" + e.getMessage(), "Erro", JOptionPane.OK_OPTION);
        }
        catch (SQLException e)
        {
            JOptionPane.showMessageDialog(null, "Ocorreu o seguinte erro:\n" + e.getMessage(), "Erro", JOptionPane.OK_OPTION);
        }
    }

    /**MÈtodo que joga na matriz de rotas os valores encontrados
     * @author Arx Henrique
     * @version 1.1
     * @param arestas String
     */
    public static void parseE(String arestas)
    {
        //inicializa matriz de adjacencias com dimensao nxn
        mAdj = new long[V.size()][V.size()];
        //inicializa
        for (int x=0; x < V.size(); x++)
        {
            for (int y=0; y < V.size(); y++)
            {
                mAdj[x][y] = infi;
            }
        }

        int i = 0;
        String aux = new String("");
        int r, s;
        float p;

        while (i < arestas.length())
        {
            if (arestas.charAt(i) != '\n')
            {
                aux += arestas.charAt(i);
            } else {
                //aux contem "v1-v2=p"
                aux = aux.trim();
                //posicao de v1 em V
                r = V.indexOf(aux.substring(0, aux.indexOf('-')).trim());
                //posicao de v2 em V
                s = V.indexOf(aux.substring(aux.indexOf('-')+1, aux.indexOf('=')).trim());
                //peso p de v1 para v2
                p = Float.parseFloat(aux.substring(aux.indexOf('=')+1).trim());
                //marca aresta (v1, v2) em mAdj
                mAdj[r][s] = (int)p;
                aux = "";
            }
                i++;
        }
    }

    /**Imprime a matriz contendo os valores no console
     * somente para fins de debug
     * @author Arx Henrique
     * @version 1.1
     */
    public static void printMAdj()
    {
        for (int i=0; i < V.size(); i++)
        {
            System.out.println('\n');
            for (int j=0; j < V.size(); j++)
            {
                if (mAdj[i][j] != infi)
                {
                    System.out.print(" " + mAdj[i][j]);
                } else {
                    System.out.print(" " + "-");
                }
            }
        }
        System.out.print("\n");
    }

    /**MÈtodo que calcula a distancia de todos os roteadores a partir de
     * um roteador principal
     * @author Arx Henrique
     * @version 1.5
     * @return boolean
     */
    public static boolean buildL()
    {
        try
        {
            //posicao de u na matriz de adj
            int pos = V.indexOf(u);
            //L tem dimensao n
            L = new long[V.size()];

            for (int i=0; i < V.size(); i++)
            {
                L[i] = mAdj[pos][i];
                if(L[i] != infi)
                {
                    System.out.println(u + " -- " + V.get(i).toString());
                    rota = u + " -- " + V.get(i).toString();
                    R.add(rota);
                }
            }
            System.out.println();
            //L(u)
            L[pos] = 0;
        } catch (IndexOutOfBoundsException e)
        {
            System.out.println(u + " nao esta em V");
            return false;
        }
        return true;
    }

    /**MÈtodo que imprime a matriz para debug somente com as rotas
     * @author Arx Henrique
     * @version 1.0
     */
    private static void printL()
    {
        System.out.print("\n");
        for (int i=0; i < V.size(); i++)
        {
            if (L[i] != infi)
            {
                System.out.print(" " + L[i]);
            } else {
                System.out.print(" -");
            }
        }
    }

    /**MÈtodo que imprime as rotas de um roteador x para todos os outros
     * roteadores
     * @author Arx Henrique
     * @version 1.2
     */
    private static void printL2()
    {
        System.out.print("\n");
        for (int i = 0; i < V.size(); i++)
        {
            if (L[i] != infi)
            {
                System.out.println("L(" + V.get(i) + ")= " + L[i]);
                resultado += "L(" + V.get(i) + ")= " + L[i] + "\n";
            } else {
                System.out.println("L(" + V.get(i) + ")= infi");
                resultado += "L(" + V.get(i) + ")= Sem rota para o host\n";
            }
        }
        if(L[V.indexOf(destino)] == infi)
        {
            System.out.println("Dist‚ncia de " + u + " atÈ: " + V.get(V.indexOf(destino)) + " = Sem rota para o host");
            resultado += "Dist‚ncia mÌnima de " + u + " atÈ: " + V.get(V.indexOf(destino)) + " = Sem rota para o host";
        } else {
            System.out.println("Dist‚ncia de " + u + " atÈ: " + V.get(V.indexOf(destino)) + " = " + L[V.indexOf(destino)]);
            resultado += "Dist‚ncia mÌnima de " + u + " atÈ: " + V.get(V.indexOf(destino)) + " = " + L[V.indexOf(destino)] + "\n";
        }
    }

    /**MÈtodo que retorna a LP para ser mostrado na tela
     * @author Arx Henrique
     * @version 1.0
     * @return String
     */
    public static String getLp()
    {
        return lp;
    }

    /**MÈtodo que retorna as rotas de um roteador x para todos os outros
     * que ser· mostrado na tela
     * @author Arx Henrique
     * @version 1.0
     * @return String
     */
    public static String getResultado()
    {
        return resultado;
    }

    /**MÈtodo que executa o algoritmo de Dijkstra
     * @author Arx Henrique
     * @version 1.7
     * @param vInicial String
     * @param vFinal String
     * @param debug boolean
     */
    public static void run(String vInicial, String vFinal, boolean debug)
    {
        T.clear();
        System.out.println("Distancia a partir de " + vInicial);
        resultado = "Distancia a partir de " + vInicial + "\n";

        u = vInicial;
        destino = vFinal;

        //constroi L(v)
        if (!buildL()) return;

        T.add(u); // T <- {u}
        if (debug)
        {
            for (int k = 0; k < V.size(); k++)
            {
                System.out.print(" " + V.get(k));
            }
        }

        while (!T.containsAll(V))
        {
            if (debug)
            {
                printL();
            }
            String vLinha = findMinL();
            T.add(vLinha);
            updateL(vLinha);
        }
        if (debug)
        {
            System.out.println("\nfim");
        } else {
            printL2();
        }
    }

    //---------------------------------------------------------------

    private static void printV()
    {
        System.out.print("\n");
        for (int k=0; k < V.size(); k++)
        {
            System.out.print(" " + V.get(k));
        }
    }

    public static void defineRota()
    {
        /*int pos = 0;
        for (int i = 1; i < (R.size()); i++)
        {
            String rota = (String) R.get(0);
            String contains = (String) R.get(i);
            if (!rota.substring(0).equals(contains.substring(0)))
            {
                pos++;
            }
            System.out.println("i: = " + i);
        }
        System.out.println("pos " + pos);
        for(int i = 0; i < R.size(); i++)
        {
            if(R.size() < pos+1 && i != pos)
            {
                String rota = (String) R.get(pos);
                String contains = (String) R.get(i);
                if(rota.substring(0).equals((String)contains.substring(4)))
                {
                    R.remove(i);
                }
            }
        }*/
        System.out.println(R.toString());
//        System.out.println(pos);
    }

    private static void printT()
    {
        System.out.print("\n");
        for (int k=0; k < T.size(); k++)
        {
            System.out.print(" " + T.get(k));
        }
    }

    /**MÈtodo que atualiza o ArrayList contendo as rotas
     * @author Arx Henrique
     * @version 1.0
     * @param vLinha String
     */
    private static void updateL(String vLinha)
    {
        int i;
        //V2 = V
        ArrayList V2 = new ArrayList(V);
        //remove T de V = V2
        for (i=0; i < T.size(); i++)
        {
            V2.remove(V2.indexOf(T.get(i)));
        }
        for (i=0; i < V2.size(); i++)
        {
            String vaux = (String)V2.get(i);
            long w = L[V.indexOf(vLinha)] + mAdj[V.indexOf(vLinha)][V.indexOf(vaux)];
            if  (w < L[V.indexOf(vaux)])
            {
                L[V.indexOf(vaux)] = w;
                System.out.print(vLinha + " - " + vaux);
                rota = vLinha + " - " + vaux;
                R.add(rota);
            }
        }
    }

    /**Retorna v n„o pertencente a T tal que L(v) seja mÌnimo
     * @author Arx Henrique
     * @version 1.2
     * @return String
     */
    private static String findMinL()
    {
        int i;
        //V2 = V
        ArrayList V2 = new ArrayList(V);
        //remove T de V = V2
        for (i=0; i < T.size(); i++)
        {
            V2.remove(V2.indexOf(T.get(i)));
        }
        long pmin = infi;
        String v = "";

        //procuro em V2 o L(v) minimo
        for (i=0; i < V2.size(); i++)
        {
            String vaux = (String)V2.get(i);
            if (L[V.indexOf(vaux)] <= pmin)
            {
                v = vaux;
                pmin = L[V.indexOf(vaux)];
            }
        }
        return v;
    }

    private static ArrayList V = new ArrayList();
    private static ArrayList T = new ArrayList();
    private static ArrayList R = new ArrayList();
    private static final int infi = 100000000;
    private static long mAdj[][];
    private static long L[];
    private static String u;
    private static String resultado;
    private static String destino;
    private static String lp = "MIN ";
    private static String rota = "";
}