0

我不明白如何让两个图表合并在一起。见下图： 在此处输入图像描述

在这里，我想将两个图与根合并为 A 和 E。由于 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. 我有两个类实例变量，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>();
}
4

0 回答 0