simpleequivalentmatrix.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.HashSet;
import java.util.LinkedList;

import com.clustering.core.SimpleGeneratingTree.Branch;
import com.clustering.ds.matrix.SimpleSymetricalMatrix;

/**
 * 聚类挖掘过程中将使用的等价矩阵.
 * <p>
 * 距离矩阵、模糊相似矩阵SimpleFuzzyMatrix、图SimpleFuzzyGraph，这些类都是创建等价矩阵SimpleEquivalentMatrix
 * 的中间计算变量，聚类挖掘时只会使用SimpleEquivalentMatrix，而不会使用到SimpleFuzzyMatrix、SimpleFuzzyGraph
 * 等， 因此没保存这些中间结果，但能够查看这些中间变量,生成树SimpleGeneratingTree虽然也是中间结果，但是在生成等价矩阵
 * 的时候会需要这个中间结果作为辅助变量，所以为生成树创建了存储空间，这个存储空间是很大
 * <p>
 * 等价矩阵的存储空间就是SimpleFuzzyMatrix的存储空间
 * 
 * @author Avon
 * @version 0.9
 * @since 0.9
 */
public class SimpleEquivalentMatrix extends SimpleSymetricalMatrix {
	private SimpleGeneratingTree tree;

	private boolean isLogingPath;

	// 该属性为了在不同的方法间共享参数而引入，init后设置该对象为null
	private HashSet<Branch> set;

	// 避免总是创建branch变量，init后设置该对象为null
	private Branch branchtmp;

	/*
	 * 路径矩阵，由生成树到图的路径矩阵.按照下三角矩阵来保存即path中元素都是从x--...--y，其中x>y
	 * 这里使用上三角会简单一些，但是要求输出下三角 
	 */ 
	private String[] pathes;

	@SuppressWarnings("deprecation")
	public SimpleEquivalentMatrix(SimpleGeneratingTree tree, boolean isLogingPath) {
		super();
		this.tree = tree;
		values = tree.values;
		this.isLogingPath = isLogingPath;
		bound = tree.powers.length + 1;
		branchtmp = tree.new Branch(0, 0);
		init();
	}

	/*
	 * 创建等价矩阵
	 * 
	 * 由于是根据无向生成树求最短路径问题，所以只要计算出了两点之间的一个距离，那么这个距离就是最短距离，而无需象dij那样 重复比较，选择最短路径
	 * 
	 * 这里i-k应该是i--k，输出成--好看，但写--繁
	 */
	private void init() {
		if (isLogingPath) {
			pathes = new String[tree.values.length];
		}

		// 将生成树中的所有边保存到一个HashSet中，通过这个HashSet来判断isDirectedEdge，并初始化路径矩阵
		set = new HashSet<Branch>();
		for (int i = 0; i < tree.branches.length; i++) {
			// 虽然tree.branches挺别扭，但是没有友元，而且强制要分步，只能把内部细节暴露一部分了
			Branch branch = tree.branches[i];
			set.add(branch);
			// 设置从x到y的路径,按照下三角矩阵来保存
			if (isLogingPath) {
				if (branch.x > branch.y)
					pathes[getIndex(branch.x, branch.y)] = branch.x + "--" + branch.y;
				else
					pathes[getIndex(branch.x, branch.y)] = branch.y + "--" + branch.x;
			}
		}
		if (isLogingPath) {
			for (int i = 0; i < bound; i++) {
				pathes[getIndex(i, i)] = null;
			}
		}

		/* dij算法确实能此处情况，认为由生成树找最短路径是一种特殊情况，可以简化dij算法，从而提高效率.详细参考resources */
		// queue/Q用来保存未遍历过的节点
		LinkedList<Node> queue = new LinkedList<Node>();
		// 对于顶点i来说，已经被遍历过的节点
		boolean[] traversed = new boolean[(int) bound];
		// 使用广度优先搜索，遍历生成树n-1次[n=bound]，从添加边的角度考虑，只需计算 [0+1+2+n-1 - (n-1)]
		// 次距离，计算次数、判断次数都会比dij少
		for (int i = 0; i < bound - 1; i++) {
			// 置traversed[0...bound-1] 为 false; traversed[i] = true
			for (int z = 0; z < traversed.length; z++)
				traversed[z] = false;
			traversed[i] = true;

			// init queue
			// 用与i直接相连的顶点初始化Q
			for (int k = 0; k < bound; k++) {
				if (isDirectedEdge(k, i))
					queue.add(new Node(k, i));
				// 由于生成树中不会有环，所以可以在后面设置traversed[k] = true;
				// 也就是说，从i出发遍历图的过程中，在expand k之前，不会通过其他节点遍历到k，所谓的expand就是
				// expand函数，意思是从从i-...-k路径出发，遍历生成树
			}

			/*
			 * if(q is empty) 树有问题
			 */
			if (queue.isEmpty()) {
				throw new RuntimeException("Generating Tree's node ["+i+"] is invalid, for there are no edge connected to it. SimpleFuzzyMatrix initialization failed.");
			}
			while (!queue.isEmpty()) {
				// 出队
				Node nodek = queue.remove();
				// 标志nodek被遍历过，一会就expand nodek
				traversed[nodek.k] = true;

				/*
				 * nodek.k<i表示(i,k)之间的最短距离已经计算过了 nodek.j == i表示(i,k)之间是直接相连
				 * 这两种情况都不需要计算最短距离都不需要计算最短距离，前者距离已经计算过了，后者在初始化过程中完成了距离计算和路径设置
				 */
				if (nodek.k < i || nodek.j == i) {
					// 不用计算 i,j之间的距离，也不用保存路径，已经计算 保存过了

					// 从j到k，也就是要计算(i,l)的距离，路径是i--j--k--l
					// 也就是按照i-j-k路径扩张图的遍历
					expand(nodek.k, queue, traversed);
					continue;
				}

				/*
				 * i--k未遍历过，即i<k 计算(i,k)的最短距离，路径是i-...j-k，其中(i,j)之间的距离已知
				 */
				// i-j的距离已知
				double distancei_j = ((Double) values[getIndex(i, nodek.j)]);
				// j-k是直接相连的，参考expand函数
				double distancei_k = distancei_j + ((Double) values[getIndex(nodek.j, nodek.k)]).doubleValue();
				values[getIndex(i, nodek.k)] = new Double(distancei_k);

				/*
				 * 保存i-k之间的路径,i一定 小于 nodek.k，因为traversed[i] = true; i,j之间的大小关系未知
				 */
				if (isLogingPath) {
					// 因为i<k，所以pathi_k一定是k-j...-i，但由于i,j之间的大小关系未知，所以pathi_j可能是
					// i-...-j，也可能是j-...-i
					String pathi_k = null;
					String pathi_j = pathes[getIndex(i, nodek.j)];
					// 按照下三角来保存路径
					// startWith依赖与路径的存储格式
					if (i > nodek.j) {
						// pathi_j是 i-...-j，因为一定是k-j-...-i，所以要把i-...-j逆序
						String[] ss = pathi_j.split("--");
						StringBuffer i_j = new StringBuffer();
						for(int z=ss.length-1;z>-1;) {
							i_j.append(ss[z]);
							if(--z>-1)
								i_j.append("--");
						}
						// 创建k-j-...-i的格式
						pathi_k = nodek.k+ "--"+i_j.toString();
					} else {
						// pathi_j是 j-...-i
						pathi_k = nodek.k + "--" + pathi_j;
					}
					pathes[getIndex(i, nodek.k)] = pathi_k;
				}
				expand(nodek.k, queue, traversed);
			} // while
		} // for
		/* 计算法发结束 */

		// 等价矩阵无需保存以下两个值
		set = null;
		branchtmp = null;
	}

	/*
	 * 从i-..-j遍历生成树，expand的意思是从i-...-j出发添加遍历路径 将与j直接相连的且未遍历过的节点都添加到queue中，等待遍历
	 * expand名字的意思是扩大q中的元素，也就是向q中添加未遍历过的节点
	 */
	private void expand(int j, LinkedList<Node> queue, boolean[] traversed) {
		for (int k = 0; k < bound; k++) {
			// 按照生成树遍历
			if (!traversed[k] && isDirectedEdge(j, k)) {
				queue.add(new Node(j, k));
				// 无需置traversed[k]为true，因为还未expand(k)
			}
		}
	}

	private boolean isDirectedEdge(int i, int j) {
		branchtmp.x = i;
		branchtmp.y = j;
		return set.contains(branchtmp);
	}

	/*
	 * 轻装的getIndex
	 */
	protected int getIndex(int r, int c) {
		if (r > c) {
			return r * (r + 1) / 2 + c;
		}
		return c * (c + 1) / 2 + r;
	}

	public SimpleGeneratingTree getTree() {
		return tree;
	}

	public void setTree(SimpleGeneratingTree tree) {
		if (null == this.tree) {
			this.tree = tree;
			values = tree.values;
			init();
			return;
		}
		boolean isEquals = false;
		if (this.tree.values.length == tree.values.length) {
			isEquals = true;
			for (int i = 0; i < tree.values.length && isEquals; i++) {
				if (((Double) tree.values[i]).doubleValue() == ((Double) this.tree.values[i]).doubleValue()) {
					isEquals = false;
				}
			}
		}
		this.tree = tree;
		values = tree.values;
		init();
	}

	@Override
	public void setBound(long bound) {
		throw new UnsupportedOperationException("SimpleEquivalentMatrix for mining is allowed to modified.");
	}

	@Override
	public void setElement(long row, long col, Object value) {
		throw new UnsupportedOperationException("SimpleEquivalentMatrix for mining is allowed to modified.");
	}

	@Override
	public String toString() {
		CharArrayWriter cWriter = new CharArrayWriter();
		PrintWriter out = new PrintWriter(cWriter);
		out.print("The equivalent matrix is a ");
		out.print(bound);
		out.print('*');
		out.print(bound);
		out.print(" matrix which is Symetrical Matrix and ");
		if (isLogingPath) {
			out.print("log ");
		} else {
			out.print("does not log");
		}
		out.println("the path. If u do not wanna to log path, please set isLogPath in constructor " +
				"or SimpleGeneratingTree#toEquivalentMatrix(boolean) to false, this will accelerate " +
				"the program. Here we simply show lower triangle matrix with row in priority and omit " +
				"diagonal elements.");
		for (int j = 0; j < bound; j++) {
			for (int i = j + 1; i < bound; i++) {
				out.printf("[%d, %d]:\t\t%.3f", i, j, ((Double) values[i * (i + 1) / 2 + j]).doubleValue());
				if (isLogingPath) {
					out.print("\tpath: ");
					// 输出下三角阵中的存储结构
					out.printf(pathes[i * (i + 1) / 2 + j]);
				}
				out.println();
			}
			out.println();
		}

		out.close();
		cWriter.close();
		return cWriter.toString();
	}

	/*
	 * 返回从i到j的路径
	 */
	@SuppressWarnings("unused")
	public String getFormattedPath(int i, int j) {
		// pathes是按照下三角矩阵存储的路径信息
		String path = pathes[getIndex(i, j)];
		if (i > j)
			return path;
		char[] ori = path.toCharArray();
		char[] des = new char[ori.length];
		for (int z = 0; z < ori.length; z++) {
			des[z] = ori[ori.length - z-1];
		}
		return new String(des);

	}

	/*
	 * 这个类与Branch没有太大的区别，但这里是使用j,k来表示i-j-k路径 如果要去掉这个类，可以规定branch的x为j，branch的y为k
	 */
	private class Node {
		// i经过j到k，如果j=-1，那么表示i,j直接相连
		// k是未遍历的节点，j是i到node1所经过的节点，说明正在遍历j，通过j找未遍历的节点
		// 注意这里要求j与k直接相连
		int j;

		int k;

		Node(int j, int k) {
			this.j = j;
			this.k = k;
		}
	}
}