search.java

检索无向图中的最短路径

package lab;
/*
 * Created on 2007-11-14
 */
import java.io.*;
import java.util.*;

/**
 * @author Songyingying
 */
public class Search {

	private static Hashtable h;
	private static boolean goal = false;//find the shortest path
	private static boolean completed = false;
	private static int currentLimit=3;

	private static List getShortestPath(Node src, Node dest){
		LinkedList paths = new LinkedList();
		if(src != dest){
			LinkedList stack = new LinkedList();
			LinkedList rlist = new LinkedList();
			src.reserve();
			src.setLayer(1);
			stack.addLast(src);
			rlist.addLast(src);
			findPaths(stack,src,dest,rlist);
			completePath(paths,dest);
			recover(rlist);
		}
		else{
			paths = new LinkedList();
			paths.add(src.getName());
		}
		return paths;
	}

	private static void recover(LinkedList rlist){//set every node back to default
		goal=false;
		completed = false;
		currentLimit=3;
		Node n;
		int len = rlist.size();
		for(int i=0;i<len;i++){
			n = (Node)rlist.removeFirst();
			n.setLayer(-1);
			n.clearPaths();
			n.clearReserve();
		}
	}

	private static void completePath(LinkedList paths,Node n){//把dest里面存的path拿出来，将dest加到最后面
		LinkedList list = n.getPaths();
		int len = list.size();
		String s = "";
		for(int i=0;i<len;i++){
			s = list.removeFirst() + "," + n.getName();
			paths.addLast(s);
		}
	}
//	private static void printList(LinkedList list){
//		int len = list.size();
//		//System.out.println(len);
//		String s="print reserve : ";
//		for(int i=0;i<len;i++){
//			s+= (String)list.get(i)+" ";
//
//		}System.out.println(s);
//	}
//	private static void printNodeList(LinkedList list){
//		int len = list.size();
//		//System.out.println(len);
//		String s="print stack : ";
//		for(int i=0;i<len;i++){
//			s+= ((Node)list.get(i)).getName()+" ";
//
//		}System.out.println(s);
//	}
	private static void findPaths(LinkedList stack,Node src, Node dest,LinkedList rlist){
		while((!completed)|(currentLimit==26)){
			if(stack.size()==0){
				if(goal){
					completed=true;
					System.out.println("complete");
				}else{currentLimit++;/**重新搜索*/
				recover(rlist);
				src.reserve();
				src.setLayer(1);
				stack.addLast(src);
				rlist.addLast(src);
				System.out.println("limit++");
				break;
				}
			}else{
				Node n = (Node)stack.getLast();
				String name = n.getName();
				if(name.equals(dest.getName())){//达到终点
					goal = true;
					//stack.removeLast();

				//	printNodeList(stack);
					Node z= (Node)stack.removeLast();
					/***/	System.out.println(" goal stack remove "+z.getName()+" layer="+z.getLayer()+" "+((Node)stack.getLast()).getName());
				}else{
					if(n.getLayer()<currentLimit){
						//System.out.print(n.getName()+ " ");
						if(n.getReserve().size()!=0){
							//	if(n.getName().equals("b")){
							//	printList(n.getReserve());
							//}
							Node reserve;
							reserve=(Node)h.get(n.popReserve());
							String paths = "";
							LinkedList plist;
							int level = reserve.getLayer();
							int currentlayer=n.getLayer();
							if(level==-1){//没读过的新节点
								reserve.setLayer(currentlayer+1);
								///***/	System.out.println(reserve.getName()+" "+reserve.getLayer()+" new node");
								reserve.reserve();
								plist = n.getPaths();
								int size = plist.size();
								if(size > 0){
									for(int j=0;j<size;j++){
										paths = plist.get(j)+","+n.getName();
										reserve.addPaths(paths);//将从src到现在的path存到节点里面
									}
								}else{reserve.addPaths(n.getName());}//当n是src的时候，n的path长度是0
								rlist.addLast(reserve);
							}else if(level == currentlayer+1){//已经读过了
							//	/***/	System.out.println(reserve.getName()+" "+reserve.getLayer()+"currentlayer+1");
								plist = n.getPaths();
								int size = plist.size();
								for(int j=0;j<size;j++){
									paths = plist.get(j)+","+n.getName();
									reserve.addPaths(paths);
								}
							}else if(level < currentlayer+1 ){
								System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~oh, I didn't care that.");
							}
							stack.addLast(reserve);
						//	System.out.println("stack add "+reserve.getName());
							if(((String)reserve.getName()).equals(dest.getName())){//达到终点
								goal = true;
								System.out.println(" goal ");
							}
							if(reserve.getLayer()==currentLimit){
								stack.removeLast();
								//Node z= (Node)stack.removeLast();
						//		/***/	System.out.println("layer=Limit stack remove "+z.getName()+" "+z.getLayer()+" stack.last="+((Node)stack.getLast()).getName());
							}
						}else{
							stack.removeLast();
							//Node z= (Node)stack.removeLast();
					//		/***/	System.out.println(z.getName()+" "+z.getLayer()+" stack remove reserve.size=0 ");
						}
					}
				}
			}
		}
	}
	public static void main(String[] args) throws IOException{
		File f = new File("e:\\wikipedia.IDX");
		BufferedReader in = new BufferedReader(new FileReader(f));
		String temp = in.readLine(); 
		String name = "";
		h = new Hashtable ();
		int i;
		int counter = Integer.parseInt(temp.substring(1,temp.length()));
		for(;counter > 0;counter--){//读文件
			temp = in.readLine();
			String[] tt = temp.split(" ");
			name = tt[0].substring(0,tt[0].length()-1);
			Node n = (Node)(h.get(name));
			if(n == null){
				n = new Node(name);
				h.put(name,n);
			}
			for(i=1;i<tt.length;i++){
				n.addNext(tt[i]);
				Node nd = (Node)h.get(tt[i]);
				if(nd == null){
					nd = new Node(tt[i]);
					h.put(tt[i],nd);
				}
				nd.addPrev(name);
			}
		}
		in.close();

		Node n1 = (Node)h.get("china");
		Node n2 = (Node)h.get("irelands");

		LinkedList l = (LinkedList)getShortestPath(n1,n2);
		for(int p=0;p<l.size();p++){
			System.out.println(">["+l.get(p)+"]");	
		}
//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		String command;//命令行
//		while(true){
//		System.out.print("> ");
//		command = br.readLine();
//		String[] s = command.split(" ");
//		if(s.length >= 3 && !s[0].equals("hasEdge") && !s[0].equals("printShortestPath")){
//		System.out.println("No such commands.");
//		}
//		else if(s[0].equals("hasEdge")){
//		Node n1 = (Node)h.get(s[1]);
//		Node n2 = (Node)h.get(s[2]);
//		System.out.println(Node.hasEdge(n1,n2));
//		}
//		else if(s[0].equals("printShortestPath")){
//		if(s[1].equals(s[2])){
//		System.out.println("src is the same to dest!");
//		}
//		else {
//		Node n1 = (Node)h.get(s[1]);
//		Node n2 = (Node)h.get(s[2]);
//		LinkedList l = (LinkedList)getShortestPath(n1,n2);
//		int len = l.size();
//		System.out.println(s[1]+" to "+s[2]+" ("+len+" paths there)");
//		if(len == 0){
//		System.out.println("There's none path from "+s[1]+" to "+s[2]+"!");
//		}
//		else {
//		for(int p=0;p<len;p++){
//		System.out.println(">["+l.get(p)+"]");
//		}
//		}
//		}
//		}
//		else if(s[0].equals("getSuccessors")){
//		Node n = (Node)h.get(s[1]);
//		n.printNext();
//		}
//		else if(s[0].equals("getPredecessors")){
//		Node n = (Node)h.get(s[1]);
//		n.printPrev();
//		}
//		else if(s[0].equals("quit")){
//		System.exit(0);
//		}
//		else {
//		System.out.println("No such commands.");
//		}
//		}
	}
}