graph - 如何从方案中的图中删除节点？

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"))

这是构建图

(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")))

在检查第一个节点是否包含在边列表中之后，我不确定下一步是什么。我知道它是否包含在内，我需要检查并删除包含它的列表。然后我需要转到节点列表中的下一个节点并检查...但我不确定如何执行此操作。

如有任何帮助，我们将不胜感激!

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))