Graphs: the longest path

Question

Well, as a college job, I have to create an algorithm that, given a certain file with x is able to verify which is the largest sequence of numbers which, on the basis of 6, comply with the following rules:

1. The sequence must be increasing
2. From one number to another of the sequence, only one digit can change
3. All numbers in the sequence must have the same number of digits (15->10015 is not valid)

An example would be:

The file contains the numbers 782, 229, 446, 527, 874, 19, 829, 70, 830, 992, 430 and 649.

That is, based on 6: 3342, 1021, 2022, 2235, 4014, 31, 3501, 154, 3502, 4332, 1554 and 3001.

Therefore, the largest sequence respecting these rules would be: 649, 829 and 830, which corresponds to 3001, 3501 and 3502 on 6 basis.

Okay, the files aren’t that simple, there are files that have up to 100,000 numbers, so I created a graph. I tried both with matrix and with adjacency list. Add vertices and edges (i.e., which numbers respect the rules for a number x) it was not a problem, my problem is to walk in the graph, because searching in the internet I found only minimal walking, but what I need is: to find the biggest way.

I tried with DFS but the result is not what I want.

My code is this:

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);
        }
    }
}

Answer 1

Since we cannot mix numbers of different sizes, the first step is to separate the input into sets containing numbers of the same length: in case {31}, {154}, {3342, 1021, 2022, 2235, 4014, 3501, 3502, 4332, 1554, 3001}; the answer must necessarily be equal to the response of some of these subsets; I will use to illustrate the algorithm, not its example, but the set {101, 322, 325, 342, 345, 422, 501, 502, 522} (on base 6, of course).

I listed the numbers already in ascending order to make the first question very easy: which is the largest sequence that meets the conditions of the problem starting at 522? Obviously it is the sequence {522}, since the restriction of the sequence is increasing ensures that we have nowhere to go after 522.

My second question: what is the largest sequence starting in 502? Obviously the answer is {502, 522}, since from {502} you can only go pro {522}. Similarly, it is easy to see that the largest sequence starting in 501 is {501, 502, 522}, etc.

If you’re analyzing the example numbers in descending order, you don’t have to think too much - you’ll always have zero or an alternative - until you get to 322.

(The gray knots are knots that we have already considered; the number in parentheses is the size of the longest path that begins at that knot. The red knot - 322 is the knot that we are now considering.)

Now we have four possibilities to continue the sequence: {322, 522, ... }, {322, 422, ... }, {322, 342, ... }, {322, 325, ... }. Which one is bigger? Now, we know that, with the exception of the sequence that begins in 522 (which can only have one term), the other choices allow to continue for two more numbers. So the largest sequence starting at 322 has 1 + 2 = 3 terms.

After that, it is easy to see that the largest (and only) sequence that starts in 101 has 4 terms, and therefore is the solution to the problem (because if you look at all the graph nodes, the largest sequence that starts in any of them is 4).

---

In short, the idea of the algorithm is this one:

para cada número n, em ordem decrescente:
    maior_sequência[n] := 1;  // sempre posso fazer a sequência unitária {n}
    para cada número “vizinho” v seguindo as regras do problema:
        // posso fazer a sequência {n, v, …}
        maior_sequência[n] := máximo(maior_sequência[n], 1 + maior_sequência[v]);        

retorne máximo(maior_sequência);

Does it make sense? This idea works because finding the largest sequence that starts at a given number depends only on the number: it doesn’t matter as I arrived in n until now; the way up n never affects the path I can follow after n. You can only do that because the graph is acyclic - I can never go back due to the restriction of numbers being increasing.

If I nay had this restriction, a valid answer to this example would be e.g. {101, 501, 502, 522, 422, 322, 342, 345, 325}, which goes through all the numbers, but this problem is much more difficult, since then I would have to somehow keep the numbers I’ve already visited. In this example, if I didn’t do this, I could have the infinite sequence, {322, 342, 345, 325, 322, 342, 345, 325, 322, …}.

This idea is an example of a much more general idea called dynamic programming; the Wikipedia link I think confuses more than clarifies, but I did not find much material in Portuguese. A wiki of the Programming Marathon at UFMG has more problems and some references in English if you want to study similar ideas.

Answer 2

Just to update and help someone who just happens to want the code solved.

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;
    int maiorSequencia;
    Vertice proximo;
    private ArrayList<Vertice> lst = new ArrayList<Vertice>();

    public Vertice(String item) {
        this.item = item;
        Visitado=false;
        maiorSequencia=0;
        lst=new ArrayList<Vertice>();
        proximo=null;
    }
    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 maior(String str1,String str2){
    int aux=Integer.parseInt(str1, 6);
    int aux1=Integer.parseInt(str2, 6);
    if(aux>aux1)
        return true;
    else return false;
}

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 && maior(numero,a)){
            graph.addEdge(a,numero);
        }   
    }
    return true;
}

public void printaSequencia(Vertice a){
    System.out.println(a.item);
    Vertice atual=a;
    while(atual.proximo!=null){
        atual=atual.proximo;
        System.out.println(atual.item);
    }
}

public void atribuiTamanhoSequencia(){
    for(int i=vert.size()-1;i>=0;i--){
        vert.get(i).maiorSequencia=1;
        for(int k=vert.get(i).lst.size()-1;k>=0;k--){
            if (vert.get(i).lst.get(k).maiorSequencia+1 > vert.get(i).maiorSequencia){
                vert.get(i).maiorSequencia=vert.get(i).lst.get(k).maiorSequencia+1;
                vert.get(i).proximo=vert.get(i).lst.get(k);
            }
        }
    }

}
public Vertice getVerticeInicial(){
    Vertice aux=null;
    int tamanho=0;
    for(int i=0;i<vert.size();i++){
        if(vert.get(i).maiorSequencia>tamanho){
            aux=vert.get(i);
            tamanho=vert.get(i).maiorSequencia;
        }
    }
    return aux;
}


public static void main(String[] args) throws FileNotFoundException
{
    ArrayList<Integer> numeros=new ArrayList<Integer>();
    criaArray(numeros,"/home/geovane/Documentos/CC/ALPROII/test100000a");
    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);
    }
    g.atribuiTamanhoSequencia();
    Vertice inicial=g.getVerticeInicial();
    g.printaSequencia(inicial);
}
}

Problem solved!! Thanks @ctgPi