2

我最近购买了 Joseph Felsenstein 的《推断系统发育》，这是一本关于推断系统发育树的数学和计算方法的好书，并且一直在尝试实现它所描述的一些算法。

具体来说，我有兴趣在具有持久性数据结构的功能设置中这样做，因为许多方法都涉及遍历可能的树空间，并且通过结构来廉价地记住我们去过的地方的历史会很好共享（这是 aphyr 在这篇博文中对“世界”所做的事情）、轻松缓存先前计算的子树值等。

这样做的问题是，很多方法都涉及“重新生根”树，我无法弄清楚如何以纯粹的功能方式廉价地做到这一点。基本上我需要一些方法来捕捉以下每一个的想法（使用 clojure 表示法，将树表示为向量）：

[:a [:b [:c :d]]] 
[:b [:a [:c :d]]]
[:a [:b [:d :c]]]
[:b [:a [:d :c]]]
[[:a :b] [:c :d]] 
[[:c :d] [:a :b]]
[:c [:d [:a :b]]]
[:d [:c [:a :b]]]
[:c [:d [:b :a]]]
[:d [:c [:b :a]]]

表示相同的数据，仅在根的位置不同；它们各自代表无根树：

a   b
 \ /
  |
 / \
c   d

我希望能够使用 zipper 导航到其中一棵树，然后调用一个函数reroot，该函数将返回一个新树，该树以这样一种方式压缩，即根位于 current loc。

在书中，Felsenstein 描述了一种用于廉价可重根树的数据结构，它看起来像下面匆忙制作的图表

可怕的图表

其中圆圈是结构，箭头是指针。结构环是树上的内部节点，一旦我们引用了一个，我们可以通过一些指针交换将根移到那里。不幸的是，这是一个变异操作，需要相互引用，这两者在纯函数设置中都是不可能的。

我觉得应该有一种方法可以使用拉链做我想做的事，但我已经玩clojure.core/zip了一段时间了，却一无所获。

有谁知道这样的实现，或者对我应该阅读的东西/我应该看的论文/如何做到这一点的想法有建议？

谢谢！

4

2 回答 2

2

jvm 实际上并没有让我们访问指针，以便我们可以直接操作。但是我们确实有一些选择来表示一个双重链接的结构。

这看起来很像一个图，对于像这样的稀疏图，一个经典的表示是邻接表。邻接表的一个优点是它们通过名称取消引用而不是依赖于指针/对象标识，因此我们可以在结构中表达任意循环或自引用路径，而无需任何突变。

按字母顺序从左到右/从上到下命名您的节点：

{:a [:c]
 :b [:d]
 :c [:a :d :e]
 :d [:b :c :e]
 :e [:c :d :g]
 :f [:h]
 :g [:e :h :i]
 :h [:f :g :i]
 :i [:g :h]}

网络中的元素按名称查找，从该元素出来的箭头由向量表示为关联值。遍历可以实现为递归函数，在每次迭代中查找要步进的节点。“根”只是用于开始遍历的元素（:i在您的图表中）。

由于哈希映射文字是常规的 clojure 持久数据结构，因此可以使用conj、update-in、等进行各种插入/拆分重新排列。assoc

于 2015-02-23T19:07:04.887 回答
1

无根树是具有以下特征的图：

  • 它是对称/无向的——它是它自己的逆。
  • 它是紧密相连的——你可以从任何地方到达任何地方。
  • 回到你原来的地方的唯一方法是追溯你的脚步。

表示图的标准方法是为每个节点提供一组邻居的地图。这就是标准 clojure 图形库所做的，尽管它的操作在很大程度上是冗余的defstruct.

对于您的示例，地图是

{:I #{:a :b :c :d}, :a #{:I}, :b #{:I}, :c #{:I}, :d #{:I}}

当它是它自己的时候，这是一个无向inverse图，其中

(defn inverse [g]
  (apply merge-with clojure.set/union
         (for [[x xs] g, y xs] {y #{x}})))

您无需执行任何操作即可将其植根于任何地方。正如@noisesmith 所说，根只是您开始枚举的节点。从图表来看，费尔森斯坦的数据结构同样如此。

如果如图所示，只有您的内部节点是多重连接的，您可以通过直接从每个外部节点映射到其唯一的邻居来节省一些空间。你的例子会变成

{:I #{:a :b :c :d}, :a :I, :b :I, :c :I, :d :I}

也许更好地表示为两张地图：

{:internals {:I #{:a :b :c :d}}, :externals {:a :I, :b :I, :c :I, :d :I}}
于 2015-02-23T16:11:35.577 回答