Java UnionFindNode Example

说明

java unionfindnode示例是从最受好评的开源项目中提取的实现代码,你可以参考下面示例的使用方式。

编程语言: Java

类/类型: UnionFindNode

示例#1
文件: UnionFindFind.java项目: PaLy/alg-vis

 @Override
 public void runAlgorithm() throws InterruptedException {
   setHeader("uffind");
   final UnionFindNode v = find(u);
   v.setColor(NodeColor.NORMAL);
   addNote("done");
 }

示例#2
文件: UnionFindFind.java项目: PaLy/alg-vis

  UnionFindNode findSimple(UnionFindNode u) throws InterruptedException {
    final Stack<UnionFindNode> S = new Stack<UnionFindNode>();
    UnionFindNode result = null;
    UnionFindNode v = null;

    u.setColor(NodeColor.FIND);
    u.mark();
    addStep("uffindstart", u.getKey());
    pause();

    // u is a representative
    if (u.getParent() == null) {
      u.setColor(NodeColor.FOUND);
      addStep("ufalreadyroot");
      pause();
      u.unmark();
      return u;
    }

    v = u;

    // looking for root
    while (v.getParent() != null) {
      S.add(v);
      v.setColor(NodeColor.FIND);
      addStep("ufup");
      pause();
      v = v.getParent();
    }

    // root found
    result = v;
    v.setColor(NodeColor.FOUND);
    addStep("ufrootfound", result.getKey());
    pause();

    // traveling back
    while (!S.empty()) {
      v = S.pop();
      v.setColor(NodeColor.NORMAL);
    }

    // u.bgcolor = Colors.NORMAL;
    u.unmark();

    return result;
  }

示例#3
文件: UnionFindFind.java项目: PaLy/alg-vis

  UnionFindNode findSplitting(UnionFindNode u) throws InterruptedException {
    UnionFindNode result = null;
    UnionFindNode v = null;

    u.setColor(NodeColor.FIND);
    u.mark();
    addStep("uffindstart", u.getKey());

    // grey path
    UnionFindNode t = u;
    while (t.getParent() != null) {
      t.setGrey(true);
      t = t.getParent();
    }

    pause();

    // u is a representative
    if (u.getParent() == null) {
      u.setColor(NodeColor.FOUND);
      addStep("ufalreadyroot");
      pause();
      u.unmark();
      return u;
    }

    v = u;
    UnionFindNode grandchild = null;
    UnionFindNode child = null;

    // looking for root
    if (v.getParent() != null) {
      grandchild = v;
      v.setColor(NodeColor.INSERT);
    }

    if (v.getParent() != null) {
      addStep("ufup");
      pause();
      v.setColor(NodeColor.FIND);
      v = v.getParent();
      child = v;
      v.setColor(NodeColor.INSERT);
    }

    if (v.getParent() != null) {
      do {
        addStep("ufup");
        pause();
        v.setColor(NodeColor.FIND);
        v = v.getParent();
        v.setColor(NodeColor.INSERT);
        grandchild.setColor(NodeColor.CACHED);
        addStep("ufupspecial");
        pause();
        grandchild.setColor(NodeColor.NORMAL);
        grandchild.getParent().deleteChild(grandchild);
        v.addChild(grandchild);
        UF.reposition();
        grandchild.setColor(NodeColor.NORMAL);
        grandchild = child;
        child = v;
      } while (v.getParent() != null);
    }

    // root found
    if (grandchild != null) {
      grandchild.setColor(NodeColor.NORMAL);
    }
    if (child != null) {
      child.setColor(NodeColor.NORMAL);
    }
    v.setColor(NodeColor.FOUND);
    result = v;
    addStep("ufrootfound", result.getKey());
    pause();

    u.unmark();
    result.setGrey(false);
    return result;
  }

示例#4
文件: UnionFindFind.java项目: PaLy/alg-vis

  UnionFindNode findWithCompression(UnionFindNode u) throws InterruptedException {
    final Stack<UnionFindNode> S = new Stack<UnionFindNode>();
    UnionFindNode result = null;
    UnionFindNode v = null;

    u.setColor(NodeColor.FIND);
    u.mark();
    addStep("uffindstart", u.getKey());
    pause();

    // u is a representative
    if (u.getParent() == null) {
      u.setColor(NodeColor.FOUND);
      addStep("ufalreadyroot");
      pause();
      u.unmark();
      return u;
    }

    v = u;

    // looking for root
    while (v.getParent() != null) {
      S.add(v);
      // v.setColor(NodeColor.FIND);
      v.setGrey(true);
      addStep("ufup");
      pause();
      v = v.getParent();
    }

    // root found
    result = v;
    v.setColor(NodeColor.FOUND);
    addStep("ufrootfound", result.getKey());
    addStep("ufdownstart");
    pause();

    // don't compress a path of a son of a root
    if (!S.empty()) {
      addStep("ufdownson");
      pause();
      v = S.pop();
      v.setColor(NodeColor.NORMAL);
    }

    while (!S.empty()) {
      addStep("ufdown");
      v = S.pop();
      // v.pointTo(result);
      pause();
      // v.noArrow();
      v.setColor(NodeColor.NORMAL);
      v.getParent().deleteChild(v);
      UF.reposition();
      // pause();
      result.addChild(v);
      UF.reposition();
      // pause();
    }

    // u.bgcolor = Colors.NORMAL;
    pause();
    u.unmark();
    result.setGrey(false);
    return result;
  }

展开阅读全文