graphalgorithm.java

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

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



	public 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;
//				System.out.println(edge.rndd_plus);
				break;
			case StreamTokenizer.TT_WORD:
				edge.rndd_plus = findNode(st.sval);
//				System.out.println(st.sval);
//				System.out.println(edge.rndd_plus);
				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*(1-INIT_UTILITY)));
			edge.len = (int)st.nval;
	//		edge.full_len = (int)((double)edge.len/INIT_UTILITY);
			edge.util = INIT_UTILITY;
			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;
		}*/
	}

	protected synchronized int getFakeLen(int index)
	{
		if(index < 0 || index > m)
		{
			log.error("the index is out of boundary");
			return -1;
		}

		return e[index].fake_len;
	}


	public synchronized void setUtil(int index, double util)
	{
		if(index < 0 || index > m)
		{
			log.error("the index is out of boundary");
			return ;
		}

//		e[index].len = len;
		e[index].util = util;
		e[index].fake_len = (int)((double)MAXINT/((double)(e[index].len)*(1-util)));

	}



	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;
//			System.out.println(k);
			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) {
		d[i].succ = d[i].pred = -1;
		if (pre_s_first<0)
			pre_s_first = i;
		else
			d[pre_s_last].succ = i;
		d[i].pred = pre_s_last;
		pre_s_last = i;
	}

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

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

	public boolean init_dynamic_variables(String sourceNode) 
	{
		int node;
		if((node = findNode(sourceNode)) == -1)
		{
			log.fatal("can't find the source node in the graph");
			return false;
		}
		return init_dynamic_variables(node);
	}

	public boolean init_dynamic_variables(int node)
	{
		int i, j;
		u = snode = node;

		for (i=0; i<n; i++) {
			if(d[i] == null)
			{
				d[i] = new DynamicEnv();
				d[i].name = v[i].name;
			}
			d[i].succ = d[i].pred = START_LABEL;
			d[i].prev = d[i].dist = d[i].real_dist = -1;
		}
		d[u].succ = INPROGRESS_LABEL;
		d[u].dist = 0;
		d[u].real_dist = 0;
		pre_s_first = pre_s_last = -1;

		for (i=0; i<n; i++) {
		//	d[i].treeNode = null;
			d[i].bVisited = false;
		//	d[i].vecStages = null;
		//	d[i].table = new int[50];
			d[i].visitArray = new Visit[50];
			d[i].numVisits = 0;
			d[i].strPlacement = new String[50];
		//	for(j = 0; j < 50; j ++)
		//		d[i].table[j] = 1;
		}
		return true;
	}

	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 = d[i].succ) 
		{
			if ((rho < 0)||(rho>d[i].dist)) 
			{
				rho = d[i].dist;
				u = i;
			}
		}
		remove_pre_s(u);
		d[u].succ = INPROGRESS_LABEL;
	}

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

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

			iterator = tempNode;
			i = d[i].prev;
		}
			
		//Originally, the recursion function is designed to
		//add all vertices to the tree we are constructing, 
		//but the problem of this function is that it makes
		//the node representing the source the root of the
		//tree. This contradicts to the above "while" loop,
		//in which the node is a leaf of the tree
		//
		//Therefore, we just comment it out
		
/*		for(count = 1; count <= n; count ++)
			recursion(count-1); */
		//for debug
		//printPaths();
		/*for (Enumeration e = root.breadthFirstEnumeration() ; e.hasMoreElements() ;) 
		{
			DefaultMutableTreeNode treenode = (DefaultMutableTreeNode)(e.nextElement());
			
			log.debug(((DynamicEnv)treenode.getUserObject()).name);
		} */
		return tempNode;
	}

	public synchronized DefaultMutableTreeNode getTreeNode(String name, int nstage, int nplacement)
	{
		int i = findNode(name);
		if(i == -1)
			return null;
		else
			return d[i].getTreeNode(nstage, nplacement);
	}

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

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

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

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

		return curNode;
	} */

	public void init(String topologyFile)
	{
		int node;
		try {
			InputStream is;

			URI topologyURI = new URI(topologyFile);
			if(topologyURI.isAbsolute())
				is = topologyURI.toURL().openStream();
			else
				is = new FileInputStream(topologyFile);

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

		construct_adjlist();
	}

	
	public synchronized void calculateKeyPaths(String strSource)
	{
		int i;

		if(!init_dynamic_variables(strSource))
		{
			log.error("can't init the graph");
			return;
		}

		for(i = 1; i <= n; i++)
		{	
			updateDist();
			chooseMinNode();
		}
		endLoop();
	}

	public synchronized void calculateKeyPaths(int nSource)
	{
		calculateKeyPaths(v[nSource].name);
	}


	public synchronized String nextConnection(int curStage, int curPlacement)
	{
		int numStages = ((Integer)XMLConfigurator.getParameter("numStages")).intValue();

		if(curStage == numStages || curStage < 1)
			return null;
		int numPlacements = ((Integer)XMLConfigurator.getParameter("stages|stage" + curStage + "|numPlacements")).intValue();
		log.debug("numSTages:" + numStages + "numPlacement:" + numPlacements + "curSTage:"  + curStage + "curPlacement: " + curPlacement);
		if(curPlacement < 1)
		{
			log.error("curPlacement is out of bound");
			return null;
		}

		String strNextConnection = (String)XMLConfigurator.getParameter("stages|stage" + curStage +"|connection" + curPlacement);
		log.debug(strNextConnection);
		String [] places = strNextConnection.split(":");
		int nextStage = Integer.parseInt(places[0].substring(5)); //the length of "placement" is 9
		int nextPlacement = Integer.parseInt(places[1].substring(9)); //the length of "placement" is 9
		log.debug("mystage is " + nextStage + " myplacement is " + nextPlacement);
		return "stage" + nextStage + ":placement" + nextPlacement;
	}
}