java - Java のハッシュマップで循環依存を検出する

Question

次のハッシュマップがあります。

Tables => Set of Parent Tables [ HashMap<String, HashSet<String>> ]

非周期的なケースの例は次のとおりです。

A -> [B,C]
D -> [B,C]
B -> [C]
c -> []

周期的なケースの例は次のとおりです。

A -> [B,C]
B -> [C]
C -> [A]

周期的なケースを拒否したいので、提供されたハッシュマップに周期があるかどうかを検出できる関数が必要です:

public boolean hasDependencies(HashMap<String, HashSet<String>> objectAndItsDependentsMap)
{
   //Implementation
}

サイクルを検出するアルゴリズムを提案する投稿を読んだことがありますが、Java の初心者であるため、その知識を使用して上記の関数を構成することはできませんでした。

Answer 1

これは、あなたの例のみに基づく大まかな実装です。他の例に対してテストすることをお勧めします。

public boolean hasDependencies(Map<String, Set<String>> objectAndItsDependentsMap) {
    for (String node : objectAndItsDependentsMap.keySet()) {
        final Set<String> directNeighbors = objectAndItsDependentsMap.get(node);
        for (String directNeighbor : directNeighbors) {
            Set<String> next = objectAndItsDependentsMap.get(directNeighbor);
            while (next != null) {
                for (String n : next) {
                    next = objectAndItsDependentsMap.get(n);
                    if (next != null && (next.contains(n) || next.contains(node))) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}