[Java] 深さ優先探索によるトポロジカルソート

TopologicalSorter.java

/**
 * 深さ優先探索によるトポロジカルソート.
 * 参考: http://ja.wikipedia.org/wiki/トポロジカルソート
 * @param <T> ノードキーの型
 */
public class TopologicalSorter<T> {
  private final Map<T, Set<T>> nodes;
  private final List<T> result;
  /** 訪問済のノードキー群 */
  private final Set<T> visited;

  /**
   * @param nodes ソート対象のノード群
   */
  public TopologicalSorter(Map<T, Set<T>> nodes) {
    this.nodes = nodes;
    this.result = new ArrayList<T>();
    this.visited = new HashSet<T>();
    sort();
  }

  private void sort() {
    for (Map.Entry<T, Set<T>> node : nodes.entrySet()) {
      visit(node.getKey(), node.getValue());
    }
  }

  private void visit(T key, Set<T> nextNodes) {
    if (visited.contains(key) || !nodes.containsKey(key)) {
      return;
    }
    visited.add(key);
    for (T nextNode : nextNodes) {
      visit(nextNode, nodes.get(nextNode));
    }
    result.add(key);
  }

  /**
   * @return ソート結果のリスト
   */
  public List<T> getResult() {
    return new ArrayList<T>(result);
  }
}

TopologicalSorterTest.java

import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;

import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

public class TopologicalSorterTest {

  @Test
  public void testGetResult_Empty() {
    Map<String, Set<String>> nodes = new LinkedHashMap<String, Set<String>>();

    List<String> result = new TopologicalSorter<String>(nodes).getResult();

    assertThat(result.size(), is(0));
  }

  @Test
  public void testGetResult_SingleNode() {
    Map<String, Set<String>> nodes = new LinkedHashMap<String, Set<String>>();
    nodes.put("node1", Collections.<String>emptySet());

    List<String> result = new TopologicalSorter<String>(nodes).getResult();

    assertThat(result.size(), is(1));
    assertThat(result.get(0), is("node1"));
  }

  @Test
  public void testGetResult_IndependentNodes() {
    Map<String, Set<String>> nodes = new LinkedHashMap<String, Set<String>>();
    nodes.put("node1", Collections.<String>emptySet());
    nodes.put("node2", Collections.<String>emptySet());

    List<String> result = new TopologicalSorter<String>(nodes).getResult();

    assertThat(result.size(), is(2));
    Iterator<String> it = result.iterator();
    assertThat(it.next(), is("node1"));
    assertThat(it.next(), is("node2"));
  }

  @Test
  public void testGetResult_DependNode() {
    Map<String, Set<String>> nodes = new LinkedHashMap<String, Set<String>>();
    nodes.put("node1", asSet("node2"));
    nodes.put("node2", Collections.<String>emptySet());

    List<String> result = new TopologicalSorter<String>(nodes).getResult();

    assertThat(result.size(), is(2));
    Iterator<String> it = result.iterator();
    assertThat(it.next(), is("node2"));
    assertThat(it.next(), is("node1"));
  }

  @Test
  public void testGetResult_MultiDependNode() {
    Map<String, Set<String>> nodes = new LinkedHashMap<String, Set<String>>();
    nodes.put("node1", asSet("node2", "node3"));
    nodes.put("node2", Collections.<String>emptySet());
    nodes.put("node3", Collections.<String>emptySet());

    List<String> result = new TopologicalSorter<String>(nodes).getResult();

    assertThat(result.size(), is(3));
    Iterator<String> it = result.iterator();
    assertThat(it.next(), is("node2"));
    assertThat(it.next(), is("node3"));
    assertThat(it.next(), is("node1"));
  }

  @Test
  public void testGetResult_DependMultiNodes() {
    Map<String, Set<String>> nodes = new LinkedHashMap<String, Set<String>>();
    nodes.put("node1", asSet("node2"));
    nodes.put("node2", Collections.<String>emptySet());
    nodes.put("node3", asSet("node2"));

    List<String> result = new TopologicalSorter<String>(nodes).getResult();

    assertThat(result.size(), is(3));
    Iterator<String> it = result.iterator();
    assertThat(it.next(), is("node2"));
    assertThat(it.next(), is("node1"));
    assertThat(it.next(), is("node3"));
  }

  @Test
  public void testGetResult_DependDeep() {
    Map<String, Set<String>> nodes = new LinkedHashMap<String, Set<String>>();
    nodes.put("node1", asSet("node2"));
    nodes.put("node2", asSet("node3"));
    nodes.put("node3", Collections.<String>emptySet());

    List<String> result = new TopologicalSorter<String>(nodes).getResult();

    assertThat(result.size(), is(3));
    Iterator<String> it = result.iterator();
    assertThat(it.next(), is("node3"));
    assertThat(it.next(), is("node2"));
    assertThat(it.next(), is("node1"));
  }

  @Test
  public void testGetResult_LoopSingleNode() {
    Map<String, Set<String>> nodes = new LinkedHashMap<String, Set<String>>();
    nodes.put("node1", asSet("node1"));

    List<String> result = new TopologicalSorter<String>(nodes).getResult();

    assertThat(result.size(), is(1));
    Iterator<String> it = result.iterator();
    assertThat(it.next(), is("node1"));
  }

  @Test
  public void testGetResult_LoopMultiNodes() {
    Map<String, Set<String>> nodes = new LinkedHashMap<String, Set<String>>();
    nodes.put("node1", asSet("node2"));
    nodes.put("node2", asSet("node1"));

    List<String> result = new TopologicalSorter<String>(nodes).getResult();

    assertThat(result.size(), is(2));
    Iterator<String> it = result.iterator();
    assertThat(it.next(), is("node2"));
    assertThat(it.next(), is("node1"));
  }

  @Test
  public void testGetResult_DependNodeKeyNotExists() {
    Map<String, Set<String>> nodes = new LinkedHashMap<String, Set<String>>();
    nodes.put("node1", asSet("node2"));

    List<String> result = new TopologicalSorter<String>(nodes).getResult();

    assertThat(result.size(), is(1));
    Iterator<String> it = result.iterator();
    assertThat(it.next(), is("node1"));
  }

  private <T> Set<T> asSet(T... items) {
    return new LinkedHashSet<T>(Arrays.asList(items));
  }
}