|
|
/*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.*/
|
|
|
|
|
|
|
|
|
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<Integer>[] getRandomTree2(int n, Random rnd)
|
|
|
{
|
|
|
@SuppressWarnings("unchecked")
|
|
|
List<Integer>[] 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<Integer>[] pruferCode2Tree(int[] pruferCode)
|
|
|
{
|
|
|
int n = pruferCode.length + 2;
|
|
|
@SuppressWarnings("unchecked")
|
|
|
List<Integer>[] 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<Integer>[] 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<Integer>[] 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<Integer>[] 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<Integer>[] getRandomUndirectedConnectedGraph(int V,
|
|
|
int E, Random rnd)
|
|
|
{
|
|
|
List<Integer>[] g = getRandomTree(V, rnd);
|
|
|
Set<Long> 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<Long> 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<Integer>[] getRandomUndirectedConnectedGraph2(int V,
|
|
|
int E, Random rnd)
|
|
|
{
|
|
|
List<Integer>[] g = getRandomTree(V, rnd);
|
|
|
Set<Long> 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<Integer>[] 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<Integer>[] 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();
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
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]
|