How can I remove a node from a graph in a schematic?
I defined a graph that has the following structure "(() () ...) The outer list is the graph itself, it contains nodes and edges. The first inner list is a list of all nodes. The edges are listed below. The edges are made up of pairs of nodes. So here's an example of a graph with three nodes and two edges: ((n1 n2 n3) (n1 n2) (n1 n3))
I was able to remove the edge like so:
(define (delete-edge edge)
(if (member edge (edges))
(build-graph (nodes) (remove edge (edges)))
"ERROR no edge to remove"))
And this is build-graph
(define (build-graph nodes edges)
(set! graph (append (list nodes) edges)))
but I am having trouble deleting nodes. If I remove a node, I also have to remove all edges associated with it. What I have so far:
(define (delete-node node)
(cond ((member (car (car graph)) (cdr graph))
("not implemented yet"))
("No Node to delete")))
I'm not sure what the next step is, after I checked if the first node is contained in the edge lists. I know if it is contained, I need to go through and delete the lists that contain it. Then I need to go to the next node in the node list and check it ... But I'm not sure how to do this.
Any help would be greatly appreciated!
source to share
In the diagram, you should prefer functional solutions to the programming style. In other words: it doesn't matter to mutate the global variable ( graph
in this case), it's better to get the graph as a parameter and return the new modified graph with the result. For example, this solves your problem:
(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))))
The above example uses the list helper functions to implement the solution, which is the idiomatic way of writing procedures. Please note: if we try to delete a nonexistent node, then the same input graph will be returned, unmodified. Use it like this:
(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))
If you definitely need to change the global variable graph
, follow these steps:
(set! graph (delete-node 'n2 graph))
source to share