Мне нужен редактор, позволяющий вводить дерево, каждый узел которого может содержать несколько подузлов.
Входная часть проста. Я могу использовать только текстовый редактор и иерархический список, например
* a ** b ** c *** d
Но мне также нужно сравнить два дерева (найти, есть ли какие-либо различия, и если есть различия, сообщить о них).
Порядок узлов значения не имеет. Таким образом, приведенное выше дерево считается эквивалентным
* a ** c *** d ** b
Я использую Ubuntu Linux, и программное обеспечение должно поставляться бесплатно.
Частичный ответ лучше, чем ничего. Этот метод может возвращать ложноположительный результат (см. примечания в конце), но не ложноотрицательный ( т . е . отрицательные результаты надежны).
tsortполезная утилита, выполняющая топологическую сортировку из стандартного ввода. tsortтребует парного ввода узла, так что это:
* a
** b
** c
*** d
Сначала нужно переформатировать tsort, чтобы выглядело так:
a b
a c
c d
Передайте это через tsort:
printf '%s %s\n' a b a c c d | sort | tsort
Вывод:
a
c
b
d
Используя bashи diff, два дерева в вопросе можно сравнить так:
diff <(printf '%s %s\n' a c c d a b | sort | tsort) \
<(printf '%s %s\n' a b a c c d | sort | tsort)
Выход ничего, так как два дерева равны.
Ноты:
документы нуждаются в tsortулучшении.
Отрицательные результаты (деревья разные) надежны. Положительных результатов, (деревья одинаковые), может и не быть. Некоторые графы (все деревья являются графами), которые отличаются друг от друга, могут иметь одинаковый результат сортировки. Но если diffчто-то и возвращает, то деревья абсолютно не равны.
Пример ложного срабатывания, рассмотрим два дерева:
+---+
| a |
+---+
|
|
v
+---+
| b |
+---+
|
|
v
+---+
| c |
+---+
и:
+---+ +---+
| c | <-- | a |
+---+ +---+
|
|
v
+---+
| b |
+---+
Поместите эти деревья в tsort:
paste <(printf '%s %s\n' a b a c | sort | tsort) \
<(printf '%s %s\n' a c c b | sort | tsort)
Вывод:
a a
c c
b b