如何在Scheme中从图中删除一个节点？

Question

我定义了一个具有以下结构的图形： '(()()...) 外部列表是图本身，它包含节点和边。 第一个内部列表是所有节点的列表。 接下来的列表是边。边由一对节点组成。 因此，这里是一个具有3个节点和2个边的示例图： ((n1 n2 n3) (n1 n2) (n1 n3))

我已经能够像这样删除一条边：

(define (delete-edge edge)
    (if (member edge (edges))
        (build-graph (nodes) (remove edge (edges)))
        "ERROR no edge to remove"))

这是“build-graph”

(define (build-graph nodes edges)
    (set! graph (append (list nodes) edges)))

但我在删除节点时遇到了问题。如果我删除一个节点，我还必须删除所有与它相关的边。我目前所做的是:

(define (delete-node node)
    (cond ((member (car (car graph)) (cdr graph))
           ("not implemented yet"))
        ("No Node to delete")))

我不确定在检查第一个节点是否包含在边缘列表后下一步是什么。如果它被包含，我知道需要遍历并删除包含它的列表。然后我需要转到节点列表中的下一个节点并检查...但我不确定如何做到这一点。

任何帮助都将不胜感激！

- Sarah

Answer 1

在Scheme中，您应该优先使用函数式编程风格的解决方案。换句话说：改变全局变量（本例中的graph）不是一个好主意，最好将图形作为参数接收，并返回一个新的修改后的图形和结果。例如，以下代码可以解决您的问题：

(define (delete-node node graph)
  (cons (remove node (car graph))                  ; remove node from list of nodes
        (filter (lambda (e) (not (member node e))) ; delete edges that contain the node
                (cdr graph))))

上述代码使用了列表辅助函数来实现解决方案，这是编写过程的惯用方法。请注意，如果我们尝试删除一个不存在的节点，则会返回未修改的相同输入图。使用方式如下：

(define graph '((n1 n2 n3) (n1 n2) (n1 n3)))

(delete-node 'n2 graph)
=> '((n1 n3) (n1 n3))
(delete-node 'n5 graph)
=> '((n1 n2 n3) (n1 n2) (n1 n3))

如果你一定需要修改全局变量graph，请在之后进行操作：

(set! graph (delete-node 'n2 graph))

- Óscar López

---

抱歉，delete-node是一个设计在使用dispatch的函数内部的函数。我正在创建一个图形对象，并实现包含在图形中的方法——否则我会同意你的观点。 - Sarah

但是感谢您的帮助！这正是我一直在寻找的。我一直为如何解决这个问题而烦恼不已。 - Sarah