Tree-Memory-Sort

基于群论的内存储拓扑排序算法

设计

此算法直接在存储节点的数组上执行内存交换。由于交换操作满足群论公理，可以使用群生成器来提高拓扑排序的效率。

群生成器是一个数组，存储每个节点索引的索引。当在数组而不是数据上执行交换操作时，可以在不改变当前节点索引意义的情况下预测节点在解中的存储位置。

一旦找到解，可以使用群生成器来重溯排序树所需的交换操作。

重溯交换操作的顺序可能与求解阶段不同

`a, b, c` => `a, (c, b)` => `(c, a), b` => `c, a, b` (solving phase)
`c, a, b` => `(b), a, (c)` => `(a, b), c` => `a, b, c` (retrace phase)

素数示例

此示例展示了算法如何使用一些简单的数字工作。

假设你有两个方程

   12 = 2 * 6
   6 = 3 * 2

如果你将这些方程作为树来排列，你将自然从顶部开始 12 并以与方程中相同的顺序列出每个节点的子节点。

当使用自动定理证明器以这种方式重写树时，可能会变得混乱。一些算法依赖于有序的树来有效地执行。

通过在树上执行拓扑排序，可以将它恢复到有序形式

    Tree            i       i'
    --------------------------
    12              3   =>  0
    |- 2            2   =>  1
    |- 6            1   =>  2
       |- 3         4   =>  3
       |- 2         0   =>  4

该算法不会改变树内的相对连接，只是改变节点在内存中的存储方式。然而，它需要更改索引，以便它们指向正确的节点。

源代码

extern crate tree_mem_sort;

use tree_mem_sort::sort;

#[derive(Debug)]
pub struct Number {
    /// The value of the number.
    pub value: u32,
    /// Which number this was factored from.
    pub parent: Option<usize>,
    /// Prime factors.
    pub children: Vec<usize>,
}

fn main() {
    let mut nodes = vec![
        Number {
            value: 2,
            parent: Some(1),
            children: vec![],
        }, // 0
        Number {
            value: 6,
            parent: Some(0),
            children: vec![4, 0],
        }, // 1
        Number {
            value: 2,
            parent: Some(2),
            children: vec![],
        }, // 2
        Number {
            value: 12,
            parent: None,
            children: vec![2, 1],
        }, // 3
        Number {
            value: 3,
            parent: Some(2),
            children: vec![],
        }, // 4
    ];
    for i in 0..nodes.len() {
        println!("{}: {:?}", i, nodes[i]);
    }
    // Prints `[2, 6, 2, 12, 3]`
    println!("{:?}", nodes.iter().map(|n| n.value).collect::<Vec<u32>>());

    sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
    println!("");
    for i in 0..nodes.len() {
        println!("{}: {:?}", i, nodes[i]);
    }
    // Prints `[12, 2, 6, 3, 2]`
    println!("{:?}", nodes.iter().map(|n| n.value).collect::<Vec<u32>>());
}

限制

sort 算法假设每个节点最多被一个父节点引用。如果你在父节点之间共享节点，算法可能会进入无限循环。

可以使用 sort_dag 对具有多个父节点的树进行排序。为了使算法与共享节点一起工作，树必须是有向无环图（DAG）。如果树不是 DAG，算法将进入无限循环。

为什么在树上进行拓扑排序？为什么不使用 DAG 表示法？

目标是保留以下属性，并在其他情况下尽量减少工作量

• 每个子节点都大于其父节点
• 每个兄弟节点都大于前面的兄弟节点

拓扑排序通常与有向无环图（DAG）相关，而不是树。此算法适用于DAG，但不适用于所有具有共享节点的树。

• 如果每个节点最多只有一个父节点，则它自动是DAG
• 具有有序子节点的树编码了兄弟之间的箭头，这会影响它是否是DAG

例如，以下具有共享节点的树不是DAG

A
|- B
   |- D
   |- C
|- C
   |- D

请注意，B在D之前排序C，因此D小于C。然而，由于D是C的子节点，它必须大于C。这导致矛盾。

如果您尝试使用sort_dag对上述树进行排序，它将进入无限循环。

树易于推理，并且对此库的常见用法具有更有效的编码。对于N个子节点，等效DAG的箭头至少需要N个箭头。此外，这些箭头必须以某种方式排列，使子节点成为全序。这是为了确定每一对子节点的顺序。通过使用有序子节点的树，箭头的内存需求为零，因为子节点无论如何都存储在数组中。

对无共享节点的树进行左子节点优先遍历可以用来生成拓扑排序。但是，从树遍历中构建索引会使所有右子节点的索引都大于左子节点的索引。这会使节点移动超过预期。

对于森林，树遍历也需要对所有节点进行额外的一次遍历。在这里，排序树的算法无需修改即可适用于森林。

树的拓扑排序具有以下性质：如果您在存储节点的数组末尾推送一个新节点，其父节点是任何现有节点，则新的树是拓扑排序的。这对于从树遍历构建的索引不成立。