search.java

检索无向图中的最短路径

package lab2;

/*
 * Created on 2007-11-4
 */
import java.io.*;
import java.util.*;

/**
 * @author Songyingying
 */
public class Search {
	static BufferedReader br;
	static Vector Vctr;
	static Map m = new HashMap();
//	static LinkedList linklist=new LinkedList();
	//static LinkedList read=new LinkedList();//已经读过的node.name

	//static boolean nopass=false;
	//static String newlayer="zorah";

	private static void read(String readFile) {
		try //源文件
		{
			br =new BufferedReader(
					new InputStreamReader(new FileInputStream(readFile)));
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	private static void readLines() //读取源文件中的每一行到Map中
	{
		try {
			String s;
			while ((s = br.readLine()) != null) {
				if (s.charAt(0) != '#') {
					String[] tokens = null;
					tokens = s.split(":");
					if (tokens.length < 2) {
						m.put(tokens[0], null);
					} else {
						StringTokenizer stoke = new StringTokenizer(tokens[1]);
						ArrayList a = new ArrayList();
						while (stoke.hasMoreElements()) {
							String st = stoke.nextToken();
							a.add(st);
						}
						m.put(tokens[0], a);
					}
				}
			}
			br.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	private static boolean hasEdge(Node a, Node b) {
		ArrayList c = (ArrayList) (m.get(a.getName()));
		return c.contains(b.getName());
	}

	private static List getSuccessors(Node a) {
		ArrayList b = new ArrayList();
		ArrayList c = (ArrayList) (m.get(a.getName()));
		if(c==null){
			return b;
		}else{
			Iterator iterater = c.iterator();
			while (iterater.hasNext()) {
				String ss = (String) iterater.next();
				//Node n = new Node(ss);
				b.add(ss);
			}
		}
		return b;
	}
	private static List getPredecessors(Node a) {
		ArrayList b = new ArrayList();
		Iterator iterater = m.keySet().iterator();
		while (iterater.hasNext()) {
			Object key;
			ArrayList value;
			key = iterater.next();
			value = (ArrayList) (m.get(key));
			if (value == null) {
			} else if (value.contains(a.getName())) {
				//Node n = new Node((String) key);
				b.add(key);
			}
		}
		return b;
	}
	private static void printList(List z) {
		Iterator iterater = z.iterator();
		while (iterater.hasNext()) {
			String ss = (String) iterater.next();
			System.out.print(ss + " ");
		}
	}



	public static void main(String args[]) {
		String source;
		source = "E:\\wikipedia.IDX";
		read(source);
		readLines();




		boolean o = false;

		try //源文件
		{
			BufferedReader brdr =
				new BufferedReader(new InputStreamReader(System.in));
			String lineStr = "";

			System.out.println("Enter your cmd:");

			while ((lineStr = brdr.readLine()) != null) {
				String[] tokens = lineStr.split(" ");
				Node p = new Node(tokens[1]);
				List z = null;
				if (tokens[0].equals("hasEdge")) {
					Node q = new Node(tokens[2]);
					o = hasEdge(p, q);
					if (o) {
						System.out.println("Yes");
					} else {
						System.out.println("No");
					}
				} else if (tokens[0].equals("getSuccessors")) {
					z = getSuccessors(p);
					printList(z);
					System.out.println("");
				} else if (tokens[0].equals("getPredecessors")) {
					z = getPredecessors(p);
					printList(z);
					System.out.println("");
				} else if (tokens[0].equals("printShortestPath")) {/*
					Node q = new Node(tokens[2]);
					if(p.getName().equals(q.getName())){
						System.out.println("src is the same to dest!");
					}else{
						List l=getShortestPath(p,q);
						System.out.println(p.getName()+" to "+q.getName()+"("+stack.size()+"paths there)");
						System.out.print("[");
						System.out.print(stack.pop());
						while(!stack.empty()){
							System.out.print(","+stack.pop());
						}
						System.out.print("]");
					}*/
				} 
				else
					System.out.println("invalid input!");
				System.out.println("Enter your cmd:");

			}
			br.close();
		} catch (Exception e) {
			e.printStackTrace();
		}

	}
}