CODEWITHSUNDEEP
javaalgorithmdata-structuresgraph
Himani
Himani

Reputation: 51

Copying graph nodes to make a whole new replication of network of nodes

A function that takes a node and copies this and all the adjacent node to create a new structure exactly similar to this one.

A
/ \
B C-E
\ /
D

should create similar network with new nodes

A Node object is defined by

Node{

Arraylist neighbours; // returns all the adjacent nodes in an array list

}

Will this code work?

public Node copyGraph(Node A){
    HashTable<Node, Node> hash = new HashTable<Node, Node> ();

    return copyGraphWithHash(A, hash);

}

public Node copyGraphWithHash(Node A, HashTable<Node, Node> hash){


  if (A.neighbours.size() == 0)
    return null;

  Node newfirst = null;

  if(!hash.hasKey(A))
    newfirst = new Node();
    hash.add(A,newfirst);
  }


  for ( Node n : A.neighbours()){

   if (copyGraphWithHash(n, hash))
         newfirst.neightbours.add(copyGraphWithHash(n, hash));
  }
  return newfirst;
 }

Please suggest what am I missing here ?

Upvotes: 0

Views: 288

Answers (1)

cporte
cporte

Reputation: 2191

This code will end by throwing a stack overflow exception.

Problems :

  • Wrong base case : as long as you have a graph containing at least 2 nodes, you will have an infinite recursion because you will always call the recursive function for every child in every case.
  • Wrong recursive case : the recursive function is called two times in the loop in some case
  • Wrong behaviour if the graph has only one node : it will not be duplicated

Solutions :

  • Remove test on neighbours
  • If the hashtable contains the handled node, directly return the duplicated node
  • If not, create a new node, add the correspondance in the table, and don't forget to initialise the neighbours variable
  • In the loop, remove the test and always fill the neighbours variable

Other potential problems :

  • The recursive function is public. Should not be public if we don't need to provide a pre-filled hashtable
  • Usage of an hashtable instead of an hashmap in a non multi-threaded context
  • No error management if A is null

Upvotes: 1

Related Questions