2 つのグラフを結合する方法がわかりません。以下の図を参照してください。
ここで、ルートを A と E として 2 つのグラフをマージします。E の方が小さいため、より大きなグラフ A のルートを指すようにします。compressToRoot()その間のすべてのノードを作成するパラメータを受け取る関数があります。それ自体とルートは、自己参照ルートを指します (したがって、compressToRoot(D): D->A、C->A、B->A)。私にその機能があれば、
public Equivalence<E> mergeClassesContaining(E a, E b);
最初compressToRoot(a)にcompressToRoot(b)、それらが同じ等価クラスの一部でない場合 - たとえば、D と F は異なりますが、C と D は同じです。次に、小さい方 (右、EF) を取得し、そのルートを左側の大きい方とマージして、右側のルートを作成します。次に、左側のサイズを更新し、サイズを決定するマップから右側のルートを削除しrootSizeMapます。2 つのクラス インスタンス変数がrootSizeMapあり、parentMap以下に示します。
private Map<E,E> parentMap = new HashMap<E,E>(); //maps node to parent
private Map<E,Integer> rootSizeMap = new HashMap<E,Integer>(); //maps node to size of class
mergeClassesContaining(E a, E b)どちらが小さいグラフであるかを判断し、そのルートを大きいグラフに向けるように関数を完成させるにはどうすればよいですか? この場合、グラフはその中の「ノード」の数に基づいて大きくなったり小さくなったりします。たとえば、左は 4、右は 2 です。
public Equivalence<E> mergeClassesContaining(E a, E b) throws IllegalArgumentException {
if (!inSameClass(a, b)) { //private function to determine if the given parameters are in the same class.
//need help here.
return this;
}
}
これが compressToRoot 関数です。
private E compressToRoot (E e) throws IllegalArgumentException {
E node;
ArrayList<E> nodes = new ArrayList<E>();
while ((node = parentMap.get(e)) != e) {
nodes.add(e);
e = node;
}
for (E element : nodes)
((ArrayList<E>) parentMap).set((Integer) node, e);
return e;
}
完全なコード:
public class HashEquivalence<E> implements Equivalence<E> {
public Equivalence<E> addSingletonClass (E e) throws IllegalArgumentException {
if (parentMap.containsKey(e))
throw new IllegalArgumentException("HashEquivalence.addSingletonClass: e(" +e+ ") already in an equivalence class");
parentMap.put(e,e); //its own parent
rootSizeMap.put(e,1); //its equivalence class has 1 value in it
return this;
}
private E compressToRoot (E e) throws IllegalArgumentException {
E node;
ArrayList<E> nodes = new ArrayList<E>();
while ((node = parentMap.get(e)) != e) {
nodes.add(e);
e = node;
}
for (E element : nodes)
((ArrayList<E>) parentMap).set((Integer) node, e);
return e; //Allows method to compile
}
public boolean inSameClass(E a, E b) throws IllegalArgumentException {
if (!parentMap.containsKey(a))
throw new IllegalArgumentException("HashEquivalence.inSameClass: a(" +a+ ") not in an equivalence class");
if (!parentMap.containsKey(b))
throw new IllegalArgumentException("HashEquivalence.inSameClass: b(" +b+ ") not in an equivalence class");
return compressToRoot(a) == compressToRoot(b);
}
public Equivalence<E> mergeClassesContaining(E a, E b) throws IllegalArgumentException {
if (!inSameClass(a,b))
return this;
}
public Set<Set<E>> allClasses () {
Map<E,Set<E>> answerMap = new HashMap<E,Set<E>>();
for (E e : parentMap.keys()) {
E root = compressToRoot(e);
Set<E> s = answerMap.get(root);
if (s == null)
answerMap.put(root, s = new HashSet<E>());
s.add(e);
}
return new HashSet<Set<E>>(1.0,answerMap.values());
}
public int numberOfClasses ()
{return rootSizeMap.size();}
public int numberOfMembers ()
{return parentMap.size();}
private Map<E,Integer> heights () {
Map<E,Integer> answer = new HashMap<E,Integer>();
for (E element : parentMap.keys()) {
E e = element;
int depth = 0;
while (parentMap.get(e) != e) {
e = parentMap.get(e);
depth++;
}
Integer soFar = answer.get(e);
if (soFar == null || soFar < depth)
answer.put(e, depth);
}
return answer;
}
public int maxHeight () {
return Collections.max(heights().values());
}
public void showMaps() {
System.out.println("parentMap (as list) = " + new ArrayList<Map.Entry<E,E>>(parentMap.entries()));
System.out.println("rootSizeMap (as list) = " + new ArrayList<Map.Entry<E,Integer>>(rootSizeMap.entries()));
System.out.println("heightMap (as list) = " + new ArrayList<Map.Entry<E,Integer>>(heights().entries()));
System.out.println("max height of tree = " + maxHeight());
}
private Map<E,E> parentMap = new HashMap<E,E>();
private Map<E,Integer> rootSizeMap = new HashMap<E,Integer>();
}