方案 - 使用列表列表

Question

目前我正在处理一个方案问题，其中我们正在使用方案列表表示一个图。我们使用的第一个变体是表示为

的边列表图

'((x y) (y z) (x z))

我们正在使用的图的第二个变体被称为 x 图，表示为

((x (y z)) (y (z)) (z ()))

我们的任务是编写两个程序以将每种形式转换为另一种形式，但我不知道如何解决这个问题。我了解公式的一般概念，捕获一个节点并构建一个列表或基于边缘进行解构，但我不明白应该如何构建列表。寻找一些指导而不是答案。

如果我描述得不够好，我会在这里发布问题以进一步澄清。

考虑将图表示为 Scheme 列表的两种技术。我们可以将有向图表示为边列表。我们称这种表示为 el-graph(即边列表图)。边本身是一个长度为 2 的列表，第一个元素是表示边源的符号，第二个元素是表示边目标的符号。请注意，边是一个列表(不仅仅是一对)。例如，下面是一个图形:'((x y) (y z) (x z))。我们还可以表示类似于邻接矩阵的图形。我们称这种表示为 x 图(即矩阵图)。在这种情况下，图是邻接列表，其中邻接是长度为 2 的列表，使得第一个元素是节点(符号)，第二个元素是该节点的目标列表。例如下面是一个图:'((x(yz))(y(z))(z())).

Write function (el-graph->x-graph g), that accepts an el-graph g and returns an x-graph of g.
Write function (x-graph->el-graph g), that accepts an x-graph g and returns an el-graph of g.

Answer 1

下面的代码片段是实际的答案，但我已尽最大努力实际解释正在做什么，这样您就可以忽略代码并编写自己的东西，如果您愿意的话。

从 x 图转换为边列表图很简单。考虑您的示例:((x (y z)) (y (z)) (z ()))。当你进入第一个子列表时，你想要生成 ((x y) (x z));当你进入第二个子列表时，你想要生成 ((y z));当您进入第三个子列表时，您想要生成 ()。然后，您可以使用 append-map 将所有这些结果平面映射到一个列表中。

(define (x-graph->el-graph g)
  (append-map (lambda (sublist)
                (define from-node (car sublist))
                (define to-nodes (cadr sublist))
                (map (lambda (to-node)
                       (list from-node to-node))
                     to-nodes))
              g))

---

使用 group-by 按起始节点对边进行分组，然后收集每组中的终止节点，可能最容易从边列表图转到 x 图。但是，这不会为您提供空的 z 关联(我将把它留给您作为练习)。

(define (el-graph->x-graph g)
  (map (lambda (group)
         (list (caar group) (map cadr group)))
       (group-by car g eq?)))