simplefuzzygraph.java

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

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

import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.NoSuchElementException;

import com.clustering.ds.graph.Arc;
import com.clustering.ds.graph.Graph;
import com.clustering.ds.graph.GraphCategory;
import com.clustering.ds.graph.Power;
import com.clustering.ds.graph.UndirectedArc;
import com.clustering.ds.graph.Vertex;
import com.clustering.ds.tree.Tree;

/**
 * 这只是一个概念，根本没有必要创建这个类.原因是这个类的对象不会在挖掘中使用，这个类的对象只是计算EquivalentMatrix的一个中间步骤。
 * 创建这个图，除了方便使用图的观点观察SimpleFuzzyMatrix和增大开销、工作量外，没有别的用途。
 * <p>
 * 通过这个图创建的生成树也是这样，只是为了方便以树的观点来观察计算EquivalentMatrix的一个中间步骤的结果。
 * 这里机械的按照5.3.3.3中的说明去实现，只是为了满足观察一个中间步骤的结果。
 * <p>
 * 最初SimpleFuzzyGraph,
 * SimpleGeneratingTree等都是作为SimpleFuzzyMatrix的内部类实现的，但是会使SimpleFuzzyMatrix过于
 * 复杂，只能把这些类作为单独的类抽出来。
 * <p>
 * SimpleFuzzyMatrix$GraphImpl的注释： Graph只是为了满足5.3.3.3
 * 求模糊等价矩阵时所涉及的图的概念，为了实现这个概念必然要创建大量的对象。 如果要降低内存的使用，那么可以直接使用相似矩阵构造等
 * 价矩阵，而不加入图的概念。这里的图只是对相似矩阵的在概念层次的包装，并没有为图新创建一片存储区，图的存储结构使用的是SimpleFuzzyMatrix。
 * 没有为图建立存储区是因为图中所涉及的对象都可以使用SimpleFuzzyMatrix来获得，建立图的存储区也只是数据的冗余。
 * 这个图只是SimpleFuzzyMatrix的一种视图，因此这里没有为图建立分配存储区，当需要图中的顶点、弧等时，也只是简单的
 * 对SimpleFuzzyMatrix中的数据使用图的概念类包装，因此该类的方法几乎都是deprecated，该类中最有意义的方法就是 Tree[]
 * toForest()
 * <p>
 * 总之，SimpleGeneratingTree和SimpleFuzzyGraph都使对SimpleFuzzyMatrix的包装，这两个类只是SimpleFuzzyMatrix
 * 创建EquivalentMatrix中间结果的两个视图，没有为这个类分配存储空间
 * 
 * @author Avon
 * @version 0.9
 * @since 0.9
 */
public class SimpleFuzzyGraph implements Graph {
	private SimpleFuzzyMatrix matrix;


	// 这个hash map用来缓存顶点，这样就不会造成冗余的顶点了，用池会比HashMap好吗？
	private HashMap<Index, Vertex> vertexes;

	// 方便检索vertexes
	Index index;

	public SimpleFuzzyGraph(SimpleFuzzyMatrix matrix) {
		this.matrix = matrix;
		vertexes = new HashMap<Index, Vertex>();
		isUpperTriangleTree = false;
	}

	private boolean isUpperTriangleTree;

	/**
	 * 由于数据挖掘不要求修改数据，所以这里也不应该修改模糊等价矩阵对应的图.
	 * <p>
	 */
	@Deprecated
	public Arc addArc(Vertex v1, Vertex v2) {
		throw new UnsupportedOperationException("Graph for mining is allowed to modified.");
	}

	/**
	 * 由于数据挖掘不要求修改数据，所以这里也不应该修改模糊等价矩阵对应的图.
	 * <p>
	 */
	@Deprecated
	public Vertex addVertex() {
		throw new UnsupportedOperationException("Graph for mining is allowed to modified.");
	}

	/**
	 * 由于数据挖掘不要求修改数据，所以这里也不应该修改模糊等价矩阵对应的图.
	 * <p>
	 */
	@Deprecated
	public Arc removeArc(Vertex v1, Vertex v2) {
		throw new UnsupportedOperationException("Graph for mining is allowed to modified.");
	}

	/**
	 * 由于数据挖掘不要求修改数据，所以这里也不应该修改模糊等价矩阵对应的图.
	 * <p>
	 */
	@Deprecated
	public Vertex removeVertex(long id) {
		throw new UnsupportedOperationException("Graph for mining is allowed to modified.");
	}

	/**
	 * 由于数据挖掘不要求修改数据，所以这里也不应该修改模糊等价矩阵对应的图.
	 * <p>
	 */
	@Deprecated
	public Vertex removeVertex(Vertex vertex) {
		throw new UnsupportedOperationException("Graph for mining is allowed to modified.");
	}

	/**
	 * 完全可以不使用Arc而直接使用{@link SimpleFuzzyMatrix.getElement(row, col)}来代替
	 */
	@Deprecated
	public UndirectedArc getArc(Vertex v1, Vertex v2) {
		return new UndirectedArcImpl(v1.getID(), v2.getID());
	}

	/**
	 * 完全可以不使用Arc而直接使用{@link SimpleFuzzyMatrix.getElement(row, col)}来代替
	 */
	@Deprecated
	public UndirectedArc getArc(long v1, long v2) {
		return new UndirectedArcImpl(v1, v2);
	}

	public long getArcNumber() {
		return matrix.values().length;
	}

	public GraphCategory getGraphCategory() {
		return GraphCategory.UndirectedNet;
	}

	/**
	 * 获取图中顶点的目的就是判断当前顶点与哪些顶点连通.
	 * <p>
	 * 被@{link SimpleFuzzyMatrix的getElement(row, col)}取代
	 */
	@Deprecated
	public Vertex getVertex(long id) {
		index.id = (int) id;
		Vertex v = vertexes.get(index);
		if (null == v) {
			v = new VertexImpl(id);
			vertexes.put(new Index((int) id), v);
			return v;
		} else {
			return v;
		}
	}

	/**
	 * 被{@link  getVertex(long)}所取代
	 */
	@Deprecated
	public Iterator getVertexIterator() {
		final long recordNum = matrix.getSource().getSourceInfo().getRecordNum();
		return new Iterator() {
			int cur = 0;

			public boolean hasNext() {
				return cur < recordNum;
			}

			public Object next() {
				if (cur > recordNum)
					throw new NoSuchElementException("iteration has no more elements.");
				return getVertex(cur++);
			}

			public void remove() {
				throw new UnsupportedOperationException("Graph for mining is allowed to modified.");
			}
		};
	}

	/**
	 * 被{@link SimpleFuzzyMatrix.getArc(long, long) }
	 */
	@Deprecated
	public Iterator getArcIterator() {
		final int bound = (int) matrix.getSource().getSourceInfo().getColumnNum();
		return new Iterator() {
			int col = 0;

			int row = 0;

			public boolean hasNext() {
				return row < bound;
			}

			/*
			 * 只返回一半的弧
			 */
			public Object next() {
				if (row == bound) {
					throw new NoSuchElementException("iteration has no more elements.");
				}
				UndirectedArcImpl arc = new UndirectedArcImpl(row, col++);
				if (col == bound) {
					col = 0;
					row++;
					// 跳过一半矩阵
					while (row > col) {
						col++;
					}
				}
				return arc;
			}

			public void remove() {
				throw new UnsupportedOperationException("Graph for mining is allowed to modified.");
			}

		};
	}

	/**
	 * 被{@link SimpleFuzzyMatrix.getBound()}取代
	 */
	@Deprecated
	public long getVertexNumber() {
		return matrix.getSource().getSourceInfo().getRecordNum();
	}

	/**
	 * 没有必要使用Arc对象，这个对象只是为了满足概念上的要求
	 */
	@Deprecated
	private class UndirectedArcImpl implements UndirectedArc {
		Power power;

		Vertex v1;

		Vertex v2;

		UndirectedArcImpl(final Vertex v1, final Vertex v2) {
			this.v1 = v1;
			this.v2 = v2;
			power = new PowerImpl();
		}

		UndirectedArcImpl(final long id1, final long id2) {
			/*
			 * GraphImpl没有为Vertex创建一个存储区，所以这个方法回造成Vertex的冗余
			 */
			v1 = getVertex(id1);
			v2 = getVertex(id2);
			power = new PowerImpl();
		}

		public Vertex[] getRelatedVertexes() {
			return new Vertex[] { v1, v2 };
		}

		public Power getPower() {
			return power;
		}

		@Deprecated
		private class PowerImpl implements Power, Comparator {
			Double weight;

			PowerImpl() {
				weight = new Double(((Double) matrix.getElement(v1.getID(), v2.getID())));
			}

			public Object getWeight() {
				return weight;
			}

			/*
			 * 为了将Power添加到SortedSet中，如果真的使用Power计算5.3.3.3中的相似序列
			 * 但这里不会使用Power排序的，创建大量的对象
			 */
			public int compare(Object o1, Object o2) {
				if (null == o1 || null == o2)
					throw new NullPointerException("Arguments is null.");
				if (!Power.class.isAssignableFrom(o1.getClass())) {
					throw new ClassCastException("Argument o1 is not a Power.");
				}
				if (!Power.class.isAssignableFrom(o2.getClass())) {
					throw new ClassCastException("Argument o2 is not a Power.");
				}
				if (!Double.class.isAssignableFrom(((Power) o1).getWeight().getClass()))
					throw new IllegalArgumentException("o1 is not suitable Power");
				if (!Double.class.isAssignableFrom(((Power) o2).getWeight().getClass()))
					throw new IllegalArgumentException("o2 is not suitable Power");
				double d1 = ((Double) ((Power) o1).getWeight()).doubleValue();
				double d2 = ((Double) ((Power) o2).getWeight()).doubleValue();
				return d1 > d2 ? 1 : (d1 == d2 ? 0 : -1);
			}

			@Override
			public boolean equals(Object obj) {
				if (null == obj) {
					return false;
				}
				if (!Power.class.isAssignableFrom(obj.getClass())) {
					return false;
				}
				if (!Double.class.isAssignableFrom(((Power) obj).getWeight().getClass()))
					return false;
				return weight == ((Double) ((Power) obj).getWeight()).doubleValue();
			}
		};
	}

	/**
	 * 没有必要使用Vertex对象，这个对象只是为了满足概念上的要求
	 */
	@Deprecated
	private class VertexImpl implements Vertex {
		private long id;

		VertexImpl(long id) {
			this.id = id;
		}

		public Arc getArc(long id) {
			return new UndirectedArcImpl(this, getVertex(id));
		}

		public Arc getArc(Vertex v) {
			return new UndirectedArcImpl(this, v);
		}

		public long getID() {
			return id;
		}

		@Override
		/*
		 * 节点的比较
		 */
		public boolean equals(Object obj) {
			if (null == obj)
				return false;
			if (!Vertex.class.isAssignableFrom(obj.getClass()))
				return false;
			return id == ((Vertex) obj).getID();
		}

		public Iterator getArcIterator() {
			final Vertex wrapper = this;
			return new Iterator() {
				long curCol = 0;

				public boolean hasNext() {
					if (curCol == matrix.getBound())
						return false;
					return true;
				}

				public Object next() {
					return new UndirectedArcImpl(wrapper, new VertexImpl(curCol++));
				}

				public void remove() {
					throw new UnsupportedOperationException("UndirectedArc for mining is allowed to modified.");
				}
			};
		}
	}

	class Index {
		int id;

		Index() {
		}

		Index(int id) {
			this.id = id;
		}

		@Override
		/*
		 * equals要简写
		 */
		public boolean equals(Object obj) {
			return id == ((Index) obj).id;
		}

		@Override
		public int hashCode() {
			return id;
		}

	}

	public boolean isUpperTriangleTree() {
		return isUpperTriangleTree;
	}

	public void setUpperTriangleTree(boolean upper) {
		isUpperTriangleTree = upper;
	}

	/*
	 * 基于模糊相似矩阵所成的无向网一定是完全的，所以这里不会有森林，只会有一棵树.
	 * 由于创建一个生成树不一定用图中n-1的弧，所以这里的排序只需找出前n-1弧，这里使用堆排序
	 */
	public Tree[] toForest() {
		return new Tree[] { new SimpleGeneratingTree(matrix,true)} ;
	}
}