Arista.java

import java.util.*;
import java.util.Random;
import java.util.ArrayList;
import java.util.Iterator;
import java.lang.Math;
import java.io.*;//io writter crear Archivo
public class Arista {
    //propiedades de la arista
    public int desde;
    public int hasta;
    //random para toda la clase
    public static final Random r = new Random();
    /**Constructor
       para asignar a una arista su identificador de que grafo y hasta que grafo se dirige
    */
    public Arista(int d, int h) {
    //arista dirijido desde a donde
    this.desde = d;
    this.hasta = h;
    }
    /**
       Metodo que para identificar la arista su punto de inicio hasta su punto final
    */
    public String toString() {
    return  this.desde + "-" + this.hasta ;
    }


    /**Metodo Genera
       recibe n = numero de nodos  p= densidad
       crea una lista de aristas
       despues a esa lista le agrega las aristas generadas(connectadas) a vertices
    */
    public static ArrayList<Arista> genera(int n, double p) {
    ArrayList<Arista> grafo = new ArrayList<Arista>();
    //genera las conexiones de mi grafo
    for (int i = 0; i < n; i++) {//recorre igual a los vertices asignando aristas al azar
        for (int j = i + 1; j < n; j++) {//se suma uno para que la arista no repita su punto de origen (vertices anteriores)
        if (Arista.r.nextDouble() <= p) {//si el numero random generado es menor igual a la densidad se genera la conexion
            grafo.add(new Arista(i, j));//se agrega una arista a mi lista de aristas de mi grafo
        }
        }
    }
    return grafo;//regresas una lista de aristas
    }
    /**Metodo que imprime listas
       recibe una lista y la imprime
    */
    public static void imprime(ArrayList lista) {
    Iterator i = lista.iterator();//
    while (i.hasNext()) {
        System.out.println(i.next());
    }
    return;
    }
    /**Calcula la cota inferior = grados de los nodos sumados den total de aristas (cantidad de vecinos sumando)
       recibe numero de nodos y numero de aristas recorre la lista agrega un arreglo que contiene la cantidad
       de vecinos que tiene esto es el grado de el vertice crea una seleccion de nodos a traves de los que tengan
       la mayor cantidad de vecinosy si la suma de estos vecinos es igual o mayor al total de aristas ya se tiene
       el conjunto de la solucion inicial
    */
    public static int cotaInferior(ArrayList<Arista> grafo, int n, int m) {
    int cuantos = 0, acumulado = 0;
    int[] grado = new int[n];

    for (int i = 0; i < n; i++) {
        grado[i] = 0;
    }
    //recorre la lista de aristas de mi grafo
    Iterator<Arista> it = grafo.iterator();

    //recorre cada arista y el indice de sus propiedades(desde-hasta) les agrega vecinos a la lista de nodos
    while (it.hasNext()) {//hasta que se acabe :P

        Arista a = it.next();//el siguiente lo toma como arista a
        //le agrega grados a los nodos que contiene dicha arista
        grado[a.desde]++;
        grado[a.hasta]++;
    }

    /**Selecciona los conjuntos de vertices que completan la condicion de aristas totales
     */
    while (acumulado <= m) {//acumulado menor igual que aristas las ordena de acuerdo al grado
        int max = 0;
        int seleccionado = -1; // no posible
        for (int i = 0; i < n; i++) {
        if (grado[i] > max) {//si es mayor
            seleccionado = i;//lo selecciona para ponerlo en el conjunto (seleccionado)
            max = grado[i];//el maximo toma el valor del grado anterior
        }
        }
        cuantos++;
        //la cantidad de aristas acumulada es la cantidad de aristas que deben cubrirse osea el tota pero no sera la optima
        acumulado += max;
        //ahora modificamos el grado (cantidad de vecinos que posee) a 0 para que contemos ahora el siguiente mas grande
        grado[seleccionado] = 0;
    }
    return cuantos;//cuantos vertices (nodos) asignamos al conjunto seleccionado
    }

    /**
       Crea el conjunto de solucion inicial
       lo mismo que el procedimiento de la cota inferior pero en lugar de ordenarlo
    */
    public static ArrayList<Integer> inicial(ArrayList<Arista> grafo) { //lista de solucion inicial

    ArrayList<Integer> cubierta = new ArrayList<Integer>();//lista de la cubierta (conjunto seleccionado como solucion inicial)
    ArrayList<Arista> copia = new ArrayList<Arista>();//lista de aristas copia de la cubierta
    //de nuevo recorre el grafo
    Iterator<Arista> it = grafo.iterator();
    while (it.hasNext()) {
        copia.add(it.next());//y lo agrega a la copia
    }
    //si el conjunto es mayor a 0
    while (copia.size() > 0) {
        int largo = copia.size();//se toma el largo del arreglo de aristas
        //System.out.println("Faltan " + largo + " aristas por cubrir.");//el largo de las aristas
        /**SELECCIONA*/
        //selecciona un vertice al azar y lo toma en el conjunto seleccion
        int seleccion = Arista.r.nextInt(largo);
        //System.out.println(seleccion);
        //de acuerdo a la posicion del elemento seleccionado verifica el arista
        Arista a = copia.get(seleccion);
        //cualquier vertice tenga este arista podra formar parte del conjunto de seleccion
        if (Arista.r.nextBoolean()) {
        seleccion = a.desde;
        } else {
        seleccion = a.hasta;
        }
        //crea la cubierta con los elementos seleccionados
        cubierta.add(new Integer(seleccion));
        it = grafo.iterator();
        //lista de aristas eliminados
        ArrayList<Arista> eliminados = new ArrayList<Arista>();
        //agrega los eliminados tanto los vertices hasta y desde  a la lista
        while (it.hasNext()) {
        a = it.next();
        //si los aristas forman parte de la seleccion los agrega a la lista eliminados
        if (a.desde == seleccion || a.hasta == seleccion) {
            eliminados.add(a);
        }
        }
        copia.removeAll(eliminados); //de la copia quita los eliminados
    }

    return cubierta;//regresa la cubierta seleccionada como solucion inicial
    }
    /** Metodo determina cota superior esta tiene que ser factible
     */
    public static int cotaSuperior(ArrayList<Arista> grafo) {
    return (Arista.inicial(grafo)).size();//el tamaño de la cubierta de una solucion inicial :3
    }
    /**funcion objetivo
     */
    public static int objetivo(ArrayList<Integer> solucion) {
    //el tamaño minimo de aristas esto seria el tamaño  minimo de una solucion
    return solucion.size();
    }
    /**
       Determina si la solucion es factible
       Recibe la lista del conjunto inicial y la lista de aristas del grafo
    */
    public static boolean factible(ArrayList<Integer> solucion, ArrayList<Arista> grafo) {
    Iterator<Arista> it = grafo.iterator();//recorre la lista de aristas del grafo
    while (it.hasNext()) {
        Arista a = it.next(); //
        if (!(solucion.contains(new Integer(a.hasta)) || solucion.contains(new Integer(a.desde)))) {
        //si la solucion no contiene(cubre) todas las aristas regresa un false no es factible
        return false;
        }
    }
    return true; //y si si pues si :D
    }
    /**Recibe una solucion inicial
       Regresa el tamaño de la modificacion
    */
    public static ArrayList<Integer> modificacion(ArrayList<Integer> solucion, int n, boolean fact)//recibe solucion inicial
    {
    ArrayList<Integer> nueva = new ArrayList<Integer>();//copia de la solucion
    int k = solucion.size();//tamanio de esta
    int brinca = (fact || k == n) ? Arista.r.nextInt(k) : -1;//.-.
    //si es factible o es igual al total de vertices quita un elemento al azar
    for (int i = 0; i < k; i++) {
        if (i != brinca) {
        nueva.add(solucion.get(i));//agrega un nuevo vertice a la solucion
        }
    }
    if (!fact && k < n) {//si no es factible y el tamaño de la solucion
        while (true) {
        Integer agrega = new Integer(Arista.r.nextInt(n));//agrega
        if (nueva.indexOf(agrega) < 0) {
            nueva.add(agrega);
            break;
        }
        }
    }

    return nueva;//regresa la nueva
    }

    /**Busqueda tabu evita que se repitan los datos de la busqueda local
       asi elimina reincidencias esta funcion aun no funciona :(
     */
    public static boolean tabu (ArrayList<ArrayList<Integer>>cola, ArrayList<Integer> solucion, int iter)
    {
    cola = null;
    while(iter>0)
        {
        if(cola.contains(solucion))
            {
            //cont++;modifica();
            return false;
            }
        else
            {
            cola.add(solucion);
            if (cola.size()>=iter)
                {
                cola.remove(cola.get(0));
                }
            }
        }
    return true;
    }
    /**Metaheurísticade genetica Basica
       Incluye metodos
       -poblacion
       -cromosoma
       -cubierta
       -mutacion
       -nacimiento
       -ruleta para la seleccion aleatoria :| <- aun no funciona :(
     */
    //genetica <3

    /**
       Metodo Poblacion
       recibe el grafo y el tamaño de la pobacion
       genera una poblacion a partir de soluciones iniciales
     */
    // genera una poblacion inicial
    public static ArrayList<ArrayList<Integer>> poblacion(ArrayList <Arista> grafo,int tam)//verif
    {
    ArrayList<ArrayList<Integer>> lista= new ArrayList<ArrayList<Integer>>();//lista de listas de enteros
    while(lista.size()<=tam)//mientras que la lista aun sea menor al tamaño
        {
        lista.add(Arista.inicial(grafo));//agrega una solucion inicial a la lista de poblacion
        }
    //System.out.println("Poblacion @_@");//flag
    //Arista.imprime(lista);//imprime dicha lista //flag
    return lista;//regresa la lista para utilizarla
    }
    //cromosoma
    /**
       metodo cromosoma transforma la solucion inicial en binario
       recibe una solucion inicial (conjunto de vertices que forman la cubierta)
       y la cantidad total de vertices

     */
    public static ArrayList<String> cromosoma(ArrayList<Integer> seleccion, int cantidad) //cantidad total de vertices
    {
    ArrayList<String> ref = new ArrayList<String>();//cadena de caracteres 0 y 1 para representarlo
    for(int i=0;i<cantidad;i++)//recorre el arreglo
        {
        if(seleccion.contains(i))//si contiene el numero referenciado al indice
           {
               ref.add("1");//agrega un uno
           }
           else
               ref.add("0");//si no ... un cero
        }
    //Arista.imprime(ref);
        return ref;//regresa el patron de referencia en binario
    }

    /**metodo cubierta
       recibe la referencia en binario de la solucion (conjunto de vertices que forman la cubierta)

     */
    public static ArrayList<Integer> cubierta (ArrayList<String> cromosoma)
    {
    ArrayList<Integer> selection= new ArrayList<Integer>();
    int pos =0;
    for (int i=0;i<cromosoma.size();i++)
        {
        if((cromosoma.get(i)).equals("1"))//si es igual a 1
            selection.add(pos);//agrega la "iteracion" actual a el conjunto cubierta
        pos+=1;
        }
    //System.out.println("cubierta");//flag
    //Arista.imprime(selection);//flag
    return selection;//regresa el conjunto
    }
    /**
       metodo mutacion
       recibe una poblacion de soluciones iniciales
       el total de vertices y el grafo
       elije un individuo a cambiar atravez del metodo ruleta que selecciona
    */

    public static void mutacion(ArrayList<ArrayList<Integer>>poblacion,int verticestotales,ArrayList<Arista> g)
    {
    int individuo = ruleta(poblacion);
    ArrayList<Integer> id = poblacion.get(individuo);//selecciono el individuo que voy a mutar
    ArrayList<String> cr =cromosoma(id,verticestotales);
    int ubic= Arista.r.nextInt(verticestotales);
    if (cr.get(ubic)== "0")//si el individuo seleccionado es igual a 0
        {
        cr.set(ubic,"1");
        }
    else
        {
        cr.set(ubic,"0");
        }
    ArrayList <Integer> mutante = Arista.cubierta(cr);
    //int objetivo = Arista.objetivo(mutante);
    boolean fact = Arista.factible(mutante,g);
    if(fact==true )
        poblacion.add(mutante);
    return;
    }
    /**
       metodo ruleta elije un elemento al azar similando la funcion de una ruleta
     */

    public static int ruleta (ArrayList<ArrayList<Integer>>poblacion)
    {
    int i=0;
    int[] ruleta = new int[poblacion.size()];//se crea un arreglo del tamaño de la poblacion
    int suma = 0;//suma en ceros
    //System.out.println(poblacion.size(); //para esta funcion se nesecita que la funcion matanza este funcionando al 100%
    for(i=0;i < poblacion.size();i++)//recorrer el arreglo
        {
        ruleta[i] = (poblacion.get(i)).size();//se realiza la suma de los elementos y cual es el valor de c/u
        suma = suma + ruleta[i];
        //System.out.println(i + " - " +ruleta[i] + " "+suma +" " );
        }
    int corte = Arista.r.nextInt(suma);//seleccion de un num al azar
    suma = 0;

    for( i=0;i < poblacion.size();i++)
        {
        suma = suma + ruleta[i];
        if(corte <= suma){
            //  System.out.println("Estee> " +i);
            //realiza la busqueda en los elementos y el primero que satisfaga la suma de el numero elegido sera el elemento seleccionado
            break;
        }
        }
    return i;//regresa un elemento de la poblacion
    }
    /**
       metodo nacimiento se refiere al metodo cruzamiento en si el algoritmo realiza un cruze entre los cromosomas
        de un elemento padre y un madre asi obtenemos un elemento hija y uno hijo y si los elementos son
    factibles se agregan a la poblacion
    este metodo aun no funciona :(
     */

    public static void nacimiento(ArrayList<ArrayList<Integer>>poblacion,int n,ArrayList<Arista> g)
    {
    ArrayList<String> papa = cromosoma(poblacion.get(ruleta(poblacion)),n);
    ArrayList<String> mama = cromosoma(poblacion.get(ruleta(poblacion)),n);

    ArrayList<String> hija = new ArrayList<String>();
    ArrayList<String> hijo = new ArrayList<String>();
    ArrayList<String> mich = new ArrayList<String>();

    Iterator<String> pa = papa.iterator();
    Iterator<String> ma = mama.iterator();

    int i=0;
    int pos = (int)(Math.random()*(n-1)+1);
    while(pa.hasNext()){
        if(i<pos){
        hija.add(pa.next());//hija con primera corte de papa
        i++;
        }
        else{
        mich.add(pa.next());//segunda corte de papa
        }
    }
    i=0;
    while(ma.hasNext()){
        if(i<pos){
            hijo.add(ma.next());//hijo con primer corte de mama
            i++;
        }
        else{
            mich.add(ma.next());//segundo corte de mama
        }
        }

    Iterator<String> mita = mich.iterator();//primero esta la micha papa despues mama :3
    i=0;
    while(mita.hasNext()){
        if(i<(mich.size()/2)){//la mitad de el ArrayList

        hijo.add(mita.next());//papa va para el hijo
        i++;
        }
        else{
        hija.add(mita.next());//mama va para hija
        }
    }
    ArrayList <Integer> nina= Arista.cubierta(hija);
    ArrayList <Integer> nino= Arista.cubierta(hijo);
    //int objetivo = Arista.objetivo(nina);
    boolean fact = Arista.factible(nina,g);
    //System.out.println(fact);
    if(fact==true )
        poblacion.add(nina);
    fact = Arista.factible(nino,g);
    //System.out.println(fact);
    if(fact==true )
        poblacion.add(nino);
    return ;
    }
    /**
       metodo matanza devuelve las mejores soluciones basadas en la lista de la poblacion
       ordenadas asi en lugar de devolver toda la poblacion primero la devuelve al tamaño inicial
       y toma la mitad ultima mitad y la devuelve
     */
    public static ArrayList<ArrayList<Integer>> matanza(ArrayList<ArrayList<Integer>>poblacion)
    {
    int tam=poblacion.size();

        for(int i = 0; i<tam;i++)
            {
        Collections.sort((ArrayList<Integer>)poblacion.get(i));
        }

    ArrayList<ArrayList<Integer>> pob= new  ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> fob = new ArrayList<Integer>();
    //System.out.println("no repeat .l.");
    for(int i=0;i<tam;i++){
        if(!pob.contains(poblacion.get(i))){
        pob.add(poblacion.get(i));
        }
    }

    //ordenar de menor funcion objetivo a mayor
    //crear una clase llamada solucion -.- contenga funcion objetivo y la misma para futuras mejoras
        return pob;
    }
    /**
       metodo generacion manda llamar a todos los metodos del algoritmo heuristico de genetica basica
       recibe la lista de aristas de coneccion (grafo)y el tamaño de la poblacion de las generaciones
     */
    public static void generacion(ArrayList<Arista> grafo,int tam,int cruz,int mut)
    {
    ArrayList<ArrayList<Integer>> pob = poblacion(grafo,tam);
    int n=pob.size();
    for(int i=0;i<(int)Math.floor(tam * cruz);i++)
        {
        Arista.nacimiento(pob,n,grafo);
        for (int m=0;m<(int)Math.floor(tam * mut);m++)
            {
            Arista.mutacion(pob,n,grafo);
            }
        }
    Arista.matanza(pob);
    //Arista.imprime(pob);
    return;
    }

    /**busqueda con algoritmo  colonia de hormigas
       metodo aun no funciona ;(
     */
    /*tabla de feromonas ... hastable
      mejor Solucion
      feromona = solucion mejor y vale un poquito double*
      alguien mas ==solucion  es buena solucion feromona +poquito;
      evaporacion
      ruleta para seleccion
      soltar feromona donde se mejora
      moviendo por si solo


      //busqueda**/
    public static ArrayList<Integer> busqueda(ArrayList<Arista> grafo, int n,int it,int re,int temperact, double enfriamiento) {
    ArrayList<Integer> mejorSol = null;
    //  int intentos =0;
    //boolean TAB;//busqueda tabu*
    //define la mejor solucion como nula para que cualquiera pueda mejorarla
    int mejorObj = n;//tamaño de la cubierta inicial seria el total de nodos en el grafo idem
    ArrayList<Integer> lista = new ArrayList<Integer>();

    for (int reinicio = 0; reinicio < re; reinicio++) {//pasos de reinicio
        ArrayList<Integer> solucion = Arista.inicial(grafo);//solucion inicial
        int obj = Arista.objetivo(solucion);//objetivo de solucion
        //temperact=1000;//busqueda recocido simulado
        for (int iter = 0; iter < it; iter++) {//iteraciones de comparar
        boolean fact = Arista.factible(solucion, grafo);//la solucion es factible
        ArrayList<Integer> otrasolucion = modificacion(solucion, n, fact); //modifica la solucion inicial a otra solucion
        boolean otraFact = Arista.factible(otrasolucion, grafo);//verifica que sea factible
        int otraObj = Arista.objetivo(otrasolucion);//el objetivo de esta
        int temp= mejorObj - obj;//busqueda recocido simulado
        if (otraFact && otraObj <= obj) {//si la otra es factible y el objetivo es menor igual
            solucion = otrasolucion;//ahora cambian de papel
            obj = otraObj;
            fact = otraFact;
            try{
            if(Arista.r.nextDouble() <= Math.exp(temp/temperact))//busqueda recocido simulado
            {
                temperact*= enfriamiento;
                lista.add(otraObj);//agrega a la lista la funcion objetivo
                //System.out.println("RS "+ otraObj+ (fact ? "  factible" : "  no factible"));
            }
            }
            catch(Exception e)
            {
                System.out.println("BYZERO"+e+"var: temperact FAIL ");

            }
            //el obj definir el candidato ._.

            if (obj < mejorObj) {//si es mejor que el mejor objetivo
            mejorObj = obj;
            mejorSol = new ArrayList<Integer>();//la agrega como mejor solucion
            Iterator<Integer> ve = solucion.iterator();
            while (ve.hasNext()) {
                mejorSol.add(ve.next());
            }
            }
        }
        lista.add(mejorObj);//agrega la mejor la minima cobertura
        //System.out.println(reinicio + " " +iter + " " + obj + " " + (fact ? "factible" : "no factible")) ;
        }
    }
    //Arista.imprime(lista);
    return mejorSol;//regresa la mejor solucion
    }
    public static void main(String[] args) {//main

    File archivo = null;
        FileReader fr = null;
        BufferedReader br = null;
        String linea = null;
    int n=0,d=0,h=0; //num de vertices/ hasta /desde
    double p= 0.0;//densidad
    ArrayList<Arista> grafo = new ArrayList<Arista>();
    //Cargamos el archivo de la ruta relativa
    archivo = new File(args[0]);
        try {
        //Cargamos el objeto FileReader
            fr = new FileReader(archivo);
        //Creamos un buffer de lectura
        br = new BufferedReader(fr);

        //Leemos hasta que se termine el archivo
        while ((linea = br.readLine()) != null) {
        //Presentamos los datos
        //                System.out.println(linea);//imprime

        if(linea.indexOf("-") >= 0)
            {
            //entra cuando hay una coma en el string
            d = Integer.parseInt(linea.substring(0,linea.indexOf("-")));
            h = Integer.parseInt(linea.substring(linea.indexOf("-")+1));
            grafo.add(new Arista(d,h));
            }
        }
    Arista.imprime(grafo);
    }
    //Capturamos las posibles excepciones
         catch (FileNotFoundException e){
        System.out.println("FILENOTFOUND");
        //si no encuentra el archivo ejecutara
        //if not arguments name the file
        n = Integer.parseInt(args[0]);//vertices
        p = Double.parseDouble(args[1]);//densidad
        grafo = Arista.genera(n, p);//genera las conexiones
        Arista.imprime(grafo);//imprime la lista

        System.out.println("numde vertices "+n);
        System.out.println("numde densidad "+p);
        try{
        FileWriter test = new FileWriter("instancia.txt");
        PrintWriter pw =new PrintWriter(test);
        for(int i=0;i<grafo.size();i++){
            String algo =(grafo.get(i)).toString();
        pw.println(algo);
        }
        test.close();
        }
        catch(Exception e3)
        {
            System.out.println("D:->"+e);
        }
    } catch (IOException e){
        System.out.println("fybbyIO");
    }
    finally {
        try {
        if (fr != null) {
        System.out.println("Ha finalizado la lectura del archivo");
        fr.close();

        }
        }catch (Exception e2) {
                e2.printStackTrace();
        }
    }
    int m = grafo.size();//m=tamaño de la lista de aristas generadas
    System.out.println("Se generaron " + m + " aristas.");//lo imprime
    System.out.println("#instancia");
    //Arista.imprime(grafo);//imprime la lista
    //imprime los rangos entre cuales estara la solucion optima
    System.out.println("Cota inferior: " + Arista.cotaInferior(grafo, n, m) + ".");//imprime la cota inferior de la lista de aristas
    System.out.println("Cota superior: " + Arista.cotaSuperior(grafo) + ".");//imprime la cota superior de la lista de aristas
    Arista.busqueda(grafo, n ,5 ,7,1000,0.3);//parametros=grafo,numero de vertices,iteraciones,reinicios,temperaturaactual,tasa de enfriamient
    Arista.generacion(grafo,10,5,5);//parametros=grafo taamaño de poblacion cant de cruzamientos y mutaciones
    return;
    }
}