Reinforcement Learning and
Artificial
Intelligence (RLAI) |
|
tiny-crystal project part 1: elementary graph operations |
Implement in scheme the following seven graph operations, with these names:
(make-nonterminal-vertex) -->
a new nonterminal vertex with no edges in or out(nonterminal-vertex? object)
--> #f
/other; was 'object' made by make-nonterminal-vertex
?(edge? v l)
-->
#f/other; is there an edge from v
with label l
?(succ v l) -->
successor vertex of the edge from v with label l
; error if no such edge(set-succ! v l object)
--> object
; creates or replaces edge (v,l
) to point to an arbitrary scheme object; returns the object(del-edge! v l) --> void
; remove edge from v with label l
; error if no such edge(labels v)
--> list of v's outgoing labels; order doesn't matterIn all these operations, where the formal parameter v is used, the
argument must be a nonterminal vertex or an error will eventually be
generated.
Hints:
This part should be about 70 lines or less of scheme code.
A nonterminal vertex needs to be an identifiable data structure; you might want to tag it in some way.
An association list is a fine way to hold bindings, such as that between a label and a result vertex. Use the assoc
versions of the association-list procedures in preference to the assq
ones.
You might want to define utility functions assoc-set!
and assoc-remove!
. you can find specifications for them (but not implementations) on the internet.
Here are some error messages you might use:
(error "this object is not a nonterminal vertex:" v)
(error "there is no successor for this edge" v l)
(error "no such key to be removed from the assoc list" key alist)
#|
some testing for elementary graph operations:
(define h (make-nonterminal-vertex))
(set-succ! h 'x 5)
5
(set-succ! h 'y 8)
8
(set-succ! h 'y 7)
7
(set-succ! h 'z 9)
9
(labels h)
(x z y) or equivalent
(succ h 'x)
5
(succ h 'y)
7
(del-edge! h 'x)
(edge? h 'x)
#f
(edge? h 'y)
true
(edge? h 'z)
true
(edge? h 'w)
#f
(labels h)
(z y) or equivalent
(define v (make-nonterminal-vertex))
(set-succ! h 'v v)
(set-succ! (succ h 'v) 'x 3)
3
(eq? (succ h 'v) v)
(succ v 'x)
3
(set-succ! h '(1 2 3 4) 13)
(succ h '(1 2 3 4))
13
(succ h 'w)
error
(nonterminal-vertex? (succ h 'v))
true
|#