mynode.java

Petri网分析工具PIPE is open-source

/*
 * Created on Feb 10, 2004
 *
 * To change the template for this generated file go to
 * Window - Preferences - Java - Code Generation - Code and Comments
 */
package pipe.dataLayer.calculations;

/**
 * @author Matthew Cook after James Bloom/Clare Clark
 *Class used in state space and GSPN modules for generation of trees and arrays of possible state spaces
 *
 */
public class  myNode  {

	boolean[] trans_array;     //array of transitions
	myNode parent;             //parent node
	myNode[] children;         //child nodes
	myTree tree;               //tree that contains the node
	int[] Markup;      //The marking of the node
	myNode previousInstance;   //same node found in tree
	int depth;        // The depth this node is in the tree

	//Attributes used for assessing whether a node has occured before
	boolean Repeated_Node = false;

	/*-------------------------------------------------------------------
	 Function: void myNode(int[] marking_array, myTree tree)

	 Node constructor called by the tree object

	 -------------------------------------------------------------------*/

	public myNode(int [] marking_array, myTree atree, int treeDepth) {
		int i;             //counter for 'for printing loop'

		//Node now knows its tree in order to use its attributes
		tree = atree;

		depth = treeDepth;

		//Update the count of nodes
		tree.nodeCount++;

		//Set up marking for this node
		Markup = marking_array;  //created in myTree
//        System.out.print("Node "+tree.nodeCount+" Created \n" );

		//Assign the root nodes parents (this constructor only called by tree)
		parent = tree.root; //Just get root to have itself as parent

		//Create an array of transitions for each node
		trans_array = new boolean[tree.number_transitions];

		//Create an array of nodes for each node (for children)
		//Number of children limited by total number of transitions
		children = new myNode[tree.number_transitions];

		//Initialise trans_array
		for(i=0; i< tree.number_transitions; i++){
			trans_array[i] = false;
		}

//        for(i=0; i< Markup.length; i++) {
//          System.out.print(this.Markup[i]);
//          System.out.print(" ");
//        }



	}


	/*-------------------------------------------------------------------
	 Function: void myNode(int[] marking_array, myNode parent_node, myTree atree)

	 The overloaded Node constructor called by a node object

	 -------------------------------------------------------------------*/

	public myNode(int [] marking_array, myNode parent_node, myTree atree, int treeDepth) {
		int i;             //counter for 'for printing loop'

		//Node now knows its tree in order to use its attributes
		tree = atree;

		depth = treeDepth;

		//Update the count of nodes
		tree.nodeCount++;

		//Set up marking for this node
		Markup = marking_array;  //created in myTree

		//Assign the nodes parents
		parent = parent_node;

//        System.out.print("Node "+tree.nodeCount+" Created \n" );

		//Create an array of transitions for each node
		trans_array = new boolean[tree.number_transitions];

		//Create an array of nodes for each node (for children)
		//Number of children limited to total number of transitions.
		children = new myNode[tree.number_transitions];

		//Initialise trans_array
		for(i=0; i< tree.number_transitions; i++){
			trans_array[i] = false;
		}

//        for(i=0; i< Markup.length; i++) {
//          System.out.print(this.Markup[i]);
//          System.out.print(" ");
//        }

	}
	/*---------------------------------------------------------------------
	 Function: boolean TransitionEnabled(int transIndex)

	 Tests to see if a particular transition is enabled by consulting C-
	 and the current markup contained in the tree.
	 transIndex = usual petri net description of a transition by an integer

	 ---------------------------------------------------------------------*/

	public  boolean TransitionEnabled(int transIndex) {
		int count;        //index for 'for loop'
		int CMinusValue;
		
		
		for(count=0; count < tree.number_places; count++)
		{

			CMinusValue = (tree.CMinus).get(count,(transIndex-1));
			if((Markup[count] < CMinusValue) && Markup[count]!=-1)
			{
				//There is a place where marking is less than required in CMinus
				return false;
			}
		}

		//All places satisfy the marking criteria
		return true;

	}

	/*---------------------------------------------------------------------
	 Function: int[] fire(int trans)

	 Produces a new markup vector to simulate the firing of a transition.
	 Destroys the number of tokens shown in CMinus for a given place and
	 transition, and creates the number of tokens shown in CPlus.

	 TransIndex refers to the actual transition number ie starting at 1.
	 ---------------------------------------------------------------------*/

	public int[] fire(int transIndex) {
		int count;                     //index for 'for loop'
		int CMinusValue;         //Value from C- matrix
		int CPlusValue;          //Value from C+ matrix

		//Create marking array to return
		int[] marking = new int[tree.number_places];

		for(count = 0; count < tree.number_places; count++)
		{
			CMinusValue = (tree.CMinus).get(count, (transIndex - 1));
			CPlusValue = (tree.CPlus).get(count, (transIndex - 1));

			if (Markup[count]!=-1)
				marking[count] = Markup[count] - CMinusValue + CPlusValue;
			else
				marking[count] = Markup[count];
		}

		//Return this new marking to RecursiveExpansion function
		//int size = marking.length;
		//for (int t = 0; t < size; t++){
		//	System.out.print(Markup[t]+ " ");
		//}
		//System.out.println();
		return marking;
	}

	/*----------------------------------------------------------------------
	 Function: void RecursiveExpansion()

	 Undertakes a recursive expansion of the tree
	 Called on root node from within the tree constructor.

	 -----------------------------------------------------------------------*/

	public void RecursiveExpansion() throws TreeTooBigException {
		int transIndex;                              //Index to count transitions
		int[] new_markup;                            //markup used to create new node
		int i;                     //index for loops
		boolean A_Transition_Is_Enabled = false;     //To check for deadlock
		boolean allOmegas;

		
		
		//For each transition
		for(transIndex = 1; transIndex <= tree.number_transitions; transIndex++)
		{
			//If it is enabled as described by CMinus and Markup
			if(TransitionEnabled(transIndex) == true)
			{
				//Set trans_array of to true for this index
				//index 0 refers to transition 1 here.
				trans_array[transIndex - 1] = true;

//          System.out.println("\n Transition " +transIndex+ " Enabled \n" );
				A_Transition_Is_Enabled = true;

				//Fire transition to produce new markup vector
				new_markup = fire(transIndex);

//          System.out.println("\n Old Markup is");
//          for(i=0; i< Markup.length; i++){
//            System.out.print(Markup[i]);
//            System.out.print(" ");
//        }
//        System.out.print("\n");

				//Check for safeness. If any of places have > 1 token set variable.
				for(i=0; i< new_markup.length; i++){
					if(new_markup[i] > 1 || new_markup[i]==-1) {
						tree.more_Than_One_Token = true;
					}

					//Print new markup
//            System.out.print(new_markup[i]);
				}

				//Create a new node using the new markup vector and attach it
				//to the current node as a child.

				children[transIndex - 1] = new myNode(new_markup, this, tree, depth+1);

				/* Now need to (a) check if any omegas (represented by -1) need to be
				 inserted in the markup vector of the new node, and (b) if the resulting
				 markup vector has appeared anywhere else in the tree. We must do (a) before
				 (b) as we need to know if the new node contains any omegas to be able to
				 compare it with existing nodes. */

				allOmegas = children[transIndex - 1].InsertOmegas();

				//check if the resulting markup vector has occured anywhere else in the tree

				Repeated_Node = (tree.root).FindMarkup(children[transIndex-1]);

				if (tree.nodeCount>=10000 && !tree.tooBig)
				{
					tree.tooBig = true;
					throw new TreeTooBigException();
				}

				if(!Repeated_Node && !allOmegas)
				{
					children[transIndex - 1].RecursiveExpansion();
				}
			}

		}

		if(!A_Transition_Is_Enabled)
		{
//          System.out.println("No transition enabled");
			if(!tree.no_Enabled_Transitions || tree.pathToDeadlock.length<depth-1)
			{
				RecordDeadlockPath();
				tree.no_Enabled_Transitions = true;
			}
			else
			{
//			System.out.println("Deadlocked node found, but path is not shorter than current path.");
			}
		}
		else
		{
//			System.out.println("Transitions enabled.");
		}
	}

	/*----------------------------------------------------------------------
	 Function: void RecordDeadlockPath()

	 If there is a deadlock, calculates the path
	 -----------------------------------------------------------------------*/

	public void RecordDeadlockPath() {
		myNode currentNode;      //The current node we're considering
		int[] path;              //returned showing path to deadlock
		int pos;                 //position in path array
		int i;

		//Set up array to return
		tree.pathToDeadlock = new int[depth-1];