Java Program to Create the Prufer Code for a Tree

Code:

package com.executecodes.combinatorial;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;

public class PruferCode
{
    public static List[] getRandomTree2(int n, Random rnd)
    {
        @SuppressWarnings("unchecked")
        List[] t = new List[n];
        for (int i = 0; i < n; i++)
            t[i] = new ArrayList<>();
        int[] p = new int[n];
        for (int i = 0, j; i < n; j = rnd.nextInt(i + 1), p[i] = p[j], p[j] = i, i++)
            ; // random permutation
        for (int i = 1; i < n; i++)
        {
            int parent = p[rnd.nextInt(i)];
            t[parent].add(p[i]);
            t[p[i]].add(parent);
        }
        return t;
    }

    public static List[] pruferCode2Tree(int[] pruferCode)
    {
        int n = pruferCode.length + 2;
        @SuppressWarnings("unchecked")
        List[] tree = new List[n];
        for (int i = 0; i < n; i++)
            tree[i] = new ArrayList<>();
        int[] degree = new int[n];
        Arrays.fill(degree, 1);
        for (int v : pruferCode)
            ++degree[v];
        int ptr = 0;
        while (degree[ptr] != 1)
            ++ptr;
        int leaf = ptr;
        for (int v : pruferCode)
        {
            tree[leaf].add(v);
            tree[v].add(leaf);
            --degree[leaf];
            --degree[v];
            if (degree[v] == 1 && v < ptr)
            {
                leaf = v;
            }
            else
            {
                for (++ptr; ptr < n && degree[ptr] != 1; ++ptr)
                    ;
                leaf = ptr;
            }
        }
        for (int v = 0; v < n - 1; v++)
        {
            if (degree[v] == 1)
            {
                tree[v].add(n - 1);
                tree[n - 1].add(v);
            }
        }
        return tree;
    }

    public static int[] tree2PruferCode(List[] tree)
    {
        int n = tree.length;
        int[] parent = new int[n];
        parent[n - 1] = -1;
        pruferDfs(tree, parent, n - 1);
        int[] degree = new int[n];
        int ptr = -1;
        for (int i = 0; i < n; ++i)
        {
            degree[i] = tree[i].size();
            if (degree[i] == 1 && ptr == -1)
                ptr = i;
        }
        int[] res = new int[n - 2];
        int leaf = ptr;
        for (int i = 0; i < n - 2; ++i)
        {
            int next = parent[leaf];
            res[i] = next;
            --degree[next];
            if (degree[next] == 1 && next < ptr)
            {
                leaf = next;
            }
            else
            {
                ++ptr;
                while (ptr < n && degree[ptr] != 1)
                    ++ptr;
                leaf = ptr;
            }
        }
        return res;
    }

    static void pruferDfs(List[] tree, int[] parent, int v)
    {
        for (int i = 0; i < tree[v].size(); ++i)
        {
            int to = tree[v].get(i);
            if (to != parent[v])
            {
                parent[to] = v;
                pruferDfs(tree, parent, to);
            }
        }
    }

    // precondition: n >= 2
    public static List[] getRandomTree(int V, Random rnd)
    {
        int[] a = new int[V - 2];
        for (int i = 0; i < a.length; i++)
        {
            a[i] = rnd.nextInt(V);
        }
        return pruferCode2Tree(a);
    }

    // precondition: V >= 2, V-1 <= E <= V*(V-1)/2
    public static List[] getRandomUndirectedConnectedGraph(int V,
            int E, Random rnd)
    {
        List[] g = getRandomTree(V, rnd);
        Set edgeSet = new LinkedHashSet<>();
        for (int i = 0; i < V; i++)
        {
            for (int j = i + 1; j < V; j++)
            {
                edgeSet.add(((long) i << 32) + j);
            }
        }
        for (int i = 0; i < V; i++)
        {
            for (int j : g[i])
            {
                edgeSet.remove(((long) i << 32) + j);
            }
        }
        List edges = new ArrayList<>(edgeSet);
        for (int x : getRandomArrangement(edges.size(), E - (V - 1), rnd))
        {
            long e = edges.get(x);
            int u = (int) (e >>> 32);
            int v = (int) e;
            g[u].add(v);
            g[v].add(u);
        }
        for (int i = 0; i < V; i++)
            Collections.sort(g[i]);
        return g;
    }

    // precondition: V >= 2, V-1 <= E <= V*(V-1)/2
    public static List[] getRandomUndirectedConnectedGraph2(int V,
            int E, Random rnd)
    {
        List[] g = getRandomTree(V, rnd);
        Set edgeSet = new LinkedHashSet<>();
        for (int i = 0; i < V; i++)
        {
            for (int j : g[i])
            {
                edgeSet.add(((long) i << 32) + j);
            }
        }
        for (int i = 0; i < E - (V - 1); i++)
        {
            int u;
            int v;
            long edge;
            while (true)
            {
                u = rnd.nextInt(V);
                v = rnd.nextInt(V);
                edge = ((long) u << 32) + v;
                if (u < v && !edgeSet.contains(edge))
                    break;
            }
            edgeSet.add(edge);
            g[u].add(v);
            g[v].add(u);
        }
        for (int i = 0; i < V; i++)
            Collections.sort(g[i]);
        return g;
    }

    static int[] getRandomArrangement(int n, int m, Random rnd)
    {
        int[] res = new int[n];
        for (int i = 0; i < n; i++)
        {
            res[i] = i;
        }
        for (int i = 0; i < m; i++)
        {
            int j = n - 1 - rnd.nextInt(n - i);
            int t = res[i];
            res[i] = res[j];
            res[j] = t;
        }
        return Arrays.copyOf(res, m);
    }

    static void checkGraph(int V, int E, Random rnd)
    {
        List[] g = getRandomUndirectedConnectedGraph(V, E, rnd);
        int n = g.length;
        int[][] a = new int[n][n];
        int edges = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j : g[i])
            {
                ++a[i][j];
                ++edges;
            }
        }
        if (edges != 2 * E)
        {
            throw new RuntimeException();
        }
        for (int i = 0; i < n; i++)
        {
            if (a[i][i] != 0)
            {
                throw new RuntimeException();
            }
            for (int j = 0; j < n; j++)
            {
                if (a[i][j] != a[j][i] || a[i][j] != 0 && a[i][j] != 1)
                {
                    throw new RuntimeException();
                }
            }
        }
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the length of code: ");
        int n = sc.nextInt();
        int[] code = new int[n];
        for (int i = 0; i < n; i++)
        {
            code[i] = sc.nextInt();
        }
        List[] tree = pruferCode2Tree(code);
        Random rnd = new Random(1);
        for (int step = 0; step < 1000; step++)
        {
            int V = rnd.nextInt(50) + 2;
            checkGraph(V, V - 1, rnd);
            checkGraph(V, V * (V - 1) / 2, rnd);
            checkGraph(V, rnd.nextInt(V * (V - 1) / 2 - (V - 1) + 1) + V - 1,
                    rnd);
        }
        System.out.println("Prufer code to tree conversion: "
                + Arrays.toString(tree));
        System.out.println("Tree to prufer code conversion: "
                + Arrays.toString(tree2PruferCode(tree)));
        sc.close();
    }
}


Output:

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]



More Java Programs: