jueves, 28 de noviembre de 2013

TAD e Implementación de Grafos en Java

A continuación dejo el TAD(Tipo abstracto de datos) genérico o interface en Java de un grafo dirigido y la implementación con colecciones y una matriz de costos.

public interface Grafo <E>{
    //Modificadoras
    void insVertice(E dato);
    void insArco(int o, int d,int dato) throws LimiteException ;
    void elimArco(int o, int d)throws LimiteException ;
    
    //Analizadoras
    int costoArco(int x, int y)throws LimiteException ;
    List<E> sucesores(int v)throws LimiteException ;
    E infoVertice(int v)throws LimiteException ;
    int ordenGrafo();
    int inf=999999;

}

public class GrafoCol<E> implements Grafo<E> {
    List<E> vertices;
    int aristas [][];
    
    public GrafoCol()
    {
        vertices = new ArrayList<>();
        aristas = new int[100][100];
        for (int i = 0; i < aristas.length; i++) {
            for (int j = 0; j < aristas.length; j++) {
                if(i!=j)
                    aristas[i][j] = inf;
                //De resto se llena automáticamente de ceros(en este caso la diag ppal)
                    
            }
        }
    }

    @Override
    public void insVertice(E dato) {
        vertices.add(dato);
                
    }

    @Override
    public void insArco(int o, int d, int dato) throws LimiteException {
        if(o>= ordenGrafo() || d>= ordenGrafo())
            throw new LimiteException("Te pasaste");
        aristas[o][d] = dato;
    }

    @Override
    public void elimArco(int o, int d) throws LimiteException {
        if(o>= ordenGrafo() || d>= ordenGrafo())
            throw new LimiteException("Te pasaste");
        aristas[o][d] = inf;
    }

    @Override
    public int costoArco(int x, int y) throws LimiteException {
        if(x>= ordenGrafo() || y>= ordenGrafo())
            throw new LimiteException("Te pasaste");
        return aristas[x][y];
    }

    @Override
    public List<E> sucesores(int v) throws LimiteException {
        List<E> res = new ArrayList<>();
        if(v>= ordenGrafo())
            throw new LimiteException("WHY");
        for (int i = 0; i < ordenGrafo(); i++) {
            if(i!=v && aristas[v][i]!= inf)
                res.add(infoVertice(i ));
                           
        }
        return res;
    }

    @Override
    public E infoVertice(int v) throws LimiteException {
        return vertices.get(v);
    }

    @Override
    public int ordenGrafo() {
        return vertices.size();
    }
    

}
public class LimiteException extends Exception {
    public LimiteException(String msg)
    {
        super(msg);
    }

}