Preventing a cycle while creating a tree

Background : In our application we are using a tree structure for representing some logic. The tree may contain another tree as a child node. The requirement was to parse the complete tree  structure by traversing it. While traversing the tree, if a child node refers to another tree, we have to parse this child tree node as well.

Eg. suppose we have tree T1 .T1 has child nodes T2 and T3. For creating the logic for T1, we have to parse  T2  and  T3’s logic and put it into T1.

T1

/   \

 T2      T3

Suppose T2 contains child node T4 and T5. Then while creating logic for T1 we have to parse T4 and T5 to build T2 and put in T1.

T2

/   \

 T4      T5

On adding logic of T2 in T1.

T1

/   \

 T2      T3

/   \           

 T4      T5             

If T2 contains T1 then there will be a cycle present in the tree.

T2

/   \

    T1      T5    

In this case, we will parse T1 then T2 then T1 then T2 putting the program into an infinite loop.

T1

/   \

      T2      T3     

      /   \                 

 T1      T5             

Problem statement : We want to create a tree such that, it can add another tree as its child node. There should be no cycle while creating the tree. Hence, we have to find whether a cycle is formed  while adding a child to the tree.

Input : We have set of trees with no cycle and each child node refers to another tree . We created a tree map to represent the relationship between trees in which the treeMap key represents the tree id and value array represents list of  tree id  in its child nodes.

var treeMap   = {

  “node1”: [

      “node4”,

      “node2”,

      “node3”

  ],

  “node2”: [

      “node4”

  ],

  “node3”: [

      “node4”,

      “node2”

  ],

  “node4”:[]

};

In above Map if we add node3 tree in node2 then cycle will be formed .

Output: We created function “isCyclePresent” which returns true if cycle is present after adding  child node in tree.

Basic idea of algorithm is : a breadth first search  begin with node which will be added in given tree. Search will visit every node of the tree exactly once .If we find a node in the child which is same as parent then the is formed

Referred from “Tarjan’s Algorithm

We have implemented  isCyclePresent function using  jQuery.

/*function to prevent cycles in tree on adding new node*/

function isCyclePresent(startNode, newNode ){

  var returnValue =false; //set return value

  var queue       = [];   //to implement queue data structure in javascript

  queue.push(newNode);  //adding element in queue rare end

  var queueElement;

  if( ! $.isEmptyObject(treeMap)) {

      while(queue.length!=0){

          queueElement= queue.shift();  //removing element from queue front end

          //check if start node is equal to it child element

          if(startNode == queueElement ){

              returnValue=true;  //cycle is present

              break;

          }

          //add element to to queue to traverse tree

          if(treeMap[queueElement].length!=0){

              $.each(treeMap[queueElement],function(index,element){

                  queue.push(element);  //adding element in queue rare end

              });

          }

      }

      return returnValue; //return true if cycle present after adding new node in existing tree

  }

  else {

      returnValue=false;

  }

}

Here is a working example – https://jsfiddle.net/ecnw2azp/1/   

Conclusion :  This is a post demonstrating how we can prevent cyclic dependency while creating a tree. So while parsing tree we can insure program never goes into an infinite loop.

Categories: Grails

Leave a Reply

Your email address will not be published. Required fields are marked *

Share: