Обрезать дерево, построенное из TXT-файла

Question

У меня есть текстовый файл, который содержит последовательность чисел, подобную следующей:

1 1 3 2
2 2 1 1
3 2 3 1
2 2 2 2
1 1 1 1
3 2 3 2
1 1 3 1
2 1 1 1

(Это только пример, объясняющий мою проблему.) Каждая строка в файле txt имеет четырепозиции, разделенные пробелом.Первое и третье могут принимать три значения: 1, 2 или 3. Остальные позиции могут принимать только два значения: 1 или 2.

Каждая строка представляет путь дерева.Дерево состоит из корневого узла и уровней дополнительных узлов, которые образуют иерархию: первый и третий уровни могут иметь три узла (1, 2 или 3) и т. Д., Как описано ранее.

Тогда дерево, описанное в предыдущем примере, выглядит следующим образом:

Я бы подрезал дерево, как описано на следующем рисунке:

Узлы, обведенные красным, должны быть уменьшены до одного узла, поскольку каждый узел в кругах имеет только один лист.

Answer 1

Вы можете определить, какие узлы имеют только один дочерний элемент, посмотрев каждую пару соседних столбцов в вашей таблице / матрице и наблюдая, сколько раз каждое число появляется рядом с другим.Предположим, ваши данные хранятся в mat:

> mat
     [,1] [,2] [,3] [,4]
[1,]    1    1    3    2
[2,]    2    2    1    1
[3,]    3    2    3    1
[4,]    2    2    2    2
[5,]    1    1    1    1
[6,]    3    2    3    2
[7,]    1    1    3    1
[8,]    2    1    1    1

. Для первых двух столбцов мы удаляем все дубликаты (т. Е. Один и тот же подпуть), мы смотрим на вхождения каждого числа с его соседями и подсчитываем, сколькоСуществуют различные пути:

> table(mat[,c(1,2)][!duplicated(mat[,c(1,2)]),1])
1 2 3 
1 2 1 

Как видите, у 1 есть 1 путь, и поэтому его можно удалить, как и 3. Наконец, у 2 есть 2 пути, поэтому мы не будем его обрезать.

Следующая часть сложная, потому что вам нужно только смотреть на поддеревья (потому что, например, 1 -> 1 может встречаться в одной части дерева, а 1 -> 2 - в другойно если они не имеют общего родителя, мы все равно можем их обрезать).Что-то вроде:

table(mat[mat[,newLevel]==newRoot,c(2,3)][!duplicated(mat[mat[,newLevel]==newRoot,c(2,3)]),1])

, где newLevel - это столбец матрицы, к которой вы находитесь, и newRoot значение узла на этом уровне, который будет корнем вашего поддерева.Например, используя узел на первом уровне дерева со значением 2 в качестве корня:

> table(mat[mat[,1]==2,c(2,3)][!duplicated(mat[mat[,1]==2,c(2,3)]),1])
1 2 
1 2 

Как вы можете видеть, он обнаружил, что 1 должен быть сокращен, а 2 - нет, для узлов напрямуюниже первых 2 узлов.Затем вы можете выполнить итерацию по дереву (например, вы можете реализовать это рекурсивно).