İçeriği Paylaş:

Dijkstra Algoritması

Dijkstra Algoritması

Bu yazımızda öğrencilerin zar zor kavrayabildiği Dijkstra Algoritmasını örnekle anlatacağım. Ayrıca tüm adımları ve var olabilecek tüm hataları göstererek ilerleyeceğim. Biraz uzun olacak ama tamamen kavrayabileceksiniz.

Dijkstra algoritması keyfi uzunlukta kenarlara sahip bir grafik aracılığıyla minimum yolu bulmak için basit bir tekniktir. Başlangıç ve bitiş düğümleri göz önüne alındığında, algoritma minimum yolu ve o yolun uzunluğunu söyleyecektir.

Bu yüzden baştan beri ilginç kararlar vermek zorundayız. Giriş grafiğini nasıl temsil edeceğim? Algoritmanın çıktısını nasıl temsil edeceğim? Muhtemelen daha fazlasını karar verebiliriz. Şimdilik, olguların en dejenere olanı: boş bir grafik üzerinde yoğunlaşmalıyız.

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

İlk test, çıktı biçimi hakkında bazı kararlar vermeye zorladı. Çıkış yolunu kıvırcık parantezler arasında bir düğüm kümesi olarak temsil edeceğim. Yolun uzunluğu, kıvrımlı parantezleri takip eden bir tam sayı olacaktır.

Bu gösterim yalnızca testlerim için. Oluşturulan assertler adlı bir teknik kullanıyorum. Açıklamalarımı, okunması kolay tablolara yazmak isterim. Bu çoğunlukla, testlerimde, oluşturulan iddiaları test edilen sistemin gerçek API’sine dönüştüren basit çevirmenler yazmak zorundayım demektir.

Açıkçası, bu test davasını bundan başka bir şey olmadan geçirebilirim:

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

Test durumuna dikkatle bakalım. MinPath çağrısı doğru değil. Dijkstra algoritması belirtilen iki düğüm arasındaki minimum yolu bulur. Demek ki, düğümlerin adları olduğunu varsayarsak, test şu şekilde görünmelidir:

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

Ayrıca çok çirkin. Biraz daha güzel olmasını sağlayabiliriz:

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

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

Assert Path yönteminin, yalnızca test durumlarının başlangıç ve bitiş noktaları için “A” ve “Z” kullanacağını varsayacağına dikkat edin.
Son bir değişiklik. Bence yolu ve uzunluğu birbirinden ayrılmalı.

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 "{}";
}

Since there are two methods to check in my assertion, I think it’s reasonable to assume that they should be methods of some class that executes Dijkstra’s algorithm. So let’s use the extract delegate refactoring to pull out a new class.

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 "{}";
  }
}

Bence bu sorunun yapısına ne kadar çok düşünce ve emek verildi ilginç; Sadece ilk dejenere test davası için. Fakat şimdi birkaç tane dejenere olgu daha ekleyebiliriz:

@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
}

Bu testler beni, bileşik assert için bir başka karar vermeye zorluyordu. Testlerimiz için bir grafik kenarının yapısı length olacaktır. Bu nedenle B1C, düğüm B’yi düğüm C’ye bağlayan uzunluk 1 kenarındadır.
Sanırım hepsi dejenere durumlarda. Bu yüzden, karmaşıklığı bir çentik kadar kilitleyelim ve marjinal akıllı bir şey yapmamızı sağlayacak ilk test örneğini yapalım.

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

Bu test elbette başarısız olur. Aynı zamanda beni rahatsız ediyor çünkü ayrı olarak test edebileceğim iki şey, uzunluk ve yol test ediyorum. Bu beni homurdanmaya çeviriyor, çünkü o kadar zamanı birlikte yazılmış iddiaları ayarlayarak geçirdim; Ve şimdi tekrar parçalamak istiyorum. Ama bundan kurtulmanın “akıllıca” bir yolunun olduğunu düşünüyorum.

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

Bu, best assert’ımı sağlam tutar ve arzulamam gereken her iki bileşenten de görmezden gelmemi sağlar. Şimdi testi geçelim.

Açıkçası şu şekilde korkunç bir şey yapabilirim:

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

Fakat bu bir takım kuralları çiğnemektedir. İlk olarak şunu söyleyen genellik kuralını ihlal ediyor: Testler daha spesifik hale geldiğinde kod daha genel bir hale geliyor. Başka bir deyişle, üretim kodunun başarısız bir testi geçmesi için daha genel hale getirilmesi gerekir. Üretim koduna, başarısız teste özgü ifadeler ekleyemezsiniz
İkinci kırık kural test kavramasıdır. Testlerin üretim koduyla kuvvetli bir şekilde birleştirilmesini istemiyoruz. Kaplin ne kadar kırılgansa, testler de o kadar zayıf olur. Üretim kodunda tek bir değişikliğin onlarca veya yüzlerce testi kırması durumunda durumu teşvik etmek istemiyoruz. Özel durumumuzda, oluşturulan iddianın üretim kodunun API’sine girmesini istemiyoruz.

Bu, String grafiğini PathFinder yapıcısına aktarmamam gerektiği anlamına geliyor. Ayrıca, minPath işlevi, oluşturulan assert tarafından kullanılan String’i döndürmemesi gerektiği anlamına gelir.

Testleri ayırmanın zamanı geldi. Aşağıdaki makePathFinder işlevi bunu nasıl yaptığım gösterir.

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

Oluşturulan onaylama için tüm ayrıştırmanın sınama sınıfında kalacağını unutmayın. PathFinder sınıfı, testlerde kullandığım komik söz diziminden hiçbir şey biliyor. Ayrıca, testlerin geçmesi için üretim kodunun, grafiğin yalnızca bir kenar olduğunu varsayması gerekir. Önümüzdeki birkaç test davasında kırılacağımız varsayım budur. Bu arada ANY’den kurtulmalıyız.

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

Dolayısıyla, yolun içindeki düğümlerin listesini oluşturmak zorunda kalacağım. Liste? Ah, listeler için bir toString sözdizimi var. Bu testi değiştirmeliyiz; Ve bütün testler aşağıdaki gibidir:

@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]");
}

Now to get this to pass we’ll have to change the assertMinPath test helper function by adding a toString call.

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

Yol listesini PathFinder’a ekleriz ve minLength işlevine yükleyin.

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

Bu çalışıyor. Ancak minLength’in de yolunu hesapladığı gerçeğini sevmiyorum. Sanırım hesaplamayı raporlamadan ayırmalıyız.

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

...

Tamam, daha iyi. Şimdi, boyu doğru tuttuğumuzdan emin olalım.

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

Evet, sorun yok Bu yüzden iki ardışık kenarı deneyelim.

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

Bu, beklendiği gibi başarısız olur ve bize sıfır uzunluk kazandırır. Bunu yapmak için, makePathFinder yardımcıcusunda birden fazla kenarı ayrıştırmamız gerekecek. Oldukça basit. Grafiği virgülle ayırın ve normal ifade eşleyici’yi bir döngüye yerleştirin.

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

Elbette test başarısız oluyor, şimdi iki kenarı birbirine bağlamalıyız. Diyelim ki, kenarların sırayla belirtildiğini varsayalım, böylece düğüm A birinci kenarı başlatır ve düğüm Z, ikinci kenarı bitirir. Bu durumda, tüm bağlantıyı bir && bir || değerini değiştirerek yapabilmeliyiz FindPath işlevinde:

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

Bu değişikliği beğeniyor musun? && için ||. Evet, çok zeki. Sadece birbirini izleyen iki kenar için çalışacaktır. Varsayımlar gökyüzüne taşıyor! Ve yine de işe yaramıyor.

Oh, twoEdges testinden geçiyor ve oneEdge test ediyor, ancak degenerateCases testlerinde başarısız oluyor. Ve hiç de şaşırtıcı değil, çünkü son iki dejenere vakanız “A” veya “Z” son varsayımıyla eşleşiyor.

Bu testlerin hepsini başarmak için, sıfır uzunluğu ve boş bir yol üreten bir uygulamaya ihtiyacım var, burada A’dan Z’ye bir yol yoksa. Şu anda kaç tane kenar bulunduğunu bilmiyorum (sıfır, bir veya daha fazla olabilir Iki) Sadece ikisini kapamam. Bunun yerine sıfır, bir veya iki kenar için bir vaka analizi yapabilirim; aşağıdaki gibi:

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

Tamam, işe yarıyor, ama gerçekten korkunç. Sadece generality kuralını ihlal etmekle kalmıyor; Ayrıca sadece icky. Dahası, yolu doğru bir şekilde monte etmiyor. Örneğin. AssertMinPath (“A1B, B1Z”, 2, “[A, B, Z]”); Başarısız olur, çünkü [A, B, B, Z] üretir. Bunu başka bir korkunç if ifadesi ekleyerek düzeltebilirim; Ama daha iyi bir fikrim var. Grafiği baştan sona takip edelim.

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

Tamam, işe yarıyor. Geçici uzunluk ve yol değişkenlerini kullanmak zorunda kalmamız garip; Ama var olmayan yolları görmezden gelmemizi sağlamak için düşünebildiğim tek yol bu. Ayrıca bu çözümün emir bağımlılığından kurtulduğunu düşünüyorum.

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

Evet. Bunların hepsi geçer. Ayrıca üç veya daha fazla kenarın işe yarayacağını düşünüyorum. Ve bazı grafikler sadece bir tam yol ve diğer sarkan yollarla olacak.

@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]");
}

Ancak grafik gezintisi C3Z kenarını özlediği için bu başarısız oluyor.

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

TAMAM. Dolayısıyla grafiği sırayla yürüyemiyoruz. Bunun yerine yapmak zorunda kalacağımız şey, başlangıç düğümünden çıkan olası tüm yolları incelemek; Ve sonuna kadar, geçici değişkenlerimizi yol boyunca kaydetmek zorunda kalacağız.

Aşağıda göreceğiniz gibi, bu, bürokratik çabanın adil bir kısmını gerektiriyordu. Tüm düğümleri ve bu düğümlerle ilişkili yolları ve uzunlukları takip etmem gerekiyor. Fakat bunun dışında, algoritma aynıdır.

Döngü yinelemesi farklıdır. Başlangıç düğümünde başlar ve ardından tüm kararsız komşuları yürür ve birikmiş uzunlukları ve yolları bu komşularına depolar.

Integer.MAX_VALUE değerini “Ziyaret edilen bir düğümden erişilememiş” anlamına gelen bir temsilci olarak kullandığım unutmayın. Aramayı yalnızca ulaşılmış olan düğümlerle sınırlıyoruz, çünkü başlangıçtan bitime doğru yürüyoruz. Ulaşılmadığı herhangi bir düğüm açıkça yolda değil.

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

Bu geçer. Şimdi paralel yolları olan bir test eklemeliyiz. Başarısız olması gereken basit bir örnek:

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

Ve öyle.

Bunu başarmak için iki yolun ne zaman buluştuğunu algılamak zorundayız. Bu çok basit. Hedef düğümün uzunluğu Integer.MAX_VALUE değilse, başka bir yol bu düğüme ulaşmıştır. Minimumdan sonra olduğumuzdan, o düğüm üzerindeki uzunluğu, yakınsak yolların minimumuna basitçe ayarlayabiliriz. Integer.MAX_VALUE, “sonsuz” uzunluğun yerini tutan bu bekçi için çok uygun bir değer olur.

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

Son düğümü ziyaret ettiğimizde aramayı sonlandırarak muhtemelen algoritmayı hızlandırabiliriz.

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

Ayrıca, en kısa uzunlukla ulaşılmış olan ziyaret edilmemiş düğümleri aramayı tercih ederek algoritmayı daha da hızlandırabiliriz.

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

Bu, tüm niyet ve amaçlar için Dijkstra’nın algoritmasıdır. Bu uygulama hızlı değil çünkü setler, listeler ve çok sayıda verimsiz yapı kullandım. Hızı hızlandırmak adil bir iş parçasını gerektirir. Dahası, sabitlenmesi gereken bazı varsayımlar yapılmıştır. Özellikle giriş grafiğinin yönlendirildiği varsayılır; Oysa genel algoritma böyle bir varsayım yapmamaktadır. Sonunda, her şey biraz daha fazla yeniden düzenleme yapabilir.

Fakat amaç, TDD’yi Dijkstra’nın algoritmasına kademeli olarak yaklaşmanın mümkün olup olmadığını görmekti. Sanirim oyle; Ama yaklaşımın oldukça sarsıldığını söylemeliyim. İlk birkaç test beni birbirine düzgün biçimde girmeyen birkaç geçici algoritma ile yönlendirdi. Yine de her yeni test, daha önceki uygulamada göreceli olarak basit bir şekilde düzeltilebilecek zayıf yönleri ortaya koydu.

Kesin sarsıntı olmadan Dijkstra’nın algoritmasına daha doğrudan yol açacak daha iyi bir dizi dizi test var mı? Belki de; Ama öyleyse, ben onları bulamadım.
Final kodumuz aşağıdaki gibidir 🙂

 

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

İçeriği Paylaş:
İlginizi Çekebilir
Yorum Yapılmamış

Henüz Hiç Yorum Yapılmadı..

Yorum Yaz

Dijkstra Algoritması

Algoritmalar

19/03/2017 | Yorum Yok | 128 | Mustafa Küçükakarsu