Java Program to Create the Prufer Code for a Tree

«
»
This is a java program to create Prufer code for a tree. In combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on n vertices has length n – 2, and can be generated by a simple iterative algorithm.

Here is the source code of the Java Program to Create the Prufer Code for a Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. package com.sanfoundry.combinatorial;
  3.  
  4. import java.util.ArrayList;
  5. import java.util.Arrays;
  6. import java.util.Collections;
  7. import java.util.LinkedHashSet;
  8. import java.util.List;
  9. import java.util.Random;
  10. import java.util.Scanner;
  11. import java.util.Set;
  12.  
  13. public class PruferCode
  14. {
  15.     public static List<Integer>[] getRandomTree2(int n, Random rnd)
  16.     {
  17.         @SuppressWarnings("unchecked")
  18.         List<Integer>[] t = new List[n];
  19.         for (int i = 0; i < n; i++)
  20.             t[i] = new ArrayList<>();
  21.         int[] p = new int[n];
  22.         for (int i = 0, j; i < n; j = rnd.nextInt(i + 1), p[i] = p[j], p[j] = i, i++)
  23.             ; // random permutation
  24.         for (int i = 1; i < n; i++)
  25.         {
  26.             int parent = p[rnd.nextInt(i)];
  27.             t[parent].add(p[i]);
  28.             t[p[i]].add(parent);
  29.         }
  30.         return t;
  31.     }
  32.  
  33.     public static List<Integer>[] pruferCode2Tree(int[] pruferCode)
  34.     {
  35.         int n = pruferCode.length + 2;
  36.         @SuppressWarnings("unchecked")
  37.         List<Integer>[] tree = new List[n];
  38.         for (int i = 0; i < n; i++)
  39.             tree[i] = new ArrayList<>();
  40.         int[] degree = new int[n];
  41.         Arrays.fill(degree, 1);
  42.         for (int v : pruferCode)
  43.             ++degree[v];
  44.         int ptr = 0;
  45.         while (degree[ptr] != 1)
  46.             ++ptr;
  47.         int leaf = ptr;
  48.         for (int v : pruferCode)
  49.         {
  50.             tree[leaf].add(v);
  51.             tree[v].add(leaf);
  52.             --degree[leaf];
  53.             --degree[v];
  54.             if (degree[v] == 1 && v < ptr)
  55.             {
  56.                 leaf = v;
  57.             }
  58.             else
  59.             {
  60.                 for (++ptr; ptr < n && degree[ptr] != 1; ++ptr)
  61.                     ;
  62.                 leaf = ptr;
  63.             }
  64.         }
  65.         for (int v = 0; v < n - 1; v++)
  66.         {
  67.             if (degree[v] == 1)
  68.             {
  69.                 tree[v].add(n - 1);
  70.                 tree[n - 1].add(v);
  71.             }
  72.         }
  73.         return tree;
  74.     }
  75.  
  76.     public static int[] tree2PruferCode(List<Integer>[] tree)
  77.     {
  78.         int n = tree.length;
  79.         int[] parent = new int[n];
  80.         parent[n - 1] = -1;
  81.         pruferDfs(tree, parent, n - 1);
  82.         int[] degree = new int[n];
  83.         int ptr = -1;
  84.         for (int i = 0; i < n; ++i)
  85.         {
  86.             degree[i] = tree[i].size();
  87.             if (degree[i] == 1 && ptr == -1)
  88.                 ptr = i;
  89.         }
  90.         int[] res = new int[n - 2];
  91.         int leaf = ptr;
  92.         for (int i = 0; i < n - 2; ++i)
  93.         {
  94.             int next = parent[leaf];
  95.             res[i] = next;
  96.             --degree[next];
  97.             if (degree[next] == 1 && next < ptr)
  98.             {
  99.                 leaf = next;
  100.             }
  101.             else
  102.             {
  103.                 ++ptr;
  104.                 while (ptr < n && degree[ptr] != 1)
  105.                     ++ptr;
  106.                 leaf = ptr;
  107.             }
  108.         }
  109.         return res;
  110.     }
  111.  
  112.     static void pruferDfs(List<Integer>[] tree, int[] parent, int v)
  113.     {
  114.         for (int i = 0; i < tree[v].size(); ++i)
  115.         {
  116.             int to = tree[v].get(i);
  117.             if (to != parent[v])
  118.             {
  119.                 parent[to] = v;
  120.                 pruferDfs(tree, parent, to);
  121.             }
  122.         }
  123.     }
  124.  
  125.     // precondition: n >= 2
  126.     public static List<Integer>[] getRandomTree(int V, Random rnd)
  127.     {
  128.         int[] a = new int[V - 2];
  129.         for (int i = 0; i < a.length; i++)
  130.         {
  131.             a[i] = rnd.nextInt(V);
  132.         }
  133.         return pruferCode2Tree(a);
  134.     }
  135.  
  136.     // precondition: V >= 2, V-1 <= E <= V*(V-1)/2
  137.     public static List<Integer>[] getRandomUndirectedConnectedGraph(int V,
  138.             int E, Random rnd)
  139.     {
  140.         List<Integer>[] g = getRandomTree(V, rnd);
  141.         Set<Long> edgeSet = new LinkedHashSet<>();
  142.         for (int i = 0; i < V; i++)
  143.         {
  144.             for (int j = i + 1; j < V; j++)
  145.             {
  146.                 edgeSet.add(((long) i << 32) + j);
  147.             }
  148.         }
  149.         for (int i = 0; i < V; i++)
  150.         {
  151.             for (int j : g[i])
  152.             {
  153.                 edgeSet.remove(((long) i << 32) + j);
  154.             }
  155.         }
  156.         List<Long> edges = new ArrayList<>(edgeSet);
  157.         for (int x : getRandomArrangement(edges.size(), E - (V - 1), rnd))
  158.         {
  159.             long e = edges.get(x);
  160.             int u = (int) (e >>> 32);
  161.             int v = (int) e;
  162.             g[u].add(v);
  163.             g[v].add(u);
  164.         }
  165.         for (int i = 0; i < V; i++)
  166.             Collections.sort(g[i]);
  167.         return g;
  168.     }
  169.  
  170.     // precondition: V >= 2, V-1 <= E <= V*(V-1)/2
  171.     public static List<Integer>[] getRandomUndirectedConnectedGraph2(int V,
  172.             int E, Random rnd)
  173.     {
  174.         List<Integer>[] g = getRandomTree(V, rnd);
  175.         Set<Long> edgeSet = new LinkedHashSet<>();
  176.         for (int i = 0; i < V; i++)
  177.         {
  178.             for (int j : g[i])
  179.             {
  180.                 edgeSet.add(((long) i << 32) + j);
  181.             }
  182.         }
  183.         for (int i = 0; i < E - (V - 1); i++)
  184.         {
  185.             int u;
  186.             int v;
  187.             long edge;
  188.             while (true)
  189.             {
  190.                 u = rnd.nextInt(V);
  191.                 v = rnd.nextInt(V);
  192.                 edge = ((long) u << 32) + v;
  193.                 if (u < v && !edgeSet.contains(edge))
  194.                     break;
  195.             }
  196.             edgeSet.add(edge);
  197.             g[u].add(v);
  198.             g[v].add(u);
  199.         }
  200.         for (int i = 0; i < V; i++)
  201.             Collections.sort(g[i]);
  202.         return g;
  203.     }
  204.  
  205.     static int[] getRandomArrangement(int n, int m, Random rnd)
  206.     {
  207.         int[] res = new int[n];
  208.         for (int i = 0; i < n; i++)
  209.         {
  210.             res[i] = i;
  211.         }
  212.         for (int i = 0; i < m; i++)
  213.         {
  214.             int j = n - 1 - rnd.nextInt(n - i);
  215.             int t = res[i];
  216.             res[i] = res[j];
  217.             res[j] = t;
  218.         }
  219.         return Arrays.copyOf(res, m);
  220.     }
  221.  
  222.     static void checkGraph(int V, int E, Random rnd)
  223.     {
  224.         List<Integer>[] g = getRandomUndirectedConnectedGraph(V, E, rnd);
  225.         int n = g.length;
  226.         int[][] a = new int[n][n];
  227.         int edges = 0;
  228.         for (int i = 0; i < n; i++)
  229.         {
  230.             for (int j : g[i])
  231.             {
  232.                 ++a[i][j];
  233.                 ++edges;
  234.             }
  235.         }
  236.         if (edges != 2 * E)
  237.         {
  238.             throw new RuntimeException();
  239.         }
  240.         for (int i = 0; i < n; i++)
  241.         {
  242.             if (a[i][i] != 0)
  243.             {
  244.                 throw new RuntimeException();
  245.             }
  246.             for (int j = 0; j < n; j++)
  247.             {
  248.                 if (a[i][j] != a[j][i] || a[i][j] != 0 && a[i][j] != 1)
  249.                 {
  250.                     throw new RuntimeException();
  251.                 }
  252.             }
  253.         }
  254.     }
  255.  
  256.     public static void main(String[] args)
  257.     {
  258.         Scanner sc = new Scanner(System.in);
  259.         System.out.println("Enter the length of code: ");
  260.         int n = sc.nextInt();
  261.         int[] code = new int[n];
  262.         for (int i = 0; i < n; i++)
  263.         {
  264.             code[i] = sc.nextInt();
  265.         }
  266.         List<Integer>[] tree = pruferCode2Tree(code);
  267.         Random rnd = new Random(1);
  268.         for (int step = 0; step < 1000; step++)
  269.         {
  270.             int V = rnd.nextInt(50) + 2;
  271.             checkGraph(V, V - 1, rnd);
  272.             checkGraph(V, V * (V - 1) / 2, rnd);
  273.             checkGraph(V, rnd.nextInt(V * (V - 1) / 2 - (V - 1) + 1) + V - 1,
  274.                     rnd);
  275.         }
  276.         System.out.println("Prufer code to tree conversion: "
  277.                 + Arrays.toString(tree));
  278.         System.out.println("Tree to prufer code conversion: "
  279.                 + Arrays.toString(tree2PruferCode(tree)));
  280.         sc.close();
  281.     }
  282. }

Output:

advertisement
$ javac PruferCode.java
$ java PruferCode
 
Enter the length of code: 
4
2 3 4 3 
Prufer code to tree conversion: [[2], [3], [0, 4], [1, 4, 5], [2, 3], [3]]
Tree to prufer code conversion: [2, 3, 4, 3]
 
Enter the length of code: 
3
2 4 3 
Prufer code to tree conversion: [[2], [4], [0, 3], [2, 4], [1, 3]]
Tree to prufer code conversion: [2, 4, 3]
 
Enter the length of code: 
5
3 4 5 1 6
Prufer code to tree conversion: [[3], [4, 6], [4], [0, 5], [2, 1], [3, 6], [1, 5]]
Tree to prufer code conversion: [3, 4, 5, 1, 6]

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Reference Books in Java Programming, Data Structures and Algorithms.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter