Usando TDD para chegar ao algoritmo de Dijkstra

novembro 16, 2016 6:14 pm Publicado por Deixe um comentário

Eu estava no SCNA outro dia, e alguém me abordou sobre TDD e o algoritmo de Dijkstra. Ele se perguntou se você poderia encontrar uma sequência de testes que o levariam ao algoritmo. Isso soou um pouco como um divertido exercício, então eu decidi tentar aqui.

Vou começar, como de costume, com um caso de teste executando geral.

public class MinPathTest {
  @Test
  public void nothing() throws Exception {
  }
}

O algoritmo de Dijkstra é uma técnica simples para encontrar o caminho mínimo através de um grafo com arestas de comprimento arbitrário. Dado os nós de início e término, o algoritmo irá dizer-lhe o caminho mínimo e o comprimento desse caminho.

Assim, desde o início, há algumas decisões interessantes a serem tomadas. Como devo representar o grafo de entrada? Como devo representar a saída do algoritmo? Podemos provavelmente decidir muito disso mais tarde. Por enquanto, devemos nos concentrar nos casos mais gerais: um gráfico vazio.

public void noGraph_NoPathZeroLength() throws Exception {
  Assert.assertEquals("{}0", minPath(""));
}

O primeiro teste me forçou a tomar algumas decisões sobre o formato de saída. Eu representarei o caminho de saída como um conjunto de nós entre chaves. O comprimento do caminho será um número inteiro após as chaves.

Essa notação é apenas para os meus testes. Estou usando uma técnica que eu chamo de composed asserts. Eu gosto de compor minhas afirmações em declarações que são fáceis de ler. Isso geralmente significa que eu devo escrever tradutores simples em meus testes que convertam as afirmações compostas na verdadeira API do sistema em teste.

Claramente eu posso fazer esse caso de teste passar com nada mais do que isto:

private String minPath(String graph) {
  return "{}0";
}

Vejamos cuidadosamente esse caso de teste. Essa chamada para minPath não está certa. O algoritmo de Dijkstra encontra o caminho mínimo entre dois nós especificados. Assim, supondo que os nós têm nomes, o teste deve realmente parecer algo como isto:

Assert.assertEquals("{}0", minPath("", "A", "Z"));

Também é muito feio. Podemos refatorá-lo para ser um pouco mais bonito:

private void assertPath(String graph, String expected) {
  assertEquals(expected, minPath(graph, "A", "Z"));
}

@Test
public void noGraph_NoPathZeroLength() throws Exception {
  assertPath("", "{}0");
}

Observe que o método assertPath simplesmente assume que todos os casos de teste usarão “A” e “Z” para seus pontos inicial e final.

Uma última mudança. Eu acho que o caminho e o comprimento devem ser separados.

private void assertMinPath(String graph, 
                           int length, String path) {
  assertEquals(length, minLength(graph, "A", "Z"));
  assertEquals(path, minPath(graph, "A", "Z"));
}

@Test
public void noGraph_NoPathZeroLength() throws Exception {
  assertMinPath("", 0, "{}");
}

private int minLength(String graph, String begin, String end) {
  return 0;
}

private String minPath(String graph, String begin, String end) {
  return "{}";
}

Uma vez que existem dois métodos para verificar a minha afirmação, acho que é razoável supor que eles devem ser métodos de alguma classe que executa o algoritmo de Dijkstra. Então, vamos usar a refatoração extract delegate para extrair uma nova classe.

public class MinPathTest {
  private void assertMinPath(String graph,
                             int length, String path) {
    PathFinder pf = new PathFinder(graph);
    assertEquals(length, pf.minLength("A", "Z"));
    assertEquals(path, pf.minPath("A", "Z"));
  }

  @Test
  public void noGraph_NoPathZeroLength() throws Exception {
    assertMinPath("", 0, "{}");
  }
}

class PathFinder {
  public PathFinder(String graph) {
  }

  public int minLength(String begin, String end) {
    return 0;
  }

  public String minPath(String begin, String end) {
    return "{}";
  }
}

Acho interessante quanto pensamento e esforço foram colocados na estrutura desse problema; apenas no primeiro caso de teste anormal. Mas agora eu acho que podemos adicionar vários casos mais anormais:

@Test
public void degenerateCases() throws Exception {
  assertMinPath("", 0, "{}");   //empty graph
  assertMinPath("A", 0, "{}");  //one node
  assertMinPath("B1C", 0, "{}");//no start or end
  assertMinPath("A1C", 0, "{}");//no end
  assertMinPath("B1Z", 0, "{}");//no start
}

Esses testes me forçaram a tomar outra decisão para a composed assert. Para os nossos testes, a estrutura de uma borda do gráfico será <name> lenght <name>. Portanto, B1C é uma aresta de comprimento 1 que conecta o nó B ao nó C.

Acho que são todos os casos degenerados. Então vamos acelerar a complexidade de um nível e fazer o primeiro caso de teste que nos forçará a fazer algo marginalmente inteligente.

@Test
public void oneEdge() throws Exception {
  assertMinPath("A1Z", 1, "{AZ}");
}

Esse teste falha, é claro. Também me deixa desconfortável porque estou testando duas coisas, o comprimento e o caminho, que eu poderia testar separadamente. Isso me faz resmungar porque eu passei todo esse tempo montando a afirmação composta, e agora eu quero separá-lo novamente. Mas eu acho que há uma maneira “inteligente” de contornar isso.

private static String ANY = null;

private void assertMinPath(String graph,
                           Integer length, String path) {
  PathFinder pf = new PathFinder(graph);
  if (length != null)
    assertEquals((int)length, pf.minLength("A", "Z"));
  if (path != null)
    assertEquals(path, pf.minPath("A", "Z"));
}
...
@Test
public void oneEdge() throws Exception {
  assertMinPath("A1Z", 1, ANY);
}

Isso mantém a minha afirmação intacta, e me permite ignorar qualquer um dos dois componentes que eu desejo. Então agora vamos fazer esse teste passar.

Agora, obviamente, eu poderia fazer algo horrível como isto:

public int minLength(String begin, String end) {
  if (graph.equals("A1Z"))
    return 1;
  return 0;
}

Mas isso quebra uma série de regras. Primeiro, ele quebra a regra de generalidade que diz: À medida que os testes ficam mais específicos, o código fica mais genérico. Em outras palavras, o código de produção tem que se tornar mais geral para passar num teste de falha. Não é possível adicionar expressões ao código de produção que são específicas para o teste de falha (eu falo muito mais sobre isso no Episódio 19: Advanced TDD, no cleancoders.com).

A segunda regra quebrada é o acoplamento de teste. Não queremos que os testes se tornem fortemente acoplados ao código de produção. Quanto maior o acoplamento, mais frágil os testes se tornam. Não queremos incentivar o caso de que uma única mudança no código de produção quebra dezenas ou centenas de testes. Em nosso caso particular, não queremos que a composed assertion vaze na API do código de produção.

Isso significa que eu não deveria estar passando o String gaph para o construtor do PathFinder. Isso também significa que a função minPath não deve retornar a String usada pela composed assert.

Então, é hora de começar a desacoplar os testes. A função makePathFinder abaixo mostra como eu fiz isso.

public class MinPathTest {
  private static String ANY = null;

  private void assertMinPath(String graph,
                             Integer length, String path) {
    PathFinder pf = makePathFinder(graph);
    if (length != null)
      assertEquals((int) length, pf.minLength("A", "Z"));
    if (path != null)
      assertEquals(path, pf.minPath("A", "Z"));
  }

  private PathFinder makePathFinder(String graph) {
    PathFinder pf = new PathFinder();
    Pattern edgePattern = 
            Pattern.compile("(D+)(d+)(D+)");
    Matcher matcher = edgePattern.matcher(graph);
    if (matcher.matches()) {
      String start = matcher.group(1);
      int length = Integer.parseInt(matcher.group(2));
      String end = matcher.group(3);
      pf.addEdge(start, end, length);
    }
    return pf;
  }

  @Test
  public void degenerateCases() throws Exception {
    assertMinPath("", 0, "{}");   //empty graph
    assertMinPath("A", 0, "{}");  //one node
    assertMinPath("B1C", 0, "{}");//no start or end
    assertMinPath("A1C", 0, "{}");//no end
    assertMinPath("B1Z", 0, "{}");//no start
  }

  @Test
  public void oneEdge() throws Exception {
    assertMinPath("A1Z", 1, ANY);
  }
}

class PathFinder {
  private List<Edge> edges = new ArrayList<>();

  public PathFinder() {
  }

  public int minLength(String begin, String end) {
    int length = 0;
    for (Edge edge : edges) {
      if (edge.begin.equals(begin) && edge.end.equals(end))
        length += edge.length;
    }
    return length;
  }

  public String minPath(String begin, String end) {
    return "{}";
  }

  public void addEdge(String start, String end, int length) {
    edges.add(new Edge(start, end, length));
  }

  private static class Edge {
    public final String begin;
    public final String end;
    public final int length;

    public Edge(String begin, String end, int length) {
      this.begin = begin;
      this.end = end;
      this.length = length;
    }
  }
}

Note que toda a análise para a composed assertion permanece na classe de teste. A classe PathFinder não sabe nada da sintaxe engraçada que estou usando nos testes. Observe também que, para obter os testes para passar, o código de produção deve assumir que o grafo tem apenas uma borda. Isso é uma suposição que estaremos quebrando dentro dos próximos casos de teste. Nesse meio tempo, devemos nos livrar disso.

assertMinPath("A1Z", 1, "{AZ}");

Então eu vou precisar construir a lista de nós no caminho. Lista? Ah, há uma sintaxe toString para listas. Devemos mudar esse teste, e todos os testes, como segue:

@Test
public void degenerateCases() throws Exception {
  assertMinPath("", 0, "[]");   //empty graph
  assertMinPath("A", 0, "[]");  //one node
  assertMinPath("B1C", 0, "[]");//no start or end
  assertMinPath("A1C", 0, "[]");//no end
  assertMinPath("B1Z", 0, "[]");//no start
}

@Test
public void oneEdge() throws Exception {
  assertMinPath("A1Z", 1, "[A, Z]");
}

Agora, para que isso aconteça, teremos que alterar a função auxiliar de teste assertMinPath, adicionando uma chamada toString.

...
    if (path != null)
      assertEquals(path, pf.minPath("A", "Z").toString());
...

Nós adicionamos a lista path ao PathFinder e simplesmente a carregamos na função minLength.

class PathFinder {
  private List<Edge> edges = new ArrayList<>();
  ...

  public int minLength(String begin, String end) {
    int length = 0;
    for (Edge edge : edges) {
      if (edge.begin.equals(begin) && edge.end.equals(end)) {
        length += edge.length;
        path.add(edge.begin);
        path.add(edge.end);
      }
    }
    return length;
  }

  public List<String> minPath(String begin, String end) {
    return path;
  }
...

Isso funciona. Mas eu não gosto do fato de que minLength também está calculando o caminho. Acho que devemos separar o cálculo dos relatórios.

private void assertMinPath(String graph,
                             Integer length, String path) {
    PathFinder pf = makePathFinder(graph);
    if (length != null)
      assertEquals((int) length, pf.getLength());
    if (path != null)
      assertEquals(path, pf.getPath().toString());
  }

  private PathFinder makePathFinder(String graph) {
    PathFinder pf = new PathFinder();
    ...
    pf.findPath("A", "Z");
    return pf;
  }

class PathFinder {
  private List<Edge> edges = new ArrayList<>();
  private List<String> path = new ArrayList<>();
  private int length;

  ...

  public int getLength() {
    return length;
  }

  public List<String> getPath() {
    return path;
  }

...

OK, isso é melhor. Agora, vamos nos certificar de que temos o comprimento certo.

assertMinPath("A2Z", 2, "[A, Z]");

Sim, isso funciona muito bem. Então vamos tentar duas bordas sequenciais.

@Test
public void twoEdges() throws Exception {
  assertMinPath("A1B,B1Z", 2, ANY);
}

Isso falha como esperado, dando-nos um comprimento zero. Para fazer isso passar, vamos ter que analisar várias bordas no helper makePathFinder. Isso é bem simples. Basta dividir o grafo em vírgula e colocar o marcador de expressão regular em um loop.

private PathFinder makePathFinder(String graph) {
  PathFinder pf = new PathFinder();
  Pattern edgePattern = Pattern.compile("(D+)(d+)(D+)");
  String[] edges = graph.split(",");
  for (String edge : edges) {
    Matcher matcher = edgePattern.matcher(edge);
    if (matcher.matches()) {
      String start = matcher.group(1);
      int length = Integer.parseInt(matcher.group(2));
      String end = matcher.group(3);
      pf.addEdge(start, end, length);
    }
  }
  pf.findPath("A", "Z");
  return pf;
}

Isso ainda falha no teste, é claro, então agora vamos ter que conectar as duas arestas. Vamos supor que as arestas são especificadas na ordem, de modo que o nó A comece a primeira aresta, e o nó Z termine a segunda aresta. Nesse caso, devemos ser capazes de fazer toda a conexão, alterando o && para um || na função findPath:

public void findPath(String begin, String end) {
  length = 0;
  for (Edge edge : edges) {
    if (edge.begin.equals(begin) || edge.end.equals(end)) {
      length += edge.length;
      path.add(edge.begin);
      path.add(edge.end);
    }
  }
}

Você gostou dessa mudança? && para ||. Sim, muito inteligente. Só funcionará para duas arestas consecutivas. As suposições estão aumentando para o céu! E, de qualquer forma, não funciona.

Oh, ele passa o teste twoEdges, e os testes oneEdge, mas ele falha nos testes degenerateCases. E não é de admirar, uma vez que os nossos dois últimos casos degenerados correspondem à “A” (primeira) ou à “Z” (última) suposição.

Para fazer todos esses testes passarem, eu preciso de uma implementação que produz comprimento zero e um caminho vazio se não houver nenhum caminho de A a Z. Agora, como eu não sei quantas arestas existem (poderia ser zero, uma ou duas), eu não consigo pegar os dois. Em vez disso, eu poderia fazer uma análise de caso para zero, uma ou duas arestas do seguinte modo:

public void findPath(String begin, String end) {
  if (edges.size() == 0)
    return;

  else if (edges.size() == 1) {
    Edge edge = edges.get(0);
    if (edge.begin.equals(begin) && edge.end.equals(end)) {
      path.add(edge.begin);
      path.add(edge.end);
      length += edge.length;
    }
  } else {
    for (Edge edge : edges) {
      if (edge.begin.equals(begin) || edge.end.equals(end)) {
        path.add(edge.begin);
        path.add(edge.end);
        length += edge.length;
      }
    }
  }
}

OK, isso funciona, mas é realmente horrível. Não só viola a regra de generalidade, mas também é apenas desagradável. Além do mais, ele não monta corretamente o caminho. Por exemplo, assertMinPath ( “A1B, B1Z”, 2, “[A, B, Z]”); falha porque produz [A, B, B, Z]. Eu poderia corrigir isso adicionando mais uma declaração horrível if, mas eu tenho uma ideia melhor. Vamos percorrer o grafo do início ao fim.

public void findPath(String begin, String end) {
  List<String> p = new ArrayList<>();
  int l = 0;
  p.add(begin);

  for (Edge e = findEdge(begin); 
       e != null; e = findEdge(e.end)) {
    p.add(e.end);
    l += e.length;
    if (e.end.equals(end)) {
      length = l;
      path = p;
      return;
    }
  }
}

private Edge findEdge(String begin) {
  for (Edge e : edges) {
    if (e.begin.equals(begin))
      return e;
  }
  return null;
}

OK, isso funciona. É estranho que tivemos que usar variáveis temporárias de comprimento e caminho, mas essa foi a única maneira que eu poderia pensar para garantir que ignoramos caminhos que não existem. Eu também acho que essa solução se livra de nossa dependência de ordem.

@Test
public void twoEdges() throws Exception {
  assertMinPath("A1B,B1Z", 2, "[A, B, Z]");
  assertMinPath("B1Z,A1B", 2, "[A, B, Z]");
  assertMinPath("A1X,Y1Z", 0, "[]");
}

Sim. Tudo isso passa. Eu também acho que três ou mais arestas vão funcionar. E assim será com alguns grafos com apenas um caminho completo, e com outros caminhos pendentes.

@Test
public void threeEdges() throws Exception {
  assertMinPath("A2B,B3C,C4Z", 9, "[A, B, C, Z]");
  assertMinPath("B3C,C4Z,A2B", 9, "[A, B, C, Z]");
}

@Test
public void OnlyOnePath() throws Exception {
  assertMinPath("A1B,B2C,C3Z,B4D,D6E", 6, "[A, B, C, Z]");
}

Mas esses falham porque o passeio do grafo falha a aresta de C3Z.

assertMinPath("A1B,B2C,C3D,C3Z", 6, "[A, B, C, Z]");

Ok. Portanto, não podemos simplesmente andar pelo gráfico na ordem. O que vamos ter que fazer em vez disso é inspecionar cada caminho possível que leva longe do nó de partida; e teremos que gravar nossas variáveis temporárias ao longo do caminho, até chegar ao final.

Como você verá abaixo, isso requer um pouco de esforço eclesiástico. Eu preciso acompanhar todos os nós, os caminhos e os comprimentos associados a esses nós. Mas, além disso, o algoritmo é quase o mesmo.

A iteração de loop é diferente. Ela começa no nó de início e, em seguida, percorre todos os vizinhos não avisados e armazena os comprimentos e caminhos acumulados nesses vizinhos.

Observe que eu usei Integer.MAX_VALUE como uma sentinela que significa “Não alcançado de um nó visitado”. Limitamos a pesquisa somente aos nós que foram alcançados, porque ainda estamos andando do começo ao fim. Qualquer nó que não tenha sido alcançado claramente não é o próximo no caminho.

class PathFinder {
  private List<Edge> edges = new ArrayList<>();
  private Set<String> nodeNames = new HashSet<>();
  private Map<String, Node> nodes = new HashMap<>();
  private Node endNode;

  public void findPath(String begin, String end) {
    List<String> unvisited = initializeSearch(begin, end);

    for (String node = begin; 
         node != null; node = getNext(unvisited)) {
      unvisited.remove(node);
      visit(node);
    }

    setupEndNode(end);
  }

  private List<String> initializeSearch(String begin, 
                                        String end) {
    nodeNames.add(begin);
    nodeNames.add(end);
    List<String> unvisited = new ArrayList<>(nodeNames);
    for (String node : unvisited)
      nodes.put(node, new Node(Integer.MAX_VALUE));

    nodes.get(begin).length = 0;
    return unvisited;
  }

  private void visit(String node) {
    List<Edge> neighbors = findEdges(node);
    Node curNode = nodes.get(node);
    for (Edge e : neighbors) {
      Node nbr = nodes.get(e.end);
      nbr.length = curNode.length + e.length;
      nbr.path = new ArrayList<String>();
      nbr.path.addAll(curNode.path);
      nbr.path.add(node);
    }
  }

  private void setupEndNode(String end) {
    endNode = nodes.get(end);
    if (endNode.length != Integer.MAX_VALUE)
      endNode.path.add(end);
    else
      endNode.length = 0;
  }

  private String getNext(List<String> unvisited) {
    for (String name : unvisited) {
      Node candidate = nodes.get(name);
      if (candidate.length != Integer.MAX_VALUE)
        return name;
    }
    return null;
  }

  private List<Edge> findEdges(String begin) {
    List<Edge> found = new ArrayList<>();
    for (Edge e : edges) {
      if (e.begin.equals(begin))
        found.add(e);
    }
    return found;
  }

  public int getLength() {
    return endNode.length;
  }

  public List<String> getPath() {
    return endNode.path;
  }

  public void addEdge(String start, String end, int length) {
    edges.add(new Edge(start, end, length));
    nodeNames.add(start);
    nodeNames.add(end);
  }

  private static class Edge {
    public final String begin;
    public final String end;
    public final int length;

    public Edge(String begin, String end, int length) {
      this.begin = begin;
      this.end = end;
      this.length = length;
    }
  }

  private static class Node {
    public int length;
    public List<String> path;

    public Node(int l) {
      this.length = l;
      this.path = new ArrayList<>();
    }
  }
}

Isso passa. Portanto, agora precisamos adicionar um teste que tenha caminhos paralelos. Aqui está um simples que deve falhar:

assertMinPath("A1B,B2Z,A1Z", 1, "[A, Z]");

E ele falha.

Para que façamos com que ele passe, teremos que detectar quando dois caminhos convergem. Isso é simples. Se o comprimento do nó de destino não for Integer.MAX_VALUE, então outro caminho atingiu esse nó. Uma vez que estamos após o mínimo, podemos simplesmente definir o comprimento nesse nó para o mínimo das vias convergentes. Integer.MAX_VALUE passa a ser um valor muito conveniente para essa sentinela, uma vez que substitui por um comprimento “infinito”.

private void visit(String node) {
  List<Edge> neighbors = findEdges(node);
  Node curNode = nodes.get(node);
  for (Edge e : neighbors) {
    Node nbr = nodes.get(e.end);

    int newLength = curNode.length + e.length;
    if (nbr.length > newLength) {
      nbr.length = newLength;
      nbr.path = new ArrayList<String>();
      nbr.path.addAll(curNode.path);
      nbr.path.add(node);
    }
  }
}

Podemos provavelmente acelerar um pouco o algoritmo, terminando a pesquisa quando visitamos o nó final.

for (String node = begin; node != null && !node.equals(end); node = getNext(unvisited)) {
  unvisited.remove(node);
  visit(node);
}

E podemos provavelmente acelerar o algoritmo ainda mais, preferindo pesquisar os nós não visitados que foram atingidos pelo menor comprimento.

private String getNext(List<String> unvisited) {
  String minNodeName = null;
  int minLength = Integer.MAX_VALUE;

  for (String name : unvisited) {
    Node candidate = nodes.get(name);
    if (candidate.length < minLength) {
      minLength = candidate.length;
      minNodeName = name;
    }
  }
  return minNodeName;
}

Isso, para todos os efeitos, é o algoritmo de Dijkstra. Essa implementação não é rápida porque eu usei conjuntos e listas, e muitas estruturas ineficientes. Acelerá-lo exigiria um pouco de trabalho. Além disso, foram construídas algumas suposições que precisam ser corrigidas. Especificamente, o grafo de entrada é assumido como sendo direcionado, enquanto que o algoritmo geral não faz tal suposição. Finalmente, a coisa toda poderia usar um pouco mais de refatoração.

Mas o objetivo era ver se era possível usar o TDD para se aproximar passo a passo do algoritmo de Dijkstra. Eu acho que é, embora eu tenha que dizer que a abordagem foi bastante brusca. Esses primeiros testes me levaram através de várias tentativas de algoritmos que não evoluíram perfeitamente em um outro. Ainda assim, cada novo teste expôs fragilidades na implementação anterior que poderiam ser corrigidas de forma relativamente direta.

Existe uma sequência de testes melhor que levaria mais diretamente ao algoritmo de Dijkstra, sem a tentativa brusca? Possivelmente, mas eu não encontrei.

Enfim, foi um exercício divertido. Grato ao participante do SCNA por recomendá-lo.

O código final, que ainda precisa de um pouco de limpeza (deixo ao o leitor como um exercício ;-):

package dijkstrasAlg;

import org.junit.Test;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import static org.junit.Assert.assertEquals;

public class MinPathTest {
  private static String ANY = null;

  private void assertMinPath(String graph,
                             Integer length, String path) {
    PathFinder pf = makePathFinder(graph);
    if (length != null)
      assertEquals((int) length, pf.getLength());
    if (path != null)
      assertEquals(path, pf.getPath().toString());
  }

  private PathFinder makePathFinder(String graph) {
    PathFinder pf = new PathFinder();
    Pattern edgePattern = 
            Pattern.compile("(D+)(d+)(D+)");
    String[] edges = graph.split(",");
    for (String edge : edges) {
      Matcher matcher = edgePattern.matcher(edge);
      if (matcher.matches()) {
        String start = matcher.group(1);
        int length = Integer.parseInt(matcher.group(2));
        String end = matcher.group(3);
        pf.addEdge(start, end, length);
      }
    }
    pf.findPath("A", "Z");
    return pf;
  }

  @Test
  public void degenerateCases() throws Exception {
    assertMinPath("", 0, "[]");   //empty graph
    assertMinPath("A", 0, "[]");  //one node
    assertMinPath("B1C", 0, "[]");//no start or end
    assertMinPath("A1C", 0, "[]");//no end
    assertMinPath("B1Z", 0, "[]");//no start
  }

  @Test
  public void oneEdge() throws Exception {
    assertMinPath("A1Z", 1, "[A, Z]");
    assertMinPath("A2Z", 2, "[A, Z]");
  }

  @Test
  public void twoEdges() throws Exception {
    assertMinPath("A1B,B1Z", 2, "[A, B, Z]");
    assertMinPath("B1Z,A1B", 2, "[A, B, Z]");
    assertMinPath("A1X,Y1Z", 0, "[]");
  }

  @Test
  public void threeEdges() throws Exception {
    assertMinPath("A2B,B3C,C4Z", 9, "[A, B, C, Z]");
    assertMinPath("B3C,C4Z,A2B", 9, "[A, B, C, Z]");
  }

  @Test
  public void OnlyOnePath() throws Exception {
    assertMinPath("A1B,B2C,C3Z,B4D,D6E", 6, "[A, B, C, Z]");
    assertMinPath("A1B,B2C,C3D,C3Z", 6, "[A, B, C, Z]");
  }

  @Test
  public void parallelPaths() throws Exception {
    assertMinPath("A1B,B2Z,A1Z", 1, "[A, Z]");
    assertMinPath("A1B,A1C,A2D,C5E,B8E,C1F,D3F,F2G,G3Z,E2G",
                   7,"[A, C, F, G, Z]");
  }
}

class PathFinder {
  private List<Edge> edges = new ArrayList<>();
  private Set<String> nodeNames = new HashSet<>();
  private Map<String, Node> nodes = new HashMap<>();
  private Node endNode;

  public void findPath(String begin, String end) {
    List<String> unvisited = initializeSearch(begin, end);

    for (String node = begin; 
         node != null && !node.equals(end); 
         node = getNext(unvisited)) {
      unvisited.remove(node);
      visit(node);
    }

    setupEndNode(end);
  }

  private List<String> initializeSearch(String begin, 
                                        String end) {
    nodeNames.add(begin);
    nodeNames.add(end);
    List<String> unvisited = new ArrayList<>(nodeNames);
    for (String node : unvisited)
      nodes.put(node, new Node(Integer.MAX_VALUE));

    nodes.get(begin).length = 0;
    return unvisited;
  }

  private void visit(String node) {
    List<Edge> neighbors = findEdges(node);
    Node curNode = nodes.get(node);
    for (Edge e : neighbors) {
      Node nbr = nodes.get(e.end);

      int newLength = curNode.length + e.length;
      if (nbr.length > newLength) {
        nbr.length = newLength;
        nbr.path = new ArrayList<String>();
        nbr.path.addAll(curNode.path);
        nbr.path.add(node);
      }
    }
  }

  private void setupEndNode(String end) {
    endNode = nodes.get(end);
    if (endNode.length != Integer.MAX_VALUE)
      endNode.path.add(end);
    else
      endNode.length = 0;
  }

  private String getNext(List<String> unvisited) {
    String minNodeName = null;
    int minLength = Integer.MAX_VALUE;

    for (String name : unvisited) {
      Node candidate = nodes.get(name);
      if (candidate.length < minLength) {
        minLength = candidate.length;
        minNodeName = name;
      }
    }
    return minNodeName;
  }

  private List<Edge> findEdges(String begin) {
    List<Edge> found = new ArrayList<>();
    for (Edge e : edges) {
      if (e.begin.equals(begin))
        found.add(e);
    }
    return found;
  }

  public int getLength() {
    return endNode.length;
  }

  public List<String> getPath() {
    return endNode.path;
  }

  public void addEdge(String start, String end, int length) {
    edges.add(new Edge(start, end, length));
    nodeNames.add(start);
    nodeNames.add(end);
  }

  private static class Edge {
    public final String begin;
    public final String end;
    public final int length;

    public Edge(String begin, String end, int length) {
      this.begin = begin;
      this.end = end;
      this.length = length;
    }
  }

  private static class Node {
    public int length;
    public List<String> path;

    public Node(int l) {
      this.length = l;
      this.path = new ArrayList<>();
    }
  }
}

***

Robert Martin faz parte do time de colunistas internacionais do iMasters. A tradução do artigo é feita pela redação iMasters, com autorização do autor, e você pode acompanhar o artigo em inglês no link: http://blog.cleancoder.com/uncle-bob/2016/10/26/DijkstrasAlg.html.

Mensagem do anunciante:

Experimente a Umbler, startup de Cloud Hosting por demanda feita para agências e desenvolvedores e ganhe até R$ 100 em créditos!

Source: IMasters

Categorizados em:

Este artigo foi escrito pormajor

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *