disjointsets.java

bayes network classifier toolbox 贝叶斯网络分类工具箱

/**
 *  JBNC - Bayesian Network Classifiers Toolbox <p>
 *
 *  Latest release available at http://sourceforge.net/projects/jbnc/ <p>
 *
 *  Copyright (C) 1999-2003 Jarek Sacha <p>
 *
 *  This program is free software; you can redistribute it and/or modify it
 *  under the terms of the GNU General Public License as published by the Free
 *  Software Foundation; either version 2 of the License, or (at your option)
 *  any later version. <p>
 *
 *  This program is distributed in the hope that it will be useful, but WITHOUT
 *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 *  FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
 *  more details. <p>
 *
 *  You should have received a copy of the GNU General Public License along with
 *  this program; if not, write to the Free Software Foundation, Inc., 59 Temple
 *  Place - Suite 330, Boston, MA 02111-1307, USA. <br>
 *  http://www.fsf.org/licenses/gpl.txt
 */
package jbnc.graphs;

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;

/**
 *  Maintains a collection of disjoint sets. <br>
 *  <br>
 *  Coremen TH, Leiserson CE, Rivest RL. <i>Introduction to Algorithms</i> .
 *  McGrow-Hill, 1990.
 *
 * @author     Jarek Sacha
 * @since      June 1, 1999
 */
public class DisjointSets {

  /**  LOCAL  */

  /**  List of disjoint sets. */
  protected LinkedList sets;


  /** */
  DisjointSets() {
    sets = new LinkedList();
  }


  /**
   *  Put each element of <i>s</i> into a separate set containing only one
   *  element.
   *
   * @param  s              Description of Parameter
   * @exception  Exception  Description of Exception
   */
  DisjointSets(Object[] s) throws Exception {
    this();

    //Test that objects in the vector are unique
    if (!isUnique(s)) {
      throw new Exception("DisjointSets:"
          + " objects in vector s are not all unique.");
    }

    // Create sets
    for (int i = 0; i < s.length; ++i) {
      LinkedList si = new LinkedList();
      si.add(s[i]);
      sets.add(si);
    }
  }


  /**
   *  Test the class operation.
   *
   * @param  argv  Description of Parameter
   */
  public static void main(String argv[]) {
    try {
      System.out.println("\nTesting class DisjointSet");

      System.out.println("\nInitialize");

      Integer[] items = new Integer[10];
      for (int i = 0; i < items.length; ++i) {
        items[i] = new Integer(i);
      }

      DisjointSets ds = new DisjointSets(items);
      ds.printSets();

      System.out.println("\nmakeSet(Integer(10))");
      ds.makeSet(new Integer(10));
      ds.printSets();

      System.out.println("\nunion({3}, {5})");
      ds.union(items[3], items[5]);
      ds.printSets();

      System.out.println("\nunion({3}, {7})");
      ds.union(items[3], items[7]);
      ds.printSets();

      System.out.println("\nfindSet({5}) = " + ds.findSet(items[5]).toString());
      ds.printSets();
    } catch (Exception e) {
      e.printStackTrace();
    }
  }


  /**
   *  Create a new set whose only member (and thus representative) is pointed by
   *  <i>x</i> . Since sets are disjoint, we require that <i>x</i> not already
   *  be in a set.
   *
   * @param  x              Description of Parameter
   * @exception  Exception  Description of Exception
   */
  public void makeSet(Object x) throws Exception {
    if (x == null) {
      throw new Exception("DisjointSets.makeSet:"
          + " memeber x is null.");
    }

    if (findSet(x) != null) {
      throw new Exception("DisjointSets.makeSet:"
          + " memeber x is already present.");
    }

    LinkedList si = new LinkedList();
    si.add(x);
    sets.add(si);
  }


  /**
   *  Unites the dynamic sets that contain <i>x</i> and <i>y</i> , say <i>S<sub>
   *  x</sub> </i> and <i>S<sub>y</sub> </i> , into a new set that is the union
   *  of these sets. The representative of the resulting set is some member of
   *  <nobr><i>S<sub>x</sub> </i> U <i>S<sub>y</sub> </i> </nobr> . Original
   *  sets <i>S<sub>x</sub> </i> and <i>S<sub>y</sub> </i> are destroyed.
   *
   * @param  x              Description of Parameter
   * @param  y              Description of Parameter
   * @exception  Exception  Description of Exception
   */
  public void union(Object x, Object y) throws Exception {
    if (x == null || y == null) {
      throw new Exception("DisjointSets.union:"
          + " memebers x or y are null.");
    }

    // Find sets Sx and Sy
    LinkedList sx = findTheSet(x);
    LinkedList sy = findTheSet(y);
    if (sx == null || y == null) {
      throw new Exception("DisjointSets.union:"
          + " memebers x or y are not present.");
    }

    // Merge sets
    LinkedList sxy = new LinkedList(sx);
    for (Iterator i = sy.iterator(); i.hasNext(); sxy.add(i.next())) {
      ;
    }

    sets.add(sxy);

    // Remove Sx and Sy
    sets.remove(sx);
    sets.remove(sy);
  }


  /**
   *  Returns a pointer to the representative of the (unique) set containing <i>
   *  x</i> .
   *
   * @param  x  Description of Parameter
   * @return    Description of the Returned Value
   */
  public Object findSet(Object x) {
    LinkedList s = findTheSet(x);

    if (s == null) {
      return null;
    }

    Iterator i = s.iterator();
    if (i.hasNext()) {
      return i.next();
    } else {
      return null;
    }
  }


  /**
   *  Test if elements of a vector are unique and are null.
   *
   * @param  s  Description of Parameter
   * @return    The Unique value
   */
  boolean isUnique(Object[] s) {
    HashSet h = new HashSet();
    for (int i = 0; i < s.length; ++i) {
      if (s[i] == null) {
        return false;
      } else {
        h.add(s[i]);
      }
    }

    return (h.size() == s.length);
  }


  /**
   *  Find the set containing element x.
   *
   * @param  x  Description of Parameter
   * @return    Description of the Returned Value
   */
  LinkedList findTheSet(Object x) {
    Iterator i = sets.iterator();
    LinkedList s = null;
    while (i.hasNext()) {
      LinkedList si = (LinkedList) i.next();
      if (si.contains(x)) {
        s = si;
        break;
      }
    }

    return s;
  }


  /**  Print set members */
  void printSets() {
    int counter = 0;
    Iterator si = sets.iterator();
    while (si.hasNext()) {
      LinkedList s = (LinkedList) si.next();

      System.out.print("Set #" + counter + ": {");
      Iterator mi = s.iterator();
      while (mi.hasNext()) {
        System.out.print(mi.next().toString() + " ");
      }

      System.out.println("}");
    }
  }
}