simplegeneratingtree.java

dm s preparing process. In this case we use O distance.

/* created at 2005-12-30 */
package com.clustering.core;

import java.io.CharArrayWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

import com.clustering.ds.tree.Tree;

/**
 * 这个树就是无向网的生成树，以后会根据这个树创建等价矩阵.
 * <p>
 * 这个树也是一个视图，用来观察创建等价矩阵的一个中间步骤。
 * <p>
 * 
 * 
 * @author Avon
 * @version 0.9
 * @since 0.9
 * @see SimpleFuzzyGraph
 */
public class SimpleGeneratingTree implements Tree {
	private SimpleFuzzyMatrix matrix;

	private boolean isUpperTriangleTree;

	private CharArrayWriter cWriter;

	private PrintWriter out;

	/*
	 * branches, powers,values 暴露给该包中的SimpleEquivalentMatrix，暴露也是没有办法的，
	 * 要不就把SimpleFuzzyGraph、SimpleGeneratingTree作为SimpleFuzzyMatrix的内部类实现。
	 * 就不应该建立图、树的类，虽然是按照图、树中的一些方法计算，但也没有必要建立这些类
	 */
	Branch[] branches;

	double[] powers;

	Object[] values;

	private boolean isLoggingSort;

	// 用来记录一共选了多少个边
	private int selectedEdgeNum;

	/**
	 * 这个构造函数应该添加一个boolean以标志是否标志是否记录排序
	 * 
	 * @param matrix
	 */
	public SimpleGeneratingTree(SimpleFuzzyMatrix matrix, boolean isLogingSort) {
		this.matrix = matrix;
		values = matrix.values();
		isUpperTriangleTree = false;
		selectedEdgeNum = 0;
		/*
		 * if(null==sort) { this.sort = new DefaultSort(values,true,new
		 * Comparator() {
		 * 
		 * public int compare(Object o1, Object o2) { Double d1 = (Double)o1;
		 * Double d2 = (Double)o2; if(d1 > d2) return 1; else if (d1<d2) return
		 * -1; else return 0; }
		 * 
		 * @Override public boolean equals(Object obj) { return 0==compare(this,
		 * obj); } }); } else { this.sort = sort; }
		 */
		cWriter = new CharArrayWriter();
		out = new PrintWriter(cWriter);
		this.isLoggingSort = isLogingSort;
		if (isLogingSort) {
			out.println("While constructing this generating tree, the pragram sorts the edge below. "
					+ "The sorts below is only the records which has been used  ,but not the "
					+ "whole sequence's sorting result.The edge which is marked with \"*\" means that "
					+ "the edge is selected by generating tree, otherwies the edge is not selected by "
					+ "generating tree.");
		}
		buildTree();
	}

	public int getRoot() {
		return 0;
	}

	/*
	 * 建立生成树
	 */
	private void buildTree() {
		int bound = (int) matrix.getBound();

		// 无向网中的所有边
		Branch[] cs = new Branch[(int) (bound * (bound - 1) / 2)];
		int count = 0;
		// 上三角阵 列优先
		if (isUpperTriangleTree) {
			for (int row = 0; row < bound; row++)
				for (int col = row + 1; col < bound; col++)
					cs[count++] = new Branch(row, col);
		}
		// 下三角 行优先
		else {
			for (int col = 0; col < bound; col++)
				for (int row = col + 1; row < bound; row++)
					cs[count++] = new Branch(row, col);
		}

		// 降序选出的不会成环n-1条边的权，缓存
		powers = new double[bound - 1];
		// n-1个叉
		branches = new Branch[bound - 1];

		/* 计算无向图的生成树，这是自己想的，没有证明，如果有算法，那么应该考虑修改此处 */
		// 保存连通集合的集合
		ArrayList<HashSet<Integer>> collection = new ArrayList<HashSet<Integer>>();

		count = 0;
		// 运行次数不少与bound-1次，while循环实际运行次数大于bound-1
		/*
		 * int count1 = 0; int count2 = 0; int count3 = 0; int count4 = 0;
		 */

		while (count < bound - 1) {
			selectedEdgeNum++;
			// 选择权最大的弧，这条弧不一定能加入图中
			Branch branch = getNextMaxCoordinate(cs, powers, count);
			// xset是brach.x所在的集合，yset是branch.y所在的集合,xset和yset都是collection中的元素
			HashSet<Integer> xset = null;
			HashSet<Integer> yset = null;
			// 选了一次边
			// 遍历collection，看branch.x, branch.y在哪个collection中
			for (Iterator<HashSet<Integer>> iter = collection.iterator(); iter.hasNext();) {
				HashSet<Integer> connectedSet = iter.next();
				if (null == xset)
					if (connectedSet.contains(branch.x))
						xset = connectedSet;
				if (null == yset)
					if (connectedSet.contains(branch.y))
						yset = connectedSet;
				if (null != xset && null != yset) {
					break;
				}
			}

			// 统计一下，选择一个号的if顺序
			// 回路情况，branch.x和branch.y都在同一个连通集合中，舍弃这条叉
			// 发生回路的情况很多
			if (null != xset && null != yset) {
				// count1++;
				// 如果branch.x 和 branch.y在同一个连通集合中，不能添加这条边
				if (xset.equals(yset)) {
					if (isLoggingSort) {
						out.println();
					}
					continue;
				}
				// branch.x 和 branch.y不在同一个连通集合，那么合并这两个连通集合
				else {
					xset.addAll(yset);
					collection.remove(yset);
				}
			}
			// branch.x在连通集合中，branch.y不在连通集合中
			else if (null != xset && null == yset) {
				// count2++;
				xset.add(branch.y);
			}
			// branch.y在连通集合中，branch.x不在连通集合中
			else if (null == xset && null != yset) {
				// count3++;
				yset.add(branch.x);
			}
			// branch.x和branch.y都不在联通集合中，建立这个连通集合
			else {
				// count4++;
				xset = new HashSet<Integer>();
				xset.add(branch.x);
				xset.add(branch.y);

				// 把新创建的连通集合保存到连同集合的集合中
				collection.add(xset);
			}

			// 保存这条边，这条边将作为第count条叉添加到生成树中
			branches[count] = branch;
			/*
			 * 无需记录权值，权值已经在getNextMaxCoordinate中记录完毕 ! powers[count] =
			 * matrix.getElement(branch.x, branch.y);
			 */
			count++;
			if (isLoggingSort) {
				out.print(' ');
				out.print('*');
				out.print(" , the edge number in generating tree");
				out.print(" ");
				out.println(count);
			}
			// 从set中移除beanch.x、branch.y
		}
		/* 最终将使set为空，collection中只有一个HashSet，这个HashSet保含图中所有顶点 */
		/* 无向图的生成树计算完毕 */
		/*
		 * System.out.println("***********************************");
		 * System.out.println(count1); System.out.println(count2);
		 * System.out.println(count3); System.out.println(count4);
		 * System.out.println("***********************************");
		 */
		// 清空矩阵
		for (int i = 0; i < values.length; i++) {
			values[i] = null;
		}
		// 把树存储在矩阵中
		for (int i = 0; i < branches.length; i++) {
			values[getIndex(branches[i].x, branches[i].y)] = new Double(powers[i]);
		}
		if (isLoggingSort) {
			boolean flag = (selectedEdgeNum / (bound - 1) * bound) > 0.6;
			if (flag) {
				out.print(selectedEdgeNum);
				out.print(" edges is sorted. Maybe use quick sorting to sort all elements[");
				out.print((bound - 1) * bound / 2);
				out.println("] can improve effiency.");
			} else {
				out.print("Only ");
				out.print(selectedEdgeNum);
				out.println(" edges is sorted. Here sorting only the elements which is used is more "
						+ "efficient than sorting all");
			}
			out.println();
		}
	}

	private int getIndex(int r, int c) {
		if (r > c) {
			return r * (r + 1) / 2 + c;
		}
		return c * (c + 1) / 2 + r;
	}

	/*
	 * 由于要求堆排序不稳定，所以只能使用选择排序，这里并没有完全排序.
	 * cs是所有未排序的边的集合，powers和cur用来帮助cs标记已排序的记录。这个方法本属于buildTree的一部分
	 * 挺难受的签名，如果写成getNextMaxCoordinate(Branch[] cs)也不能好到哪里去，这个排序就不独立了
	 */

	private Branch getNextMaxCoordinate(Branch[] cs, double[] powers, int cur) {
		// index只是一个临时变量,cs的c是cordinate的意思
		int index = 0;
		for (int i = 0; i < cs.length; i++)
			if (null == cs[i])
				index++;
			else
				break;
		Branch c = cs[index];
		// 认为这样能快点
		double max = 1 - matrix.getP() * ((Double) values[getIndex(c.x, c.y)]).doubleValue();
		double d = 0;
		// 用选择排序找最大弧，要求稳定性
		for (int i = index + 1; i < cs.length; i++) {
			if (null == cs[i])
				continue;
			d = 1 - matrix.getP() * ((Double) values[getIndex(cs[i].x, cs[i].y)]).doubleValue();
			if (max < d) {
				max = d;
				c = cs[i];
				index = i;
			}
		}
		if (isLoggingSort) {
			out.print('\t');
			out.print(selectedEdgeNum);
			out.print(". [");
			out.print(cs[index].x);
			out.print(',');
			out.print(' ');
			out.print(cs[index].y);
			out.print(']');
		}
		// 记录branch的权值
		powers[cur] = max;
		c = cs[index];
		// cs中去掉已排序的记录
		cs[index] = null;
		return c;
	}

	public boolean isUpperTriangleTree() {
		return isUpperTriangleTree;
	}

	public void setUpperTriangleTree(boolean isUpperTriangleTree) {
		if (isUpperTriangleTree != this.isUpperTriangleTree) {
			this.isUpperTriangleTree = isUpperTriangleTree;
			buildTree();
		}
	}

	public SimpleFuzzyMatrix getMatrix() {
		return matrix;
	}

	public void setMatrix(SimpleFuzzyMatrix matrix) {
		// 深度比较
		if (!this.matrix.equals(matrix)) {
			Object[] values1 = this.matrix.values();
			Object[] values2 = matrix.values();
			boolean isEquals = true;
			if (values1.length != values2.length) {
				isEquals = false;
				for (int i = 0; i < values1.length && isEquals; i++) {
					if (values1[i] != values2[i]) {
						isEquals = false;
						break;
					}
				}
			}
			if (!isEquals) {
				this.matrix = matrix;
				buildTree();
			}
		}
	}

	@Override
	public String toString() {
		out.print("While constructing this tree, chose ");
		out.print(selectedEdgeNum);
		out.print(" edge. Among the edges, ");
		out.print(selectedEdgeNum - matrix.getBound() + 1);
		out.println(" edges arosed cycle to the tree.");
		for (int i = 0; i < branches.length; i++) {
			out.print('\t');
			out.print(i);
			out.print("th generating tree edge: ");
			out.print(branches[i].x.toString());
			out.print(" to ");
			out.print(branches[i].y.toString());
			out.printf(", pow=%.3f", powers[i]);
			out.println();
		}
		out.close();
		cWriter.close();
		return cWriter.toString();
	}

	public SimpleEquivalentMatrix toEquivalentMatrix(boolean isLogingPath) {
		return new SimpleEquivalentMatrix(this, isLogingPath);
	}

	/*
	 * 该类暴露给该包中的SimpleEquivalentMatrix 树叉，也就是图中的边。
	 * Branch在SimpleEquivalentMatrix中会经常被isDirectedEdge(i,j)查找
	 */
	class Branch {
		Branch(Integer x, Integer y) {
			this.x = x;
			this.y = y;
		}

		Integer x;

		Integer y;

		@Override
		public boolean equals(Object obj) {
			Branch branch = (Branch) obj;
			return (branch.x == x && branch.y == y) || (branch.x == y && branch.y == x);
		}

		@Override
		public int hashCode() {
			/*
			 * if(x>y) return new String("c"+x+"row"+y).hashCode(); return new
			 * String("c"+y+"row"+x).hashCode();
			 */
			// 下三角计算,hashcode选成元素 按行优先的序号
			if (x > y)
				return x * ((int) matrix.getBound()) + y;
			return y * ((int) matrix.getBound()) + x;
		}

	}

}