graphalgorithm.java

本人历尽千辛万苦找的clustream中的jar包

package org.osu.ogsa.stream.info;

import java.util.*;
import org.osu.ogsa.stream.util.Visit;
import java.io.*;
import java.net.URL;
import java.net.URI;
import javax.swing.tree.*;
import org.apache.log4j.*;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
class GANode {
	int	x;
	int	y;
	int	delta_plus;	/* edge starts from this node */
	int	delta_minus;	/* edge terminates at this node */
	int	dist;		/* 1/distance from the start node */
	int	real_dist;	/* real distance from the start node */
	int	prev;		/* previous node of the shortest path */
	int	succ,pred;	/* node in Sbar with finite dist. */
	int	w;
	int	h;
	int	pw;
	int	dx;
	int	dy;
	boolean bVisited;
	DefaultMutableTreeNode treeNode;
	int 	[] table;
	String	strPlacement[];
	Vector 	vecStages;
	Visit	visitArray[];
	int 	numVisits;
	String	name;
}

class Edge {
	int	rndd_plus;	/* initial vertex of this edge */
	int	rndd_minus;	/* terminal vertex of this edge */
	int	delta_plus;	/* edge starts from rndd_plus */
	int	delta_minus;	/* edge terminates at rndd_minus */
	int	len;		/* length */
	int	fake_len;
	String	name;
}


public abstract class GraphAlgorithm{
	int	n,m;
	int	u,snode;	/* start node */
	int	pre_s_first, pre_s_last;
	boolean	isdigraph;
	int	iteration, step;
	GANode	v[] = new GANode[500];
	Edge	e[] = new Edge[500];
//	private static Category log = Category.getInstance(GraphAlgorithm.class.getName());
        static Log log = LogFactory.getLog(GraphAlgorithm.class.getName());
	protected static int START_LABEL = -2;
	protected static int INPROGRESS_LABEL = -3;
	protected static int COMPLETION_LABEL = -4;
	private static final int MAXINT = 1000000000;

	int findNode(String name) {
		for (int i=0; i<n; i++)
			if (v[i].name.equals(name))
				return i;
		log.debug("can't find " + name);
		return -1;
	}

	public int findEdge(String start_name, String end_name)
	{
		//find the edge
		int start = findNode(start_name);
		int end = findNode(end_name);
		if(start < 0 || end < 0)
			return -1;

		for(int i = 0; i < m; i ++)
			if(e[i].rndd_plus == start && 
					e[i].rndd_minus == end)
				return i;
		return -1;
	}

	public int getEdgeLength(String start_name, String end_name)
	{
		int i = findEdge(start_name, end_name);
		if(i < 0)
			return -1;
		else
			return e[i].len;
	}

	void merge(GraphAlgorithm ga, String strSource)
	{
		log.debug("merge" + ga);
		DefaultMutableTreeNode leaf = ga.getTreeNode(strSource);
		if(leaf == null)
		{
			log.debug("can't find "+strSource+"in" + ga);
			return;
		}

		GANode gaNode_Source, gaNode_Dest;
		DefaultMutableTreeNode curNode, lastNode = null;
		while(leaf != null)
		{
			gaNode_Source = (GANode)leaf.getUserObject();
			gaNode_Dest = v[findNode(gaNode_Source.name)];
			if(gaNode_Dest.treeNode == null)
			{
				curNode = new DefaultMutableTreeNode(gaNode_Dest);
				//init newTreeNode
				gaNode_Dest.treeNode = curNode;
			}
			else 
			{
				curNode = gaNode_Dest.treeNode;
			}

			if(lastNode != null)
			{
				curNode.add(lastNode);
				//copy the distance information to the last node
			        //from the source tree
				((GANode)lastNode.getUserObject()).real_dist = gaNode_Source.real_dist;
			}

			lastNode = curNode;
			leaf = (DefaultMutableTreeNode)leaf.getParent();
		}
	}





	void input_graph(InputStream is) throws IOException {
		int x,y,l;
		String	s;

		Reader r = new BufferedReader(new InputStreamReader(is));
		StreamTokenizer st = new StreamTokenizer(r);
		st.commentChar('#');
		st.nextToken();	n = (int)st.nval;
		st.nextToken();	m = (int)st.nval;
		st.nextToken();	s = st.sval;
		isdigraph = "digraph".equals(s);
		for (int i = 0; i<n; i++) {
			GANode node = new GANode();
			st.nextToken();	node.name = st.sval;
			st.nextToken();	node.x = (int)st.nval;
			st.nextToken();	node.y = (int)st.nval;
			v[i] = node;
		}
		for (int i = 0; i<m; i++) {
			Edge edge = new Edge();
			st.nextToken();	edge.name = st.sval;
			switch (st.nextToken()) {
			case StreamTokenizer.TT_NUMBER:
				edge.rndd_plus = (int)st.nval;
				break;
			case StreamTokenizer.TT_WORD:
				edge.rndd_plus = findNode(st.sval);
				break;
			default:
				break;
			}
			switch (st.nextToken()) {
			case StreamTokenizer.TT_NUMBER:
				edge.rndd_minus = (int)st.nval;
				break;
			case StreamTokenizer.TT_WORD:
				edge.rndd_minus = findNode(st.sval);
				break;
			default:
				break;
			}
			st.nextToken();	edge.fake_len = (int)((double)MAXINT/(double)st.nval);
			edge.len = (int)st.nval;
			e[i] = edge;
		}
		for (int i=0; i<n; i++) {
			v[i].succ = v[i].pred = START_LABEL;
			v[i].prev = -1;
			v[i].dist = -1;
			v[i].real_dist = -1;
			v[i].pw = 0;
		}
		iteration = step = 0;
	}

	void construct_adjlist() {
		int	i,k;

		for (i=0; i<n; i++)
			v[i].delta_plus = v[i].delta_minus = -1;
		for (i=0; i<m; i++)
			e[i].delta_plus = e[i].delta_minus = -1;
		for (i=0; i<m; i++) {
			k = e[i].rndd_plus;
			if (v[k].delta_plus == -1)
				v[k].delta_plus = i;
			else {
				k = v[k].delta_plus;
				while(e[k].delta_plus >= 0)
					k = e[k].delta_plus;
				e[k].delta_plus = i;
			}
			k = e[i].rndd_minus;
			if (v[k].delta_minus == -1)
				v[k].delta_minus = i;
			else {
				k = v[k].delta_minus;
				while(e[k].delta_minus >= 0)
					k = e[k].delta_minus;
				e[k].delta_minus = i;
			}
		}
	}

	void append_pre_s(int i) {
		v[i].succ = v[i].pred = -1;
		if (pre_s_first<0)
			pre_s_first = i;
		else
			v[pre_s_last].succ = i;
		v[i].pred = pre_s_last;
		pre_s_last = i;
	}

	void remove_pre_s(int i) {
		int	succ = v[i].succ;
		int	pred = v[i].pred;

		if (succ>=0)
			v[succ].pred = pred;
		else
			pre_s_last = pred;
		if (pred>=0)
			v[pred].succ = succ;
		else
			pre_s_first = succ;
	}

	void init_step1() {		/* initialize */
		u = snode;
		int j;
		for (int i=0; i<n; i++) {
			v[i].succ = v[i].pred = START_LABEL;
			v[i].prev = v[i].dist = v[i].real_dist = -1;
			v[i].treeNode = null;
			v[i].bVisited = false;
			v[i].vecStages = null;
			v[i].table = new int[50];
			v[i].visitArray = new Visit[50];
			v[i].numVisits = 0;
			v[i].strPlacement = new String[50];
			for(j = 0; j < 50; j ++)
				v[i].table[j] = 1;
		}
		v[u].succ = INPROGRESS_LABEL;
		v[u].dist = 0;
		v[u].real_dist = 0;
		pre_s_first = pre_s_last = -1;
	}


	abstract void updateDist();		/* replace labels */

	void chooseMinNode() 
	{		/* find the shortest node in Sbar */
		int i,rho;

		rho = -1;
		for (i = pre_s_first; i>=0; i = v[i].succ) 
		{
			if ((rho < 0)||(rho>v[i].dist)) 
			{
				rho = v[i].dist;
				u = i;
			}
		}
		remove_pre_s(u);
		v[u].succ = INPROGRESS_LABEL;
	}

	void endLoop() {
		v[u].succ = COMPLETION_LABEL;
	}

	void printPaths()
	{
		int i,j;
		for(i = 1; i <= n; i ++)
		{
			j = i - 1;
			while(v[j].prev >= 0)
			{
				System.out.print(v[j].name + ":"+v[j].real_dist+" ");
				j = v[j].prev;
			}
			System.out.println("##");
		}
		System.out.println("_______________");
	}
	
	public DefaultMutableTreeNode constructTree(String strDest)
	{
		int nDest = findNode(strDest);
		if(nDest == -1)
			return null;
		DefaultMutableTreeNode root = new DefaultMutableTreeNode(v[nDest]);
		v[nDest].treeNode = root;
		v[nDest].bVisited = true;
		
		int count,i,j;
		i = nDest;
		DefaultMutableTreeNode iterator = root, tempNode, curNode;
		while(v[i].prev >= 0)
		{
			j = v[i].prev;
			tempNode = new DefaultMutableTreeNode(v[j]);
			v[j].treeNode = tempNode;
			v[j].bVisited = true;
			iterator.add(tempNode);

			iterator = tempNode;
			i = v[i].prev;
		}
			
		for(count = 1; count <= n; count ++)
			recursion(count-1);
		//for debug
		printPaths();
		for (Enumeration e = root.breadthFirstEnumeration() ; e.hasMoreElements() ;) 
		{
			DefaultMutableTreeNode treenode = (DefaultMutableTreeNode)(e.nextElement());
			
			System.err.println(((GANode)treenode.getUserObject()).name);
			log.debug(((GANode)treenode.getUserObject()).name);
		}
		return root;
	}

	public DefaultMutableTreeNode getTreeNode(String name)
	{
		int i = findNode(name);
		if(i == -1)
			return null;
		else
			return v[i].treeNode;
	}

	private DefaultMutableTreeNode recursion(int i)
	{
		DefaultMutableTreeNode tempNode, curNode;
		if(i < 0)
			return null;
        	if(v[i].bVisited)//Return the treeNode
			return v[i].treeNode;

		curNode = new DefaultMutableTreeNode(v[i]);
		v[i].bVisited = true;
		v[i].treeNode = curNode;

		tempNode = recursion(v[i].prev);

		if(tempNode != null) //v[j].prev < 0
			tempNode.add(curNode);

		return curNode;
	}

	public void init(String configFile, String sourceNode)
	{
		int node;
		try {
			InputStream is;

			URI configURI = new URI(configFile);
			if(configURI.isAbsolute())
				is = configURI.toURL().openStream();
			else
				is = new FileInputStream(configFile);

			input_graph(is);
			try {
				if (is != null)
					is.close();
				} catch(Exception e) {
					log.fatal("can't close the config file");
			}
		} catch (FileNotFoundException e) {
			System.err.println("File not found.");
			System.exit(-1);
		} catch (IOException e) {
			System.err.println("Cannot access file.");
			System.exit(-1);
		} catch (java.net.URISyntaxException  e){
			System.err.println("the incorrect URI");
			System.exit(-1);
		}

		if((node = findNode(sourceNode)) == -1)
		{
			log.fatal("can't find the source node in the graph");
			snode = 0;
		}
		else
			snode = node;

		construct_adjlist();
		getShortestPaths();

	}


	public void init(String configFile, int sourceNode)
	{

		try {
			InputStream is;

			URI configURI = new URI(configFile);
			if(configURI.isAbsolute())
				is = configURI.toURL().openStream();
			else
				is = new FileInputStream(configFile);

			input_graph(is);
			try {
				if (is != null)
					is.close();
				} catch(Exception e) {
			}
		} catch (FileNotFoundException e) {
			System.err.println("File not found.");
			System.exit(-1);
		} catch (IOException e) {
			System.err.println("Cannot access file.");
			System.exit(-1);
		} catch (java.net.URISyntaxException  e){
			System.err.println("the incorrect URI");
			System.exit(-1);
		}

		if(sourceNode > 0)
			snode = sourceNode;
		else
			snode = 0;

		construct_adjlist();
		getShortestPaths();
	//	printPaths();
	}


	public void getShortestPaths()
	{
		init_step1();
		int i;
		for(i = 1; i <= n; i++)
		{	
			updateDist();
			chooseMinNode();
		}
		endLoop();
	}
}