Comparing two finite trees

Question

I need an editor which allows to enter a tree, each node of which may contain several subnodes.

The enter part is easy. I can use just a text editor and a hierarchical list like

* a ** b ** c *** d

But I also need to compare two trees (find if there are any differences and if there are differences report them).

Order of the nodes does not matter. So the above tree is considered equivalent to

* a ** c *** d ** b

I'm using Ubuntu Linux, and the software should come with no money paid.

Answer 1

Better than nothing partial answer. This method can return a false positive, (see notes at end), but not a false negative, (i.e. negative results are reliable).

tsort is useful util that does topological sorting from standard input. tsort requires node paired input, so that this:

* a
** b
** c
*** d

Must first be reformatted for tsort to look like this:

a b
a c
c d

Pipe that through tsort:

printf '%s %s\n' a b  a c  c d | sort | tsort

Output:

a
c
b
d

Using bash and diff, the two trees in the question can be compared like so:

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)

Output is nothing, since the two trees are equal.

---

Notes:

• the tsort docs need improvement.

• Negative results, (the trees are different), are reliable. Positive results, (the trees are the same), might not be. Some graphs (all trees are graphs) that are different can still have the same sort result. But if diff does return something, the trees are absolutely not equal.

  Example of false positive, consider the two trees:

  +---+
  | a |
  +---+
    |
    |
    v
  +---+
  | b |
  +---+
    |
    |
    v
  +---+
  | c |
  +---+
  

  and:

  +---+     +---+
  | c | <-- | a |
  +---+     +---+
              |
              |
              v
            +---+
            | b |
            +---+
  

  Put those trees into tsort:

  paste <(printf '%s %s\n' a b  a c | sort | tsort)  \
        <(printf '%s %s\n' a c  c b | sort | tsort)
  

  Output:

  a       a
  c       c
  b       b