extra/graph-theory/sparse/sparse.factor

   1 ! Copyright (C) 2008 William Schlieper <schlieper@unc.edu>
   2 ! See http://factorcode.org/license.txt for BSD license.
   3
   4 USING: accessors kernel sequences arrays vectors sets assocs hashtables graph-theory namespaces fry ;
   5
   6 IN: graph-theory.sparse
   7
   8 TUPLE: sparse-graph alist ;
   9
  10 : <sparse-graph> ( -- sparse-graph )
  11     H{ } clone sparse-graph boa ;
  12
  13 : >sparse-graph ( graph -- sparse-graph )
  14     [ vertices ] keep
  15     '[ dup _ adjlist 2array ] map >hashtable sparse-graph boa ;
  16
  17 INSTANCE: sparse-graph graph
  18
  19 M: sparse-graph vertices
  20     alist>> keys ;
  21
  22 M: sparse-graph adjlist
  23     alist>> at ;
  24
  25 M: sparse-graph add-blank-vertex
  26     alist>> V{ } clone -rot set-at ;
  27
  28 M: sparse-graph delete-blank-vertex
  29     alist>> delete-at ;
  30
  31 M: sparse-graph add-edge*
  32     alist>> swapd at adjoin ;
  33
  34 M: sparse-graph delete-edge*
  35     alist>> swapd at delete ;