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