4

ここに画像の説明を入力してください

渡されたパラメータノードのルートを指すようにすることで、特定のノードのすべての祖先を圧縮しようとしています。

 private E compressToRoot (E e) throws IllegalArgumentException;

たとえば、上の画像でcompressToRoot（D）を実行した場合、DはAを直接指し、CはAを直接指します。パラメーターとルートの間に他のノードがある場合、それらはすべてAを指します。

すべてのラベルと矢印は、2つの別々のマップに保存されます。

private Map<E,E>       parentMap   = new HashMap<E,E>(); //labels + arrows

この方法は、（1）Dとルートの間のすべてのノードをセットで保持することで完了できます。（2）セットポイントのすべての要素をルート（親にする）にする（3）ルートを返す。

ただし、このマップをトラバースしてルートに到達する方法に固執しています。だから、この方法では、私は次のようなことをします

private E compressToRoot (E e) throws IllegalArgumentException {
    Set<E> collectLables = new HashSet<E>();
E root = null;

//get root.
for (E cycle : parentMap.keys()) {
    while (parentMap.get(e) != e) 
        e = parentMap.get(e);
        if (parentMap.get(e) == e)
            root = cycle;
 }


//collect all labels from parameter to root.
for (E element : parentMap.keys()) {
    while (parentMap.get(e) != root) {
        collectLables.add(element);
    }   
}


}

しかし、特定のノードの親をルートまで循環させる方法がわかりません。

4

3 に答える 3

1

このマップをトラバースしてルートに到達する方法に固執しています。

「ルート」の定義は、それ自体を指す唯一のノードのようです。これは特に効率的ではありませんが、そのような要素を探すことができます。

E findRoot(Map<E, E> parentMap) {
    for (Map.Entry<E, E> entry: parentMap.entrySet() {
        if (entry.key().equals(entry.value()) {
            return entry;
        }
    }

    // parentMap is empty, or the graph is corrupted
    // handle this edge case however you want
    return null;
}
于 2012-12-01T01:17:29.187 に答える
1

再帰はきれいですが、ルートまでの最長のパスの長さが長くなる可能性がある場合は、反復法をお勧めします。スタックを使い果たしたくありません。

private E compressToRoot(E node) {
    if (parentMap.get(node) != node)
        parentMap.set(node, compressToRoot(node));
    return parentMap.get(node);
}

private E compressToRoot(E cursor) {
    E node;
    ArrayList<E> nodes = new ArrayList<E>();
    while ((node = parentMap.get(cursor)) != cursor)  {
        nodes.add(cursor);
        cursor = node;
    }

    for (node : nodes)
        parentMap.set(node, cursor);

    return cursor;
}
于 2012-12-01T05:18:23.540 に答える
1

マップの効率に応じて、上記のランボーコーダーの回答がわずかに改善される可能性があります。ArrayListパスを2回トラバースするだけで、の余分なメモリとオーバーヘッドを使用せずにそれを行うことができます。

private E compressToRoot(E cursor) {
    E cursor2 = cursor;
    E node = parentMap.get(cursor);
    while (node != cursor)  {
        cursor = node;
        node = parentMap.get(node);
    }
    // Now cursor (and node) are the root.    

    node = parentMap.get(cursor2);
    while (node != cursor2) {
        parentMap.set(cursor2, cursor);
        cursor2 = node;
        node = parentMap.get(node);
    }

    return cursor;
}
于 2012-12-02T20:53:38.790 に答える