今回はトポロジカルソートというアルゴリズムを説明します。

トポロジカルソートは有効グラフの位相順序を求めるアルゴリズムです。といっても誰も分かってくれないと思うので分かりやすく説明しますと、ある非循環有向グラフがあるとして、全ての辺(u, v) に対して

頂点 u の番号 < 頂点 v の番号

となるように接点の番号をつけるアルゴリズムです。

非循環有向グラフであるの必要があるのは、循環していると上の不等式が成り立たなくなるためです。

Javaによるサンプルコードを示します。

sort/TopologicalSort.java

package sort;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class TopologicalSort {
  public static class Node {
    private String name;
    private Set<Node> edges;
    public Node(String name) {
      this.name = name;
      this.edges = new HashSet<Node>();
    }

    public String getName() {
      return this.name;
    }

    public Iterable<Node> getEdges() {
      return this.edges;
    }

    public void addEdgeTo(Node node) {
      this.edges.add(node);
    }

    public String toString() {
      return this.name;
    }
  }

  private static void tsortWithResult(Node root, List<Node> result) {
    for (Node node : root.edges) {
      if (!result.contains(node)) {
        tsortWithResult(node, result);
      }
    }
    result.add(root);
  }

  public static List<Node> tsort(Node root) {
    List<Node> result = new ArrayList<Node>();
    tsortWithResult(root, result);return result;
  }

  public static void main(String[] args) {
    final Node OBJECT = new Node("Object");
    final Node ABSTRACT_COLLECTION = new Node("AbstractCollection");
    final Node ABSTRACT_LIST = new Node("AbstractList");
    final Node ARRAY_LIST = new Node("ArrayList");
    final Node SERIALIZABLE = new Node("Serializable");
    final Node CLONEABLE = new Node("Cloneable");
    final Node ITERABLE = new Node("Iterable");
    final Node COLLECTION = new Node("Collection");
    final Node LIST = new Node("List");
    final Node RANDOM_ACCESS = new Node("RandomAccess");

    COLLECTION.addEdgeTo(ITERABLE);

    LIST.addEdgeTo(COLLECTION);

    ABSTRACT_COLLECTION.addEdgeTo(OBJECT);
    ABSTRACT_COLLECTION.addEdgeTo(COLLECTION);
    ABSTRACT_LIST.addEdgeTo(ABSTRACT_COLLECTION);
    ABSTRACT_LIST.addEdgeTo(LIST);
    ARRAY_LIST.addEdgeTo(ABSTRACT_LIST);
    ARRAY_LIST.addEdgeTo(SERIALIZABLE);
    ARRAY_LIST.addEdgeTo(CLONEABLE);
    ARRAY_LIST.addEdgeTo(RANDOM_ACCESS);
    System.out.println(tsort(ARRAY_LIST));
  }
}

このコードでは ArrayList クラスの継承関係を表す非循環有向グラフをトポロジカルソートしています。

実行すると下記のように出力されます。

[Cloneable, Serializable, RandomAccess, Iterable, Collection, List, Object, AbstractCollection, AbstractList, ArrayList]

これが何を意味するかというと、例えば、ArrayList クラスを実装(コンパイル)するには継承(依存)するクラス、インターフェースが既に実装されている必要があります。ソートされた結果の順番に実装していくことで、スーパークラスやインターフェースが未実装でコンパイルできないといったことにならずに実装することができます。