graphalgorithm.java

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

package org.osu.ogsa.stream.util;

import java.util.*;
import java.io.*;
import java.net.URL;
import java.net.URI;
import javax.swing.tree.*;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.osu.ogsa.stream.util.Visit;
import org.osu.ogsa.stream.util.xmlconfig.XMLConfigurator;

public abstract class GraphAlgorithm extends Object{
	public  static int	n,m;
	public	int	u,snode;	/* start node */
	public	int	pre_s_first, pre_s_last;
	public static	GANode	v[] = new GANode[500];
	public static	Edge	e[] = new Edge[500];
	public DynamicEnv	d[] = new DynamicEnv[500];
	static  double	INIT_UTILITY = 0.20;
	static boolean	isdigraph;
//	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;



	public int findNode(String strName) 
	{
		for (int i=0; i<n; i++)
		{
			if (v[i].name.equals(strName))
				return i;
		}
		log.debug("can't find " + strName);;
		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;
	}

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

		return e[index].util;
	}

	public synchronized double getEdgeUtil(String start_name, String end_name)
	{
		int i = findEdge(start_name, end_name);
		if(i < 0)
			return -1.0;
		else
			return e[i].util;
	}

	public synchronized DefaultMutableTreeNode []  deletePath(DefaultMutableTreeNode treenode, int nChildStage, int nChildPlacement, boolean [][]stagePlacements, boolean bRemoveAllChildren)
	{
		//Remove strSource from its parents.
		//If strSource is the first one to call detele,
		//bRemoveAllChildren is set to true, and its chilren array is returned
		//if strSource isn't the first one, then if strSource still has children
		//stop.
		//else remove itself from its parents
		if(treenode == null)
		{
			log.debug("treenode is null");
			return null;
		}

		DynamicEnv dNode = (DynamicEnv)treenode.getUserObject();
		if(dNode == null)
		{
			log.debug("can't find "+treenode);
			return null;
		}

		String strSource = dNode.name;
		log.debug(strSource);
		String strNextConnection;
		String tempStr = null;
		String [] places;
		int myStage, myPlacement, numStages;
		int i, f;
		boolean bConnectionExist = false;
		i = f = -1;
		myStage = myPlacement = -1;

		numStages = ((Integer)XMLConfigurator.getParameter("numStages")).intValue();

		//get myStage
		if(nChildStage == -1)
		{
			myStage = 1;
			myPlacement = nChildPlacement;
		}
		else if(nChildStage != numStages)
		{
			strNextConnection = (String)XMLConfigurator.getParameter("stages|stage" + nChildStage +"|connection" + nChildPlacement);
			log.debug(strNextConnection);
			places = strNextConnection.split(":");
			myStage = Integer.parseInt(places[0].substring(5)); //the length of "placement" is 9
			myPlacement = Integer.parseInt(places[1].substring(9)); //the length of "placement" is 9
			log.debug("mystage is " + myStage + " myplacement is " + myPlacement);
		}
		if(myStage == numStages)
			return null;


		DefaultMutableTreeNode [] myChildren;
		int nChildCount = treenode.getChildCount();
		log.debug("number of children:" + nChildCount);
		if(nChildCount != 0)
		{
			//first call, and has children
			myChildren = new DefaultMutableTreeNode[nChildCount];
			Enumeration e = treenode.children();
			for(i = 0; e.hasMoreElements(); i ++)
			{
				myChildren[i] = (DefaultMutableTreeNode)(e.nextElement());
				log.debug("child " + i + ":" +  myChildren[i]);
			}
		}
		else
			myChildren = null;

		//remove stages and placements information in the dNode
		InstanceIndex []iiArray = dNode.getInstanceIndex(treenode);
		if(iiArray == null)
		{
			log.error("information in the structure is not correct");
			return myChildren;
		}
		InstanceIndex ii = null;
		DynamicEnv tempDNode = null;
		InstanceIndex tempII = null;
		if(nChildCount == 0 || (nChildCount != 0 && bRemoveAllChildren))
		{
			//remove all the information of stages and placements
			for(i = 0; i < iiArray.length; i++)
			{
				ii = iiArray[i];
				if(ii == null)
				{
					log.error("information in the structure is not correct");
					continue;
				}
				log.debug("stage:" + ii.nstage + " placement: " + ii.nplacement);
				dNode.remove(ii.nstage, ii.nplacement);
				if(ii.nstage > 0 && ii.nplacement > 0)
					stagePlacements[ii.nstage][ii.nplacement] = false;
			}
		}
		else //nChildCount != 0 && !bRemoveAllChildren
		{
			//Check if all treenodes that have "nChildStage" has been delete

			for(i = 0; i < nChildCount; i ++)
			{
				tempDNode = (DynamicEnv)myChildren[i].getUserObject();
				tempII = tempDNode.getInstanceIndex(myChildren[i], nChildStage);
				if(tempII != null)
				{
					tempStr = nextConnection(tempII.nstage, tempII.nplacement);
					if(tempStr != null)
					{
						log.debug(tempStr);
						if(tempStr.equals("stage" + myStage + ":placement" + myPlacement))
						{
							log.debug("there is still one child having stage" + nChildStage + "placement" + tempII.nplacement);
							bConnectionExist = true;
							break;
						}
					}
				}

			}
			//Whether or not we need to check if there are two consecutive stages in the same node
			//There is a bug here ********************************************************
			//When stage 2, 3, 4 etc at the same stage, 3, 4 stages would be checked !!!!!!!!!!
			f = iiArray.length;
			log.debug("the length of instances of " + treenode + " is " + f); 
			if(i == nChildCount)
			{
				for(f = 0; f < iiArray.length; f++)
				{
					ii = iiArray[f];
					if(ii == null)
					{
						log.error("information in the structure is not correct");
						continue;
					}
					log.debug("stage:" + ii.nstage + " placement: " + ii.nplacement);
					tempStr = nextConnection(ii.nstage, ii.nplacement);
					if(tempStr != null)
					{
						log.debug(tempStr);
						if(tempStr.equals("stage" + myStage + ":placement" + myPlacement))
						{
							log.debug("myself has one child having stage" + nChildStage + "placement" + tempII.nplacement);
							bConnectionExist = true;
							break;
						}
					}
				}
			}
			if(f == iiArray.length && i == nChildCount)
			{

				log.debug("no children have stage " + nChildStage);
				log.debug("remove stage " + myStage + " from this node");
				tempII = dNode.getInstanceIndex(treenode, myStage);
				if(tempII == null)
					log.error("can't be null");
				else
				{
					dNode.remove(tempII.nstage, tempII.nplacement);
					if(tempII.nstage > 0 && tempII.nplacement > 0)
						stagePlacements[tempII.nstage][tempII.nplacement] = false;
				}

			}
		}

		if(nChildCount != 0 && bRemoveAllChildren)
		{
			treenode.removeAllChildren();
		}
		if(bConnectionExist)
			return myChildren;

		tempStr = nextConnection(myStage, myPlacement);
		if(tempStr == null)
			return myChildren;

		log.debug(tempStr);
		for(f = 0; f < iiArray.length; f++)
		{
			ii = iiArray[f];
			if(ii == null)
			{
				log.error("information in the structure is not correct");
				continue;
			}
			log.debug("stage:" + ii.nstage + " placement: " + ii.nplacement);
			if(tempStr.equals("stage" + ii.nstage+ ":placement" + ii.nplacement))
			{
				log.debug("need to call this treenode itself");
				deletePath(treenode, myStage, myPlacement, stagePlacements, bRemoveAllChildren);
				return myChildren;
			}
		}

		DefaultMutableTreeNode parent = (DefaultMutableTreeNode)treenode.getParent();
		if(parent != null)
		{
			if(treenode.getChildCount() == 0);
				treenode.removeFromParent();
			deletePath(parent, myStage, myPlacement, stagePlacements, false);
		}
		else
		{
			log.debug("parent is null");
		}

		return myChildren;
	}

	public synchronized boolean merge(GraphAlgorithm ga, DefaultMutableTreeNode leaf)
	{
		//ga represents the source key path
		//"this" object represents the destination 
		if(leaf == null)
			return false;

		DynamicEnv dNode = (DynamicEnv)leaf.getUserObject();
		if(dNode == null)
		{
			log.debug("can't find "+leaf);
			return false;
		}

		String strSource = dNode.name;
		log.debug(strSource);

		DynamicEnv gaNode_Source, gaNode_Dest;
		DefaultMutableTreeNode leafNode, curNode, lastNode = null;
		DefaultMutableTreeNode exitingNode, newPathNode;
		boolean bExit = false;
		boolean completelySame = false;
		int i;
		while(leaf != null && !bExit)
		{
			//Get the corresponding DynamicEnv from the source key path
			//leaf is the source
			gaNode_Source = (DynamicEnv)leaf.getUserObject();
			log.debug(gaNode_Source.name);

			//find the corresponding DynamicEnv in the "this" GraphAlgorithm
			gaNode_Dest = d[findNode(gaNode_Source.name)];
			DefaultMutableTreeNode [] nodes = gaNode_Dest.treeNodes();
			if(nodes != null)
			{
				DynamicEnv gaNode_Source1, gaNode_Dest1;
				log.debug("the number of treenodes at " + gaNode_Source.name + " is " + nodes.length);
				//check if the two pathes are same
				boolean bSame = true;
				for(i = 0; i < nodes.length; i ++)
				{
					exitingNode = (DefaultMutableTreeNode)nodes[i].getParent();;
					newPathNode = (DefaultMutableTreeNode)leaf.getParent();;
					bSame = true;
					while(newPathNode != null)
					{
						if(exitingNode == null)
						{
							bSame = false;
							break;
						}

						gaNode_Source1 = (DynamicEnv)newPathNode.getUserObject();
						gaNode_Dest1 = (DynamicEnv)exitingNode.getUserObject();

						if(gaNode_Source1 == null || gaNode_Dest1 == null)
						{
							log.error("some thing wrong with the ga_config");
							return false;
						}

						if(!gaNode_Source1.name.equals(gaNode_Dest1.name))
						{
							bSame = false;
							break;
						}
						exitingNode = (DefaultMutableTreeNode)exitingNode.getParent();
						newPathNode = (DefaultMutableTreeNode)newPathNode.getParent();
					}
					if(newPathNode == null && exitingNode != null)
						bSame = false;
					if(bSame)
						break;
				}
				if(bSame) //i must be less than length
				{
					curNode = nodes[i];
					//Ready to stop!
					bExit = true;
				}
				else
				{
					log.debug("i:" + i);
					curNode = new DefaultMutableTreeNode(gaNode_Dest);
					//init newTreeNode
					gaNode_Dest.put(curNode, -1, -1);
				}
			}
			else 
			{
				curNode = new DefaultMutableTreeNode(gaNode_Dest);
				//init newTreeNode
				gaNode_Dest.put(curNode, -1, -1);
			}

			if(lastNode != null)
			{
				curNode.add(lastNode);
				//copy the distance information to the last node
			        //from the source tree
				//We should use the last node instead of curNode!!!!!
				((DynamicEnv)lastNode.getUserObject()).real_dist = gaNode_Source.real_dist;
			}