nshortpath.java

基于中科院的ICTCLAS实现中文分词系统 开发工具是JAVA.经测试,效果很好

package com.gftech.ictclas4j.segment;

import java.util.ArrayList;

import com.gftech.ictclas4j.bean.Queue;
import com.gftech.ictclas4j.bean.QueueNode;
import com.gftech.ictclas4j.bean.SegGraph;
import com.gftech.ictclas4j.utility.Utility;

/**
 * N-最短路径
 * 
 * @author sinboy
 * 
 */
public class NShortPath {
	// 最短路径的数目
	private int pathCount;

	//
	private ArrayList<SegGraph> biSgs;

	// 每条路径对应的权值
	private double[] pathWeight;

	private QueueNode[] parent;

	private int vertex;

	public NShortPath(ArrayList<SegGraph> biSgs, int pathCount) {
		this.biSgs = biSgs;
		this.pathCount = pathCount;

		if (biSgs != null && biSgs.size() > 0 && pathCount > 0) {
			SegGraph sg = biSgs.get(biSgs.size() - 1);
			vertex = sg.getCol() + 1;
			if (sg.getRow() + 1 > vertex)
				vertex = sg.getRow() + 1;

			parent = new QueueNode[vertex - 1];
			pathWeight = new double[vertex - 1];

			for (int i = 0; i < vertex - 1; i++) {
				parent[i] = new QueueNode();
			}
		}
	}

	public ArrayList<SegGraph> getBiSgs() {
		return biSgs;
	}

	public void setBiSgs(ArrayList<SegGraph> biSgs) {
		this.biSgs = biSgs;
	}

	public int getPathCount() {
		return pathCount;
	}

	public void setPathCount(int pathCount) {
		this.pathCount = pathCount;
	}

	/**
	 * 得到N-最短路径
	 * 
	 * @param isGetBest
	 *            只得到最优的那条路径
	 * @return
	 */
	public int[] getNShortPath(boolean isGetBest) {

		shortPath();
		int[] first = getPaths();
		return Utility.removeInvalid(first);

	}

	/**
	 * 按列遍历图表，并把每一列中权重最小的取出来。
	 * 
	 */
	private void shortPath() {
		int preNode = -1;
		double weight = 0;

		if (biSgs != null) {
			// 图表的列值是从1开始,所以忽略掉第0列
			for (int cur = 1; cur < vertex; cur++) {
				// 得到同一列的所有元素
				ArrayList<SegGraph> colSgs = Utility.getColElements(biSgs, cur);
				if (colSgs == null || colSgs.size() == 0)
					return;

				Queue queWork = new Queue();
				for (SegGraph seg : colSgs) {
					preNode = seg.getRow();
					weight = seg.getValue();
					if (preNode == 0)
						queWork.push(new QueueNode(preNode, 0, weight));
					else if (pathWeight[preNode - 1] != Utility.INFINITE_VALUE)
						queWork.push(new QueueNode(preNode, 0, weight + pathWeight[preNode - 1]));
				}

				QueueNode minNode = queWork.pop();
				pathWeight[cur - 1] = minNode.getWeight();
				minNode.setWeight(0);
				parent[cur - 1] = minNode;
				System.out.println("pathWeight[" + (cur - 1) + "]:" + pathWeight[cur - 1]);
				System.out.println("parent[" + (cur - 1) + "]:" + parent[cur - 1]);
			}
		}
	}

	private int[] getPaths() {
		int[] result = new int[vertex];

		Queue queResult = null;
		int curNode, curIndex = 0;
		int resultIndex = 0;

		if (vertex > 0) {
			result[resultIndex] = -1;
			queResult = new Queue();
			queResult.push(new QueueNode(vertex - 1, 0, 0));
			curNode = vertex - 1;
			// curIndex = i;

			while (!queResult.isEmpty()) {
				while (curNode > 0) {
					// Get its parent and store them in nParentNode,nParentIndex
					QueueNode qn = parent[curNode - 1];
					if (qn != null) {
						curNode = qn.getParent();
						curIndex = qn.getIndex();
					}
					if (curNode > 0)
						queResult.push(new QueueNode(curNode, curIndex, 0));
				}

				if (curNode == 0) { // Get a path and output
					result[resultIndex++] = curNode;

					QueueNode qn = null;
					while ((qn = queResult.pop()) != null && resultIndex < result.length)
						result[resultIndex++] = qn.getParent();

				}

			}
		}
		return result;
	}

}