Skip to main content
1 de 6

Grafos: maior caminho

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

  1. A sequência deve ser crescente
  2. De um numero para outro da sequência, somente um digito pode mudar

Um exemplo seria: O arquivo contém os números 782,229,446,527,874,19,829,70,830,992,430,649. Ou seja, em base 6: 3342,1021,2022,2235,4014,31,3501,154,3502,4332,1554,3001.

Portanto, a maior sequencia respeitando essas regras seria: 649,829,830, que corresponde a 3001,3501,3502 em base6.

Certo, os arquivos não são assim tão simples, há arquivos com 5000,100mil números, portanto, criei um grafo. Eu tentei tanto com matriz como com lista de adjacencias. Adicionar os vertices e as arestas (ou seja, quais são os numeros 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 minimo, 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);
    }
}

}