Changeset 27208 in project


Ignore:
Timestamp:
08/06/12 08:35:15 (9 years ago)
Author:
Ivan Raikov
Message:

digraph: added terminals message to digraph object

Location:
release/4/digraph/trunk
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • release/4/digraph/trunk/digraph.scm

    r24476 r27208  
    232232                                                 #f))
    233233                                           (get-nodes))))
     234        ((terminals)         (lambda ()
     235                               (filter-map (lambda (n)
     236                                             (if (null?
     237                                                  ;; check only edges to other nodes
     238                                                  (remove (o (cut fx= <> (car n)) cadr)
     239                                                          (out-edges (car n))))
     240                                                 (car n)
     241                                                 #f))
     242                                           (get-nodes))))
    234243        ((debug)             (list (cons nodes (dynvector->list nodes))
    235244                                   (cons succ (dynvector->list succ))
  • release/4/digraph/trunk/digraph.setup

    r24476 r27208  
    1616
    1717  ; Assoc list with properties for your extension:
    18   `((version 1.15)
     18  `((version 1.16)
    1919    ))
    2020
  • release/4/digraph/trunk/tests/run.scm

    r24476 r27208  
    4949  (let ((g (make-digraph 'depgraph "dependency graph")))
    5050
    51   ;; add the nodes to the graph
     51    ;; add the nodes to the graph
    5252    (for-each (lambda (i n) ((g 'add-node!) i n))
    5353              node-ids node-list)
     54   
     55    (pp ((g 'nodes)))
    5456
    55   ;; make sure all nodes got inserted
    56   (test "add nodes to the graph"
    57    ((g 'nodes))
    58    '((14 killerapp)
    59      (13 libzigzag_a) (12 zag_o) (11 zag_cpp)
    60      (10 zig_o) (9 zig_cpp) (8 libfoobar_a) (7 bar_o)
    61      (6 bar_cpp) (5 foo_o) (4 foo_cpp) (3 zow_h) (2 boz_h)
    62      (1 yow_h) (0 dax_h)))
     57    ;; make sure all nodes got inserted
     58    (test "add nodes to the graph"
     59          ((g 'nodes))
     60          '((14 killerapp)
     61            (13 libzigzag_a) (12 zag_o) (11 zag_cpp)
     62            (10 zig_o) (9 zig_cpp) (8 libfoobar_a) (7 bar_o)
     63            (6 bar_cpp) (5 foo_o) (4 foo_cpp) (3 zow_h) (2 boz_h)
     64            (1 yow_h) (0 dax_h)))
     65   
     66    ;; add the edges to the graph
     67    (for-each (lambda (e)
     68                (let* ((ni (car e))
     69                       (nj (cdr e))
     70                       (i (car (alist-ref ni node-map)))
     71                       (j (car (alist-ref nj node-map))))
     72                  ((g 'add-edge!) (list i j (format "~A->~A" ni nj)))))
     73              used-by)
     74   
     75    ;; make sure all edges got correctly created
     76    (test "add edges to the graph"
     77          ((g 'edges))
     78          '((13 14 "libzigzag_a->killerapp") (12 13 "zag_o->libzigzag_a")
     79            (11 12 "zag_cpp->zag_o") (10 13 "zig_o->libzigzag_a")
     80            (9 10 "zig_cpp->zig_o") (8 13 "libfoobar_a->libzigzag_a")
     81            (7 8 "bar_o->libfoobar_a") (6 7 "bar_cpp->bar_o")
     82            (5 8 "foo_o->libfoobar_a") (4 5 "foo_cpp->foo_o")
     83            (3 4 "zow_h->foo_cpp") (2 11 "boz_h->zag_cpp")
     84            (2 9 "boz_h->zig_cpp") (2 6 "boz_h->bar_cpp")
     85            (1 11 "yow_h->zag_cpp") (1 6 "yow_h->bar_cpp")
     86            (0 1 "dax_h->yow_h") (0 6 "dax_h->bar_cpp") (0 4 "dax_h->foo_cpp")))
    6387
    64   ;; add the edges to the graph
    65   (for-each (lambda (e)
    66               (let* ((ni (car e))
    67                      (nj (cdr e))
    68                      (i (car (alist-ref ni node-map)))
    69                      (j (car (alist-ref nj node-map))))
    70                 ((g 'add-edge!) (list i j (format "~A->~A" ni nj)))))
    71             used-by)
     88    ;; check roots and terminals
     89    (test "roots"
     90          ((g 'roots))
     91          '(3 2 0))
    7292
    73    ;; make sure all edges got correctly created
    74    (test "add edges to the graph"
    75     ((g 'edges))
    76     '((13 14 "libzigzag_a->killerapp") (12 13 "zag_o->libzigzag_a")
    77       (11 12 "zag_cpp->zag_o") (10 13 "zig_o->libzigzag_a")
    78       (9 10 "zig_cpp->zig_o") (8 13 "libfoobar_a->libzigzag_a")
    79       (7 8 "bar_o->libfoobar_a") (6 7 "bar_cpp->bar_o")
    80       (5 8 "foo_o->libfoobar_a") (4 5 "foo_cpp->foo_o")
    81       (3 4 "zow_h->foo_cpp") (2 11 "boz_h->zag_cpp")
    82       (2 9 "boz_h->zig_cpp") (2 6 "boz_h->bar_cpp")
    83       (1 11 "yow_h->zag_cpp") (1 6 "yow_h->bar_cpp")
    84       (0 1 "dax_h->yow_h") (0 6 "dax_h->bar_cpp") (0 4 "dax_h->foo_cpp")))
     93    (test "terminals"
     94          ((g 'terminals))
     95          '(14))
     96   
     97    ;; remove node 0 from graph
     98    ((g 'remove-node!) 0)
     99   
     100    ;; make sure node 0 got removed
     101    (test "remove node 0"
     102          ((g 'nodes))
     103          '((14 killerapp) (13 libzigzag_a) (12 zag_o)
     104            (11 zag_cpp) (10 zig_o) (9 zig_cpp) (8 libfoobar_a)
     105            (7 bar_o) (6 bar_cpp) (5 foo_o) (4 foo_cpp) (3 zow_h)
     106            (2 boz_h) (1 yow_h)))
     107   
     108    ;; make sure the edges of node 0 got removed
     109    (test "make sure node 0 edges got removed"
     110          ((g 'edges))
     111          '((13 14 "libzigzag_a->killerapp") (12 13 "zag_o->libzigzag_a")
     112            (11 12 "zag_cpp->zag_o") (10 13 "zig_o->libzigzag_a")
     113            (9 10 "zig_cpp->zig_o") (8 13 "libfoobar_a->libzigzag_a")
     114            (7 8 "bar_o->libfoobar_a") (6 7 "bar_cpp->bar_o")
     115            (5 8 "foo_o->libfoobar_a") (4 5 "foo_cpp->foo_o")
     116            (3 4 "zow_h->foo_cpp") (2 11 "boz_h->zag_cpp")
     117            (2 9 "boz_h->zig_cpp") (2 6 "boz_h->bar_cpp")
     118            (1 11 "yow_h->zag_cpp") (1 6 "yow_h->bar_cpp")))
     119   
     120    ;; remove node 2 from graph
     121    ((g 'remove-node!) 2)
     122   
     123    ;; make sure node 2 got removed
     124    (test "remove node 2"
     125          ((g 'nodes))
     126          '((14 killerapp) (13 libzigzag_a) (12 zag_o)
     127            (11 zag_cpp) (10 zig_o) (9 zig_cpp) (8 libfoobar_a)
     128            (7 bar_o) (6 bar_cpp) (5 foo_o) (4 foo_cpp) (3 zow_h) (1 yow_h)))
     129   
     130    ;; make sure the edges of node 2 got removed
     131    (test "make sure node 2 edges got removed"
     132          ((g 'edges))
     133          '((13 14 "libzigzag_a->killerapp") (12 13 "zag_o->libzigzag_a")
     134            (11 12 "zag_cpp->zag_o") (10 13 "zig_o->libzigzag_a")
     135            (9 10 "zig_cpp->zig_o") (8 13 "libfoobar_a->libzigzag_a")
     136            (7 8 "bar_o->libfoobar_a") (6 7 "bar_cpp->bar_o")
     137            (5 8 "foo_o->libfoobar_a") (4 5 "foo_cpp->foo_o")
     138            (3 4 "zow_h->foo_cpp") (1 11 "yow_h->zag_cpp")
     139            (1 6 "yow_h->bar_cpp")))
     140   
    85141
    86     ;; remove node 0 from graph
    87    ((g 'remove-node!) 0)
    88 
    89    ;; make sure node 0 got removed
    90    (test "remove node 0"
    91     ((g 'nodes))
    92     '((14 killerapp) (13 libzigzag_a) (12 zag_o)
    93       (11 zag_cpp) (10 zig_o) (9 zig_cpp) (8 libfoobar_a)
    94       (7 bar_o) (6 bar_cpp) (5 foo_o) (4 foo_cpp) (3 zow_h)
    95       (2 boz_h) (1 yow_h)))
    96 
    97     ;; make sure the edges of node 0 got removed
    98    (test "make sure node 0 edges got removed"
    99     ((g 'edges))
    100     '((13 14 "libzigzag_a->killerapp") (12 13 "zag_o->libzigzag_a")
    101       (11 12 "zag_cpp->zag_o") (10 13 "zig_o->libzigzag_a")
    102       (9 10 "zig_cpp->zig_o") (8 13 "libfoobar_a->libzigzag_a")
    103       (7 8 "bar_o->libfoobar_a") (6 7 "bar_cpp->bar_o")
    104       (5 8 "foo_o->libfoobar_a") (4 5 "foo_cpp->foo_o")
    105       (3 4 "zow_h->foo_cpp") (2 11 "boz_h->zag_cpp")
    106       (2 9 "boz_h->zig_cpp") (2 6 "boz_h->bar_cpp")
    107       (1 11 "yow_h->zag_cpp") (1 6 "yow_h->bar_cpp")))
    108 
    109     ;; remove node 2 from graph
    110    ((g 'remove-node!) 2)
    111 
    112    ;; make sure node 2 got removed
    113    (test "remove node 2"
    114     ((g 'nodes))
    115     '((14 killerapp) (13 libzigzag_a) (12 zag_o)
    116       (11 zag_cpp) (10 zig_o) (9 zig_cpp) (8 libfoobar_a)
    117       (7 bar_o) (6 bar_cpp) (5 foo_o) (4 foo_cpp) (3 zow_h) (1 yow_h)))
    118 
    119    ;; make sure the edges of node 2 got removed
    120    (test "make sure node 2 edges got removed"
    121     ((g 'edges))
    122     '((13 14 "libzigzag_a->killerapp") (12 13 "zag_o->libzigzag_a")
    123       (11 12 "zag_cpp->zag_o") (10 13 "zig_o->libzigzag_a")
    124       (9 10 "zig_cpp->zig_o") (8 13 "libfoobar_a->libzigzag_a")
    125       (7 8 "bar_o->libfoobar_a") (6 7 "bar_cpp->bar_o")
    126       (5 8 "foo_o->libfoobar_a") (4 5 "foo_cpp->foo_o")
    127       (3 4 "zow_h->foo_cpp") (1 11 "yow_h->zag_cpp")
    128       (1 6 "yow_h->bar_cpp")))
    129142  ))
    130143 
Note: See TracChangeset for help on using the changeset viewer.