v0.401: added experimental lookup() and paths()

svn path=/trunk/externals/moocow/; revision=4946

11 files changed, 665 insertions, 44 deletions

diff --git a/gfsm/configure.in b/gfsm/configure.in
index ea900a0..422a340 100644
--- a/gfsm/configure.in
+++ b/gfsm/configure.in
@@ -4,7 +4,7 @@ AC_PREREQ(2.5)
 
 dnl Some handy macros
 define([THE_PACKAGE_NAME],    [pd-gfsm])
-define([THE_PACKAGE_VERSION], [0.04])
+define([THE_PACKAGE_VERSION], [0.0401])
 define([THE_PACKAGE_AUTHOR],  [moocow@ling.uni-potsdam.de])
 
 AC_INIT(THE_PACKAGE_NAME, THE_PACKAGE_VERSION, THE_PACKAGE_AUTHOR)
diff --git a/gfsm/src/gfsm-help.pd b/gfsm/src/gfsm-help.pd
index c91aa46..ca0aa18 100644
--- a/gfsm/src/gfsm-help.pd
+++ b/gfsm/src/gfsm-help.pd
@@ -1,6 +1,6 @@
-#N canvas 0 0 430 269 10;
+#N canvas 0 0 436 289 10;
 #X obj 66 7 gfsm;
-#X text 126 232 Bryan Jurish <moocow@ling.uni-potsdam.de>;
+#X text 126 241 Bryan Jurish <moocow@ling.uni-potsdam.de>;
 #X text 21 43 EXTERNALS:;
 #X obj 41 72 gfsm_alphabet;
 #X obj 41 98 gfsm_automaton;
@@ -8,8 +8,8 @@
 #X obj 41 124 gfsm_state;
 #X text 161 125 automaton position;
 #X text 160 98 weighted finite state machine;
-#X text 21 184 SEE ALSO:;
-#X text 38 201 gfsmutils(1);
+#X text 21 194 SEE ALSO:;
+#X text 38 211 gfsmutils(1);
 #X text 99 8 : finite state machine external library;
 #X obj 40 150 gfsm_markov;
 #X text 161 151 trainable Markov chain;
diff --git a/gfsm/src/gfsm_automaton-help.pd b/gfsm/src/gfsm_automaton-help.pd
index 10f35ba..52a2bc8 100644
--- a/gfsm/src/gfsm_automaton-help.pd
+++ b/gfsm/src/gfsm_automaton-help.pd
@@ -1,8 +1,8 @@
-#N canvas 126 0 473 476 10;
+#N canvas 126 0 479 520 10;
 #X text 89 7 gfsm_automaton : weighted finite state machine;
-#X text 173 441 Bryan Jurish <moocow@ling.uni-potsdam.de>;
-#X text 7 379 SEE ALSO:;
-#X obj 22 399 gfsm;
+#X text 183 489 Bryan Jurish <moocow@ling.uni-potsdam.de>;
+#X text 7 436 SEE ALSO:;
+#X obj 22 457 gfsm;
 #X text 12 73 INLETS:;
 #X text 30 87 1 - control messages;
 #X text 244 74 OUTLETS:;
@@ -18,7 +18,7 @@ edges are labelled with triples (LO \, HI \, WEIGHT) \, where LO and
 HI are alphabet labels (see gfsm_alphabet) \, and WEIGHT is a floating
 point number.;
 #X obj 265 272 print fsm-help-out;
-#X obj 137 400 gfsm_alphabet;
+#X obj 135 457 gfsm_alphabet;
 #N canvas 192 14 651 458 help-automaton-flags 0;
 #X text 167 4 gfsm_automaton : flags;
 #X msg 22 36 weighted;
@@ -195,8 +195,8 @@ time for large automata.;
 #X connect 18 0 27 0;
 #X connect 30 0 27 0;
 #X connect 34 0 27 0;
-#X restore 21 342 pd help-automaton-algebra;
-#X obj 59 400 gfsm_state;
+#X restore 21 362 pd help-automaton-algebra;
+#X obj 58 457 gfsm_state;
 #X obj 265 230 r fsm-help-in;
 #N canvas 293 117 651 504 help-automaton-access 0;
 #X msg 22 42 size;
@@ -234,7 +234,7 @@ i.e. \, a message such as "root 1E+37" is likely to crash Pd.;
 #X text 242 403 adds an arc from state FROM to state TO on lower (input)
 label LO and upper (output) label HI with weight WEIGHT. states FROM
 and TO are implicitly created.;
-#X msg 26 390 add_arc 0 1 2 3 4;
+#X msg 33 390 add_arc 0 1 2 3 4;
 #X msg 38 412 add_arc 0 2 42 24 0.7;
 #X text 349 480 Bryan Jurish <moocow@ling.uni-potsdam.de>;
 #X connect 0 0 3 0;
@@ -279,10 +279,62 @@ package from at&t.;
 #X connect 18 0 0 0;
 #X connect 20 0 19 0;
 #X restore 20 318 pd help-automaton-draw;
-#X text 239 401 gfsmutils(1);
+#X text 234 457 gfsmutils(1);
 #X obj 265 344 gfsm_automaton fsm-help-2;
 #X text 248 303 PLACEHOLDERS:;
 #X obj 265 323 gfsm_automaton fsm-help;
 #X obj 265 251 gfsm_automaton fsm-help;
+#N canvas 0 0 450 300 help-automaton-properties 0;
+#X msg 15 13 cyclic;
+#X text 89 15 "cyclic" : is the fsm cyclic?;
+#X obj 14 192 s fsm-help-in;
+#X connect 0 0 2 0;
+#X restore 22 340 pd help-automaton-properties;
+#N canvas 448 142 552 352 help-automaton-lookup 0;
+#N canvas 0 0 450 300 lookup_init 0;
+#X obj 22 16 inlet;
+#X msg 22 40 clear \, root 0 \, add_arc 0 0 1 2 0.5 \, add_arc 0 0
+2 1 0.5 \, add_arc 0 1 1 1 0 \, final 0 1 \, final 1 1;
+#X obj 22 76 outlet;
+#X connect 0 0 1 0;
+#X connect 1 0 2 0;
+#X restore 24 54 pd lookup_init;
+#X msg 24 33 bang;
+#X obj 24 232 gfsm_automaton lookup-help;
+#X msg 39 93 lookup fsm-help 1 2;
+#X obj 24 255 print lookup-help-out;
+#N canvas 0 0 450 300 view-automaton 0;
+#X obj 30 16 inlet;
+#X obj 30 60 t b s;
+#X msg 60 85 \; \$1-in draw_dot gfsm_help.dot;
+#X msg 30 133 dotty gfsm_help.dot;
+#X obj 30 154 shell;
+#X obj 30 38 symbol;
+#X connect 0 0 5 0;
+#X connect 1 0 3 0;
+#X connect 1 1 2 0;
+#X connect 3 0 4 0;
+#X connect 5 0 1 0;
+#X restore 326 222 pd view-automaton;
+#X msg 326 177 lookup-help;
+#X msg 326 198 fsm-help;
+#X text 303 145 VIEWING:;
+#X text 321 158 (requires 'graphviz');
+#X obj 38 209 r lookup-help-in;
+#X text 221 92 "lookup RESULT LABELS..." : linear composition;
+#X text 313 108 result = compose(id(labels) \, fsm);
+#X text 243 297 Bryan Jurish <moocow@ling.uni-potsdam.de>;
+#X text 135 -2 gfsm_automaton : lookup;
+#X msg 41 117 lookup fsm-help 1 1 1;
+#X text 137 32 <-- START HERE: create lookup transducer;
+#X connect 0 0 2 0;
+#X connect 1 0 0 0;
+#X connect 2 0 4 0;
+#X connect 3 0 2 0;
+#X connect 6 0 5 0;
+#X connect 7 0 5 0;
+#X connect 10 0 2 0;
+#X connect 15 0 2 0;
+#X restore 22 386 pd help-automaton-lookup;
 #X connect 21 0 28 0;
 #X connect 28 0 14 0;
diff --git a/gfsm/src/gfsm_state-help.pd b/gfsm/src/gfsm_state-help.pd
index e26ace2..b798c0a 100644
--- a/gfsm/src/gfsm_state-help.pd
+++ b/gfsm/src/gfsm_state-help.pd
@@ -24,8 +24,8 @@
 #X msg 58 239 degree;
 #X text 137 240 "degree" : get number of outgoing arcs (linear time)
 ;
-#X msg 58 295 arc_first;
-#X msg 58 317 arc_next;
+#X msg 61 295 arc_first;
+#X msg 61 317 arc_next;
 #X msg 59 382 arc_reset;
 #X obj 26 508 gfsm_state fsm-help 0;
 #X text 229 398 arcs are output as a list:;
@@ -42,6 +42,8 @@ first);
 ID;
 #X text 416 463 with labels LO:HI;
 #X text 271 479 (implicitly resets arc iterator);
+#X msg 59 263 cyclic;
+#X text 141 263 "cyclic" : does this state lead to any cycles?;
 #X connect 12 0 25 0;
 #X connect 15 0 25 0;
 #X connect 16 0 25 0;
@@ -53,3 +55,4 @@ ID;
 #X connect 25 0 11 0;
 #X connect 29 0 25 0;
 #X connect 34 0 25 0;
+#X connect 38 0 25 0;
diff --git a/gfsm/src/pd_automaton.c b/gfsm/src/pd_automaton.c
index 47ce4cd..bfcd7e9 100644
--- a/gfsm/src/pd_automaton.c
+++ b/gfsm/src/pd_automaton.c
@@ -3,7 +3,7 @@
  * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
  * Description: finite state automata for Pd
  *
- * Copyright (c) 2004 Bryan Jurish.
+ * Copyright (c) 2004-2006 Bryan Jurish.
  *
  * For information on usage and redistribution, and for a DISCLAIMER OF ALL
  * WARRANTIES, see the file, "LICENSE.txt," in this distribution.
@@ -44,6 +44,8 @@
 static t_class *pd_gfsm_automaton_pd_class;
 static t_class *pd_gfsm_automaton_obj_class;
 
+#define PD_GFSM_AUTOMATON_OBJ_DEFAULT_LABELS_LENGTH 32
+
 /*=====================================================================
  * pd_gfsm_automaton_pd: Methods
  *=====================================================================*/
@@ -150,7 +152,7 @@ void pd_gfsm_automaton_obj_outlet_symbol(t_pd_gfsm_automaton_obj *x, t_symbol *s
 }
 
 /*--------------------------------------------------------------------
- * Utilties: pd_gfsm_automaton_obj: outlet_symbol()
+ * Utilties: pd_gfsm_automaton_obj: outlet_symbol_float()
  */
 void pd_gfsm_automaton_obj_outlet_symbol_float(t_pd_gfsm_automaton_obj *x, t_symbol *sel, t_symbol *sym, t_float f)
 {
@@ -187,6 +189,28 @@ void pd_gfsm_automaton_obj_outlet_bang(t_pd_gfsm_automaton_obj *x, t_symbol *sel
   outlet_anything(x->x_valout, sel, 1, x->x_argv);
 }
 
+/*--------------------------------------------------------------------
+ * Utilties: pd_gfsm_automaton_obj: outlet_labels()
+ */
+void pd_gfsm_automaton_obj_outlet_labels(t_pd_gfsm_automaton_obj *x, t_symbol *sel, gfsmLabelVector *labs)
+{
+
+  if (labs->len > 0) {
+    int i;
+    if (x->x_argc < labs->len) {
+      size_t newsize = labs->len * sizeof(t_atom);
+      x->x_argv = resizebytes(x->x_argv, x->x_argc*sizeof(t_atom), newsize);
+      x->x_argc = labs->len;
+    }
+    for (i=0; i < labs->len; i++) {
+      SETFLOAT(x->x_argv+i, (gfsmLabelVal)g_ptr_array_index(labs,i));
+    }
+    outlet_anything(x->x_valout, sel, labs->len, x->x_argv);
+  } else {
+    SETSYMBOL(x->x_argv, &s_bang);
+    outlet_anything(x->x_valout, sel, 1, x->x_argv);
+  }
+}
 
 
 /*=====================================================================
@@ -211,17 +235,24 @@ static void *pd_gfsm_automaton_obj_new(t_symbol *name)
        x);
 #endif
 
-    //-- defaults
-    //x->x_automaton_pd = NULL;
+  //-- defaults
+  //x->x_automaton_pd = NULL;
+  x->x_labels       = NULL;
+  x->x_paths_s      = NULL;
+  x->x_paths_a      = NULL;
 
-    //-- bindings
-    x->x_automaton_pd = pd_gfsm_automaton_pd_get(name);
-    x->x_automaton_pd->x_refcnt++;
+  //-- bindings
+  x->x_automaton_pd = pd_gfsm_automaton_pd_get(name);
+  x->x_automaton_pd->x_refcnt++;
 
-    //-- outlets
-    x->x_valout = outlet_new(&x->x_obj, &s_anything);  //-- value outlet
+  //-- output buffer
+  x->x_argc = 5;
+  x->x_argv = (t_atom*)getbytes(x->x_argc * sizeof(t_atom));
 
-    return (void *)x;
+  //-- outlets
+  x->x_valout = outlet_new(&x->x_obj, &s_anything);  //-- value outlet
+
+  return (void *)x;
 }
 
 
@@ -235,6 +266,11 @@ static void pd_gfsm_automaton_obj_free(t_pd_gfsm_automaton_obj *x)
 #endif
 
   pd_gfsm_automaton_pd_release(x->x_automaton_pd);
+  if (x->x_labels) g_ptr_array_free(x->x_labels,TRUE);
+  if (x->x_paths_s) gfsm_set_free(x->x_paths_s);
+  if (x->x_paths_a) g_ptr_array_free(x->x_paths_a,TRUE);
+
+  freebytes(x->x_argv, x->x_argc*sizeof(t_atom));
 
   //-- do we need to do this?
   outlet_free(x->x_valout);
@@ -339,6 +375,20 @@ static void pd_gfsm_automaton_obj_semiring(t_pd_gfsm_automaton_obj *x, GIMME_ARG
 }
 
 /*=====================================================================
+ * automaton_obj: automaton properties
+ */
+
+/*--------------------------------------------------------------------
+ * pd_gfsm_automaton_obj: cyclic()
+ */
+static void pd_gfsm_automaton_obj_cyclic(t_pd_gfsm_automaton_obj *x)
+{
+  gboolean rc = gfsm_automaton_is_cyclic(x->x_automaton_pd->x_automaton);
+  pd_gfsm_automaton_obj_outlet_float(x, gensym("cyclic"), (t_float)rc);
+}
+
+
+/*=====================================================================
  * automaton_obj: state properties
  */
 
@@ -643,6 +693,192 @@ static void pd_gfsm_automaton_obj_draw_dot(t_pd_gfsm_automaton_obj *x, GIMME_ARG
   pd_gfsm_automaton_obj_outlet_symbol(x, gensym("draw_dot"), filename);
 }
 
+/*=====================================================================
+ * automaton_obj: lookup
+ */
+
+/*--------------------------------------------------------------------
+ * lookup()
+ *   lookup RESULT LABELS
+ */
+static void pd_gfsm_automaton_obj_lookup(t_pd_gfsm_automaton_obj *x, GIMME_ARGS)
+{
+  if (argc > 1) {
+    guint i;
+    t_pd_gfsm_automaton_pd *result_pd;
+
+    //-- get result automaton
+    result_pd = pd_gfsm_automaton_pd_get(atom_getsymbol(argv));
+    result_pd->x_refcnt++;
+
+    //-- ensure labels exists, is cleared, & is sufficiently allocated
+    if (!x->x_labels) {
+      x->x_labels = g_ptr_array_sized_new(argc-1);
+    } else if (argc > x->x_labels->len) {
+      g_ptr_array_set_size(x->x_labels, argc);
+    }
+    x->x_labels->len = 0;
+
+    //-- get labels
+    for (i=1; i < argc; i++) {
+      gfsmLabelVal lab = atom_getfloat(argv+i);
+      //if (lab==gfsmEpsilon) continue; //-- ignore epsilons (?)
+      g_ptr_array_add(x->x_labels, (gpointer)lab);
+    }
+
+    //-- actual lookup
+    gfsm_automaton_lookup(x->x_automaton_pd->x_automaton,
+			  x->x_labels,
+			  result_pd->x_automaton);
+   
+
+    //-- outlet
+    pd_gfsm_automaton_obj_outlet_symbol(x, sel, result_pd->x_name);
+
+    //-- cleanup
+    pd_gfsm_automaton_pd_release(result_pd);
+  }
+  else {
+    //-- no result automaton specified: complain
+    error("gfsm_automaton: lookup: no result automaton specified!");
+  }
+}
+
+
+/*=====================================================================
+ * automaton_obj: paths
+ */
+
+/*--------------------------------------------------------------------
+ * paths_unsafe()
+ */
+static void pd_gfsm_automaton_obj_paths_unsafe(t_pd_gfsm_automaton_obj *x, GIMME_ARGS)
+{
+  //-- clear set first
+  if (x->x_paths_s) gfsm_set_clear(x->x_paths_s);
+
+  //-- get paths
+  x->x_paths_s = gfsm_automaton_paths(x->x_automaton_pd->x_automaton, x->x_paths_s);
+
+  //-- get array of paths
+  if (!x->x_paths_a) {
+    x->x_paths_a = g_ptr_array_sized_new(gfsm_set_size(x->x_paths_s));
+  } else {
+    g_ptr_array_set_size(x->x_paths_a,0);
+  }
+  gfsm_set_to_ptr_array(x->x_paths_s, x->x_paths_a);
+
+  //-- set path index
+  x->x_paths_i = 0;
+
+  //-- report done
+  pd_gfsm_automaton_obj_outlet_float(x, sel, x->x_paths_a->len);
+}
+
+/*--------------------------------------------------------------------
+ * paths_safe()
+ */
+static void pd_gfsm_automaton_obj_paths_safe(t_pd_gfsm_automaton_obj *x, GIMME_ARGS)
+{
+  gfsmAutomaton *fsm = x->x_automaton_pd->x_automaton;
+
+  if (fsm && gfsm_automaton_is_cyclic(fsm)) {
+    error("gfsm_automaton: paths: automaton is cyclic!");
+    return;
+  } else if (!fsm || !gfsm_automaton_has_state(fsm,fsm->root_id)) {
+    pd_gfsm_automaton_obj_outlet_float(x, sel, 0);
+  } else {
+    pd_gfsm_automaton_obj_paths_unsafe(x,sel, 0,NULL);
+  }
+}
+
+/*--------------------------------------------------------------------
+ * path_first()
+ */
+static void pd_gfsm_automaton_obj_path_first(t_pd_gfsm_automaton_obj *x, GIMME_ARGS)
+{
+  x->x_paths_i = 0;
+  if (x->x_paths_a && x->x_paths_i < x->x_paths_a->len) {
+    pd_gfsm_automaton_obj_outlet_float(x, sel, x->x_paths_i);
+  } else {
+    pd_gfsm_automaton_obj_outlet_float(x, sel, -1);
+  }
+}
+
+/*--------------------------------------------------------------------
+ * path_next()
+ */
+static void pd_gfsm_automaton_obj_path_next(t_pd_gfsm_automaton_obj *x, GIMME_ARGS)
+{
+  if (x->x_paths_a && x->x_paths_i >= 0 && x->x_paths_i+1 < x->x_paths_a->len) {
+    x->x_paths_i++;
+    pd_gfsm_automaton_obj_outlet_float(x, sel, x->x_paths_i);
+  } else {
+    pd_gfsm_automaton_obj_outlet_float(x, sel, -1);
+  }
+}
+
+/*--------------------------------------------------------------------
+ * path_nth()
+ */
+static void pd_gfsm_automaton_obj_path_nth(t_pd_gfsm_automaton_obj *x, GIMME_ARGS)
+{
+  int ni = argc > 0 ? atom_getfloat(argv) : 0;
+  if (x->x_paths_a && ni >= 0 && ni < x->x_paths_a->len) {
+    x->x_paths_i = ni;
+    pd_gfsm_automaton_obj_outlet_float(x, sel, x->x_paths_i);
+  } else {
+    pd_gfsm_automaton_obj_outlet_float(x, sel, -1);
+  }
+}
+
+/*--------------------------------------------------------------------
+ * path_lo()
+ */
+static void pd_gfsm_automaton_obj_path_lo(t_pd_gfsm_automaton_obj *x, GIMME_ARGS)
+{
+  if (x->x_paths_a && x->x_paths_i >= 0 && x->x_paths_i < x->x_paths_a->len) {
+    gfsmPath *p = (gfsmPath*)g_ptr_array_index(x->x_paths_a,x->x_paths_i);
+    pd_gfsm_automaton_obj_outlet_labels(x, sel, p->lo);
+  }
+  else {
+    pd_gfsm_automaton_obj_outlet_bang(x, sel);
+  }
+}
+
+/*--------------------------------------------------------------------
+ * path_hi()
+ */
+static void pd_gfsm_automaton_obj_path_hi(t_pd_gfsm_automaton_obj *x, GIMME_ARGS)
+{
+  if (x->x_paths_a && x->x_paths_i >= 0 && x->x_paths_i < x->x_paths_a->len) {
+    gfsmPath *p = (gfsmPath*)g_ptr_array_index(x->x_paths_a,x->x_paths_i);
+    pd_gfsm_automaton_obj_outlet_labels(x, sel, p->hi);
+  }
+  else {
+    pd_gfsm_automaton_obj_outlet_bang(x, sel);
+  }
+}
+
+/*--------------------------------------------------------------------
+ * path_w()
+ */
+static void pd_gfsm_automaton_obj_path_w(t_pd_gfsm_automaton_obj *x, GIMME_ARGS)
+{
+  if (x->x_paths_a && x->x_paths_i >= 0 && x->x_paths_i < x->x_paths_a->len) {
+    gfsmPath *p = (gfsmPath*)g_ptr_array_index(x->x_paths_a,x->x_paths_i);
+    pd_gfsm_automaton_obj_outlet_float(x, sel, p->w);
+  }
+  else {
+    pd_gfsm_automaton_obj_outlet_bang(x, sel);
+  }
+}
+
+
+/*=====================================================================
+ * automaton_obj: setup
+ */
+
 /*--------------------------------------------------------------------
  * pd_gfsm_automaton_obj: setup()
  */
@@ -691,6 +927,12 @@ static void pd_gfsm_automaton_obj_setup(void)
 		  gensym("clear"),
 		  A_NULL);
 
+  //-- methods: automaton properties
+  class_addmethod(pd_gfsm_automaton_obj_class,
+		  (t_method)pd_gfsm_automaton_obj_cyclic,
+		  gensym("cyclic"),
+		  A_NULL);
+
   //-- methods: state properties
   class_addmethod(pd_gfsm_automaton_obj_class,
 		  (t_method)pd_gfsm_automaton_obj_final,
@@ -745,6 +987,46 @@ static void pd_gfsm_automaton_obj_setup(void)
 		  gensym("draw_dot"),
 		  A_GIMME, A_NULL);
 
+  //-- methods: lookup
+  class_addmethod(pd_gfsm_automaton_obj_class,
+		  (t_method)pd_gfsm_automaton_obj_lookup,
+		  gensym("lookup"),
+		  A_GIMME, A_NULL);
+
+  //-- methods: paths
+  class_addmethod(pd_gfsm_automaton_obj_class,
+		  (t_method)pd_gfsm_automaton_obj_paths_safe,
+		  gensym("paths"),
+		  A_GIMME, A_NULL);
+  class_addmethod(pd_gfsm_automaton_obj_class,
+		  (t_method)pd_gfsm_automaton_obj_paths_unsafe,
+		  gensym("paths_fast"),
+		  A_GIMME, A_NULL);
+  class_addmethod(pd_gfsm_automaton_obj_class,
+		  (t_method)pd_gfsm_automaton_obj_path_first,
+		  gensym("path_first"),
+		  A_GIMME, A_NULL);
+  class_addmethod(pd_gfsm_automaton_obj_class,
+		  (t_method)pd_gfsm_automaton_obj_path_next,
+		  gensym("path_next"),
+		  A_GIMME, A_NULL);
+  class_addmethod(pd_gfsm_automaton_obj_class,
+		  (t_method)pd_gfsm_automaton_obj_path_nth,
+		  gensym("path_nth"),
+		  A_GIMME, A_NULL);
+  class_addmethod(pd_gfsm_automaton_obj_class,
+		  (t_method)pd_gfsm_automaton_obj_path_lo,
+		  gensym("path_lo"),
+		  A_GIMME, A_NULL);
+  class_addmethod(pd_gfsm_automaton_obj_class,
+		  (t_method)pd_gfsm_automaton_obj_path_hi,
+		  gensym("path_hi"),
+		  A_GIMME, A_NULL);
+  class_addmethod(pd_gfsm_automaton_obj_class,
+		  (t_method)pd_gfsm_automaton_obj_path_w,
+		  gensym("path_w"),
+		  A_GIMME, A_NULL);
+
   //-- help symbol
   class_sethelpsymbol(pd_gfsm_automaton_obj_class, gensym("gfsm_automaton-help.pd"));
 }
diff --git a/gfsm/src/pd_automaton.h b/gfsm/src/pd_automaton.h
index ed95954..fcc2646 100644
--- a/gfsm/src/pd_automaton.h
+++ b/gfsm/src/pd_automaton.h
@@ -3,7 +3,7 @@
  * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
  * Description: finite state automata for Pd
  *
- * Copyright (c) 2004 Bryan Jurish.
+ * Copyright (c) 2004-2006 Bryan Jurish.
  *
  * For information on usage and redistribution, and for a DISCLAIMER OF ALL
  * WARRANTIES, see the file, "LICENSE.txt," in this distribution.
@@ -52,8 +52,21 @@ typedef struct _pd_gfsm_automaton_pd
 typedef struct _pd_gfsm_automaton_obj
 {
   t_object                 x_obj;
+
+  //-- underlying automaton
   t_pd_gfsm_automaton_pd  *x_automaton_pd;
-  t_atom                   x_argv[5];
+
+  //-- for lookup()
+  gfsmLabelVector         *x_labels;
+
+  //-- for paths()
+  gfsmSet                 *x_paths_s;
+  GPtrArray               *x_paths_a;
+  guint                    x_paths_i;
+
+  //-- output-related stuff
+  t_int                    x_argc;
+  t_atom                  *x_argv;
   t_outlet                *x_valout;
 } t_pd_gfsm_automaton_obj;
 
diff --git a/gfsm/src/pd_gfsm.c b/gfsm/src/pd_gfsm.c
index 2deb6c8..9f8ad48 100644
--- a/gfsm/src/pd_gfsm.c
+++ b/gfsm/src/pd_gfsm.c
@@ -3,7 +3,7 @@
  * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
  * Description: finite state automata for Pd
  *
- * Copyright (c) 2004 Bryan Jurish.
+ * Copyright (c) 2004-2006 Bryan Jurish.
  *
  * For information on usage and redistribution, and for a DISCLAIMER OF ALL
  * WARRANTIES, see the file, "LICENSE.txt," in this distribution.
diff --git a/gfsm/src/pd_paths.c b/gfsm/src/pd_paths.c
new file mode 100644
index 0000000..c79ed46
--- /dev/null
+++ b/gfsm/src/pd_paths.c
@@ -0,0 +1,186 @@
+/*=============================================================================*\
+ * File: pd_paths.c
+ * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
+ * Description: finite state automata for Pd: paths
+ *
+ * Copyright (c) 2006 Bryan Jurish.
+ *
+ * For information on usage and redistribution, and for a DISCLAIMER OF ALL
+ * WARRANTIES, see the file, "LICENSE.txt," in this distribution.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * See file LICENSE for further informations on licensing terms.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *=============================================================================*/
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <pd_paths.h>
+
+/*=====================================================================
+ * Structures and Types
+ *=====================================================================*/
+static t_class *pd_gfsm_paths_class;
+
+
+/*=====================================================================
+ * pd_gfsm_paths: Methods
+ *=====================================================================*/
+
+/*=====================================================================
+ * Constructors, etc.
+ */
+
+/*--------------------------------------------------------------------
+ * new()
+ */
+static void *pd_gfsm_paths_new(t_symbol *sel, int argc, t_atom *argv)
+{
+  t_symbol *name  = &s_;
+  t_symbol *rname = &s_;
+  t_pd_gfsm_paths *x = (t_pd_gfsm_paths*)pd_new(pd_gfsm_paths_class);
+
+  //-- defaults
+  x->x_automaton_pd = NULL;
+  x->x_result_pd    = NULL;
+  x->x_labels       = g_ptr_array_sized_new(PD_GFSM_PATHS_DEFAULT_LABELS_LENGTH);
+  x->x_labels->len  = 0;
+
+  //-- args
+  if (argc > 0) name  = atom_getsymbolarg(0,argc,argv);
+  if (argc > 1) rname = atom_getsymbolarg(1,argc,argv);
+
+  //-- bindings
+  x->x_automaton_pd = pd_gfsm_automaton_pd_get(name);
+  x->x_automaton_pd->x_refcnt++;
+
+  x->x_result_pd = pd_gfsm_automaton_pd_get(rname);
+  x->x_result_pd->x_refcnt++;
+
+  //-- outlets
+  x->x_valout = outlet_new(&x->x_obj, &s_anything);  //-- value outlet
+
+  return (void *)x;
+}
+
+/*--------------------------------------------------------------------
+ * free
+ */
+static void pd_gfsm_paths_free(t_pd_gfsm_paths *x)
+{
+  pd_gfsm_automaton_pd_release(x->x_automaton_pd);
+  pd_gfsm_automaton_pd_release(x->x_result_pd);
+  g_ptr_array_free(x->x_labels,TRUE);
+
+  //-- do we need to do this?
+  outlet_free(x->x_valout);
+}
+
+/*=====================================================================
+ * Basic Accessors
+ */
+
+/*--------------------------------------------------------------------
+ * automaton
+ */
+static void pd_gfsm_paths_automaton(t_pd_gfsm_paths *x, t_symbol *name)
+{
+  if (name == x->x_automaton_pd->x_name) return;
+  pd_gfsm_automaton_pd_release(x->x_automaton_pd);
+  x->x_automaton_pd = pd_gfsm_automaton_pd_get(name);
+  ++x->x_automaton_pd->x_refcnt;
+}
+
+/*--------------------------------------------------------------------
+ * result
+ */
+static void pd_gfsm_paths_result(t_pd_gfsm_paths *x, t_symbol *rname)
+{
+  if (rname == x->x_result_pd->x_name) return;
+  pd_gfsm_automaton_pd_release(x->x_result_pd);
+  x->x_result_pd = pd_gfsm_automaton_pd_get(rname);
+  ++x->x_result_pd->x_refcnt;
+}
+
+
+/*=====================================================================
+ * Paths
+ */
+static void pd_gfsm_paths_paths(t_pd_gfsm_paths *x, t_symbol *sel, int argc, t_atom *argv)
+{
+  //gfsmAutomaton  *fsm  = x->x_automaton_pd->x_automaton;
+  guint i;
+
+  //-- ensure labels is cleared & sufficiently allocated
+  if (argc > x->x_labels->len) g_ptr_array_set_size(x->x_labels, argc);
+  x->x_labels->len = 0;
+  for (i=0; i < argc; i++) {
+    gfsmLabelVal lab = atom_getfloat(argv+i);
+    //if (lab==gfsmEpsilon) continue; //-- ignore epsilons (?)
+    g_ptr_array_add(x->x_labels, (gpointer)lab);
+  }
+
+  //-- actual paths
+  gfsm_automaton_paths(x->x_automaton_pd->x_automaton,
+			x->x_labels,
+			x->x_result_pd->x_automaton);
+
+  //-- bang: report that we're done
+  outlet_bang(x->x_valout);
+}
+
+
+/*=====================================================================
+ * Setup
+ */
+
+/*--------------------------------------------------------------------
+ * setup()
+ */
+void pd_gfsm_paths_setup(void)
+{
+  //-- class
+  pd_gfsm_paths_class = class_new(gensym("gfsm_paths"),
+				  (t_newmethod)pd_gfsm_paths_new,
+				  (t_method)pd_gfsm_paths_free,
+				  sizeof(t_pd_gfsm_paths),
+				  CLASS_DEFAULT,
+				  A_GIMME, A_NULL);
+
+  //-- methods: automaton, result
+  class_addmethod(pd_gfsm_paths_class,
+		  (t_method)pd_gfsm_paths_automaton,
+		  gensym("automaton"),
+		  A_DEFSYM, A_NULL);
+  class_addmethod(pd_gfsm_paths_class,
+		  (t_method)pd_gfsm_paths_result,
+		  gensym("result"),
+		  A_DEFSYM, A_NULL);
+
+  //-- methods: paths
+  class_addmethod(pd_gfsm_paths_class,
+		  (t_method)pd_gfsm_paths_paths,
+		  gensym("paths"),
+		  A_GIMME, A_NULL);
+  class_addmethod(pd_gfsm_paths_class,
+		  (t_method)pd_gfsm_paths_paths,
+		  &s_list,
+		  A_GIMME, A_NULL);
+
+  //-- help symbol
+  class_sethelpsymbol(pd_gfsm_paths_class, gensym("gfsm_paths-help.pd"));
+}
diff --git a/gfsm/src/pd_paths.h b/gfsm/src/pd_paths.h
new file mode 100644
index 0000000..910882f
--- /dev/null
+++ b/gfsm/src/pd_paths.h
@@ -0,0 +1,58 @@
+/*=============================================================================*\
+ * File: pd_paths.h
+ * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
+ * Description: finite state automata for Pd: paths()
+ *
+ * Copyright (c) 2006 Bryan Jurish.
+ *
+ * For information on usage and redistribution, and for a DISCLAIMER OF ALL
+ * WARRANTIES, see the file, "LICENSE.txt," in this distribution.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * See file LICENSE for further informations on licensing terms.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *=============================================================================*/
+
+/*=====================================================================
+ * Protos
+ *=====================================================================*/
+#ifndef PD_GFSM_PATHS_H
+#define PD_GFSM_PATHS_H
+
+/*----------------------------------------------------------------------
+ * includes
+ */
+#include <pd_automaton.h>
+
+/*--------------------------------------------------------------
+ * pd_gfsm_lookup
+ */
+typedef struct _pd_gfsm_paths
+{
+  t_object                 x_obj;
+  t_pd_gfsm_automaton_pd  *x_automaton_pd;
+  GPtrArray               *x_paths;
+  t_outlet                *x_out_lo;
+  t_outlet                *x_out_hi;
+  t_outlet                *x_out_w;
+  t_outlet                *x_out_done;
+} t_pd_gfsm_lookup;
+
+/*----------------------------------------------------------------------
+ * setup routines
+ */
+void pd_gfsm_paths_setup(void);
+
+#endif /* PD_GFSM_PATHS_H */
diff --git a/gfsm/src/pd_state.c b/gfsm/src/pd_state.c
index b7cd938..63b2e27 100644
--- a/gfsm/src/pd_state.c
+++ b/gfsm/src/pd_state.c
@@ -3,7 +3,7 @@
  * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
  * Description: finite state automata for Pd
  *
- * Copyright (c) 2004 Bryan Jurish.
+ * Copyright (c) 2004-2006 Bryan Jurish.
  *
  * For information on usage and redistribution, and for a DISCLAIMER OF ALL
  * WARRANTIES, see the file, "LICENSE.txt," in this distribution.
@@ -128,15 +128,6 @@ static void pd_gfsm_state_set(t_pd_gfsm_state *x, t_floatarg qf)
   x->x_id   = gfsm_automaton_ensure_state(x->x_automaton_pd->x_automaton, (gfsmStateId)qf);
 }
 
-/*--------------------------------------------------------------------
- * degree
- */
-static void pd_gfsm_state_degree(t_pd_gfsm_state *x)
-{
-  gfsmState *s = gfsm_automaton_find_state(x->x_automaton_pd->x_automaton, x->x_id);
-  SETFLOAT(x->x_argv, (s ? (t_float)gfsm_state_out_degree(s) : 0));
-  outlet_anything(x->x_valout, gensym("degree"), 1, x->x_argv);
-}
 
 /*=====================================================================
  * Navigation
@@ -249,6 +240,39 @@ static void pd_gfsm_state_add_weight(t_pd_gfsm_state *x,
   pd_gfsm_state_arc_reset(x);
 }
 
+/*=====================================================================
+ * Properties
+ */
+
+/*--------------------------------------------------------------------
+ * degree
+ */
+static void pd_gfsm_state_degree(t_pd_gfsm_state *x)
+{
+  gfsmState *s = gfsm_automaton_find_state(x->x_automaton_pd->x_automaton, x->x_id);
+  SETFLOAT(x->x_argv, (s ? (t_float)gfsm_state_out_degree(s) : 0));
+  outlet_anything(x->x_valout, gensym("degree"), 1, x->x_argv);
+}
+
+/*--------------------------------------------------------------------
+ * cyclic()
+ */
+static void pd_gfsm_state_cyclic(t_pd_gfsm_state *x)
+{
+  gfsmAutomaton *fsm = x->x_automaton_pd->x_automaton;
+  gfsmBitVector *visited, *completed;
+  gboolean rc = FALSE;
+
+  if (gfsm_automaton_has_state(fsm,x->x_id)) {
+    visited   = gfsm_bitvector_sized_new(fsm->states->len);
+    completed = gfsm_bitvector_sized_new(fsm->states->len);
+    rc        = gfsm_automaton_is_cyclic_state(fsm, x->x_id, visited, completed);
+    gfsm_bitvector_free(visited);
+    gfsm_bitvector_free(completed);
+  }
+  SETFLOAT(x->x_argv, (t_float)rc);
+  outlet_anything(x->x_valout, gensym("cyclic"), 1, x->x_argv);
+}
 
 
 /*=====================================================================
@@ -280,9 +304,6 @@ void pd_gfsm_state_setup(void)
   class_addmethod(pd_gfsm_state_class, (t_method)pd_gfsm_state_set,
 		  gensym("set"), A_DEFFLOAT, A_NULL);
 
-  //-- methods: degree
-  class_addmethod(pd_gfsm_state_class, (t_method)pd_gfsm_state_degree,
-		  gensym("degree"), A_NULL);
 
   //-- methods: navigation
   class_addmethod(pd_gfsm_state_class, (t_method)pd_gfsm_state_arc_first,
@@ -298,6 +319,12 @@ void pd_gfsm_state_setup(void)
   class_addmethod(pd_gfsm_state_class, (t_method)pd_gfsm_state_add_weight,
 		  gensym("add_weight"), A_FLOAT, A_FLOAT, A_FLOAT, A_FLOAT, A_NULL);
 
+  //-- methods: properties
+  class_addmethod(pd_gfsm_state_class, (t_method)pd_gfsm_state_degree,
+		  gensym("degree"), A_NULL);
+  class_addmethod(pd_gfsm_state_class, (t_method)pd_gfsm_state_cyclic,
+		  gensym("cyclic"), A_NULL);
+
   //-- help symbol
   class_sethelpsymbol(pd_gfsm_state_class, gensym("gfsm_state-help.pd"));
 }
diff --git a/gfsm/src/pd_state.h b/gfsm/src/pd_state.h
index b2e7576..7bb96ee 100644
--- a/gfsm/src/pd_state.h
+++ b/gfsm/src/pd_state.h
@@ -3,7 +3,7 @@
  * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
  * Description: finite state automata for Pd
  *
- * Copyright (c) 2004 Bryan Jurish.
+ * Copyright (c) 2004-2006 Bryan Jurish.
  *
  * For information on usage and redistribution, and for a DISCLAIMER OF ALL
  * WARRANTIES, see the file, "LICENSE.txt," in this distribution.
@@ -37,7 +37,7 @@
 #include <pd_automaton.h>
 
 /*--------------------------------------------------------------
- * pd_fsm_automaton_pd
+ * pd_gfsm_state
  */
 typedef struct _pd_gfsm_state
 {