Skip to main content
6 de 6
Commonmark migration

Grafos: maior caminho

Bom, como trabalho da faculdade, tenho que criar um algoritmo que, dado certo arquivo com x números, seja capaz de verificar qual a maior sequência de números que, em base 6, respeitem as as seguintes regras:

  1. A sequência deve ser crescente
  2. De um número para outro da sequência, somente um dígito pode mudar
  3. Todos os números da sequência tem que ter o mesmo número de digitos (15-->10015 não é válido)

Um exemplo seria:

O arquivo contém os números 782, 229, 446, 527, 874, 19, 829, 70, 830, 992, 430 e 649.

Ou seja, em base 6: 3342, 1021, 2022, 2235, 4014, 31, 3501, 154, 3502, 4332, 1554 e 3001.

Portanto, a maior sequência respeitando essas regras seria: 649, 829 e 830, que corresponde a 3001, 3501 e 3502 em base 6.

Certo, os arquivos não são assim tão simples, há arquivos que chegam a ter até 100.000 números, portanto, criei um grafo. Eu tentei tanto com matriz como com lista de adjacências. Adicionar os vértices e as arestas (ou seja, quais são os números que respeitam as regras para um número x) não foi um problema, meu problema é caminhar no grafo, pois pesquisando na internet só achei caminhamento mínimo, mas o que eu preciso é: achar o maior caminho.

Tentei com DFS mas o resultado não é o que eu quero.

Meu código é o seguinte:

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class DirectedGraphList
{
    private class Vertice
    {
        private String item;
        private boolean Visitado;
        private ArrayList<Vertice> lst = new ArrayList<Vertice>();

        public Vertice(String item) {
            this.item = item;
        }
        public String getItem() {
            return this.item;
        }
        public void setItem(String item) {
            this.item = item;
        }
        public void addAdjacent(Vertice v) {
            if (!lst.contains(v))
                lst.add(v);
        }
        public ArrayList<Vertice> getAdjacents() {
            return lst;
        }
        public Vertice getAdjacent(int i) {
            Vertice res = null;
            if ((i >= 0) && (i < lst.size()))
                res = lst.get(i);
            return res;
        }
        public int getDegree(){
            return lst.size(); 
        }
    }

    private ArrayList<Vertice> vert;

    public DirectedGraphList() {
        vert = new ArrayList<Vertice>();
    }

    private Vertice searchVerticeRef(String item)
    {
        Vertice res = null;
        int i;

        for (i = 0; ((i < vert.size()) && !vert.get(i).getItem().equals(item)); i++);

        if (i < vert.size())
            res = vert.get(i);

        return res;
    }

    public void addVertice(String item)
    {
        if (searchVerticeRef(item) == null) 
        {
            Vertice novo = new Vertice(item);
            vert.add(novo);
        }
    }

    public void addEdge(String strOrig, String strDest)
    {
        Vertice vAux1 = searchVerticeRef(strOrig);
        Vertice vAux2 = searchVerticeRef(strDest);

        if (vAux1 == null)
            throw new IllegalArgumentException("Aresta origem invalida: " + strOrig);
        else if (vAux2 == null)
            throw new IllegalArgumentException("Aresta destino invalida: " + strDest);
        else
        {
            vAux1.addAdjacent(vAux2);
        }
    }

    public int getNumVertices() {
        return vert.size();
    }

    public int getDegree(String vertice)
    {
        int i, j, c = 0;
        Vertice v = searchVerticeRef(vertice);
        if (v != null)
        {
            // grau de saida
            c += v.getDegree();

            // grau de entrada
            for (i = 0; i < vert.size(); i++)
            {
                if (!vert.get(i).getItem().equals(vertice))
                {
                    for (j = 0; j < vert.get(i).getDegree(); j++)
                    {
                        if (vert.get(i).getAdjacent(j).getItem().equals(vertice))
                            c++;
                    }                    
                }
            }
        }
        return c;
    }

    public ArrayList<String> getAllAdjacents(String vertice)
    {
        ArrayList<String> res = null;
        Vertice v = searchVerticeRef(vertice);
        if (v != null)
        {
            res = new ArrayList<String>();
            for (int j = 0; j < v.getDegree(); j++)
                res.add(v.getAdjacent(j).getItem());
        }
        return res;
    }

    public ArrayList<String> getSources()
    {
        ArrayList<String> res = new ArrayList<String>();
        boolean checked;
        String vertice;

        for (int k=0; k<vert.size(); k++)
        {
            vertice = vert.get(k).getItem();

            checked = false;
            for (int i=0; i<vert.size(); i++)
            {
                for (int j=0; j<vert.get(i).getDegree(); j++)
                {
                    if (vert.get(i).getAdjacent(j).getItem().equals(vertice))
                    {
                        checked = true;
                        break;
                    }
                }
            }

            if (!checked)
                res.add(vertice);
        }
        return res;
    }

    public ArrayList<String> getSinks()
    {
        ArrayList<String> res = new ArrayList<String>();

        for (int i=0; i<vert.size(); i++)
        {
            if (vert.get(i).getAdjacents().isEmpty())
                res.add(vert.get(i).getItem());
        }
        return res;
    }

    public void showInfo()
    {
        System.out.print("V = { ");
        for (int i = 0; i < vert.size()-1; i++)
            System.out.printf("%s, ", vert.get(i).getItem());
        System.out.printf("%s }\n", vert.get(vert.size()-1).getItem());

        ArrayList<String> arestas = new ArrayList<String>();
        for (int i = 0; i < vert.size(); i++)
            for (int j = 0; j < vert.get(i).lst.size(); j++)
                arestas.add(String.format("(%s, %s)", vert.get(i).getItem(), vert.get(i).getAdjacent(j).getItem()));

        System.out.print("E = {\n");
        if (!arestas.isEmpty()) {
            System.out.printf("      %s", arestas.get(0));

            for (int i = 1; i < arestas.size(); i++)
                System.out.printf(",\n      %s", arestas.get(i));
        }
        System.out.println("\n    }");
    }
    public static void criaArray(ArrayList<Integer> a,String nome) throws FileNotFoundException{
        try{
            FileReader ler= new FileReader(nome);
            BufferedReader arq=new BufferedReader(ler);
            int parsedStr;
            String str=arq.readLine();
            while(str!=null){
                parsedStr=Integer.parseInt(str);
                a.add(parsedStr);
                str=arq.readLine();
            }
        }
        catch(IOException e){
            System.out.println("Erro na abertura do arquivo: "+
                    e.getMessage());
        }
    }
    public static int diferente(String a,String b){
        int diferentes=0;
        if(a.length()==b.length()){
            for(int i=0;i<a.length();i++){
                if(a.charAt(i)!=b.charAt(i))
                    diferentes++;
            }
        }
        else 
            diferentes=2;
        return diferentes;
    }

    public static boolean possibilidades(DirectedGraphList graph,String a,ArrayList<Integer> array){
        int diferentes=0;
        for(int i=0;i<array.size();i++){
            String numero=Integer.toString(array.get(i),6);
            diferentes=diferente(numero,a);
            if(diferentes==1){
                graph.addEdge(a,numero);
            }    
        }
        return true;
    }
    
    public void DFS(Vertice a){
        a.Visitado=true;
        for(int i=0;i<a.lst.size();i++){
            Vertice b=a.lst.get(i);
            if(!b.Visitado){
                DFS(b);
            }
        }
    }

    public static void main(String[] args) throws FileNotFoundException
    {
        ArrayList<Integer> numeros=new ArrayList<Integer>();
        criaArray(numeros,"/home/geovane/Documentos/CC/ALPROII/teste5000b");
        DirectedGraphList g = new DirectedGraphList();
        HeapSort.heapsort(numeros);
        for(int j=0;j<numeros.size();j++){
        g.addVertice(Integer.toString(numeros.get(j),6));
        }
        for(int i=0;i<numeros.size();i++){
            String numer=Integer.toString(numeros.get(i), 6);
            possibilidades(g,numer,numeros);
        }
    }
}