Reinforcement Learning and
Artificial
Intelligence (RLAI) 

tinycrystal project part 1: elementary graph operations 
Implement in scheme the following seven graph operations, with these names:
(makenonterminalvertex) >
a new nonterminal vertex with no edges in or out(nonterminalvertex? object)
> #f
/other; was 'object' made by makenonterminalvertex
?(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(setsucc! v l object)
> object
; creates or replaces edge (v,l
) to point to an arbitrary scheme object; returns the object(deledge! 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 associationlist procedures in preference to the assq
ones.
You might want to define utility functions assocset!
and assocremove!
. 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 (makenonterminalvertex))
(setsucc! h 'x 5)
5
(setsucc! h 'y 8)
8
(setsucc! h 'y 7)
7
(setsucc! h 'z 9)
9
(labels h)
(x z y) or equivalent
(succ h 'x)
5
(succ h 'y)
7
(deledge! 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 (makenonterminalvertex))
(setsucc! h 'v v)
(setsucc! (succ h 'v) 'x 3)
3
(eq? (succ h 'v) v)
(succ v 'x)
3
(setsucc! h '(1 2 3 4) 13)
(succ h '(1 2 3 4))
13
(succ h 'w)
error
(nonterminalvertex? (succ h 'v))
true
#