RLAI Reinforcement Learning and Artificial Intelligence (RLAI)

tiny-crystal project part 1: elementary graph operations

[The examples were reworked to give clearer test cases with answers on Nov 26]

Implement an abstract interface for constructing, editing, and examining a graph. This part could be totally independent of how the graph will be used in crystal.

Implement in scheme the following seven graph operations, with these names:

  1. (make-nonterminal-vertex) --> a new nonterminal vertex with no edges in or out
  2. (nonterminal-vertex? object) --> #f/other; was 'object' made by make-nonterminal-vertex?
  3. (edge? v l) --> #f/other; is there an edge from v with label l?
  4. (succ v l) --> successor vertex of the edge from v with label l; error if no such edge
  5. (set-succ! v l object) --> object; creates or replaces edge (v,l) to point to an arbitrary scheme object; returns the object
  6. (del-edge! v l) --> void; remove edge from v with label l; error if no such edge
  7. (labels v) --> list of v's outgoing labels; order doesn't matter

In 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
|#

Extend this Page   How to edit   Style   Subscribe   Notify   Suggest   Help   This open web page hosted at the University of Alberta.   Terms of use  713/0