[gegl] graph: add gegl_visitor_traverse()

[N/A <ell src gnome org>]

commit d917167c5d9a02762734c93193792f5ae0c03573
Author: Ell <ell_se yahoo com>
Date:   Thu Nov 9 14:31:32 2017 -0500

    graph: add gegl_visitor_traverse()
    
    Add gegl_visitor_traverse(), which traverses the graph in arbitrary
    order, allowing it to be more efficient than either a DFS or a BFS.
    
    In parctice, the graph is traversed recursively, in a similar
    fashion to a DFS, however, nodes are visited before their
    dependencies, allowing faster bailing when traversal is terminated
    early.

 gegl/graph/gegl-visitor.c |   68 +++++++++++++++++++++++++++++++++++++++++++++
 gegl/graph/gegl-visitor.h |    2 +
 2 files changed, 70 insertions(+), 0 deletions(-)
---
diff --git a/gegl/graph/gegl-visitor.c b/gegl/graph/gegl-visitor.c
index 818e42e..1a0805e 100644
--- a/gegl/graph/gegl-visitor.c
+++ b/gegl/graph/gegl-visitor.c
@@ -32,6 +32,9 @@
 
 static void       gegl_visitor_class_init        (GeglVisitorClass *klass);
 static void       gegl_visitor_init              (GeglVisitor      *self);
+static gboolean   gegl_visitor_traverse_step     (GeglVisitor      *self,
+                                                  GeglVisitable    *visitable,
+                                                  GHashTable       *visited_set);
 static gboolean   gegl_visitor_dfs_traverse_step (GeglVisitor      *self,
                                                   GeglVisitable    *visitable,
                                                   GHashTable       *visited_set);
@@ -92,6 +95,71 @@ gegl_visitor_visit_node (GeglVisitor *self,
 }
 
 /**
+ * gegl_visitor_traverse:
+ * @self: #GeglVisitor
+ * @visitable: the start #GeglVisitable
+ *
+ * Traverse starting at @visitable in arbitrary order.
+ * Use this function when you don't need a DFS/BFS
+ * specifically, since it can be more efficient.
+ *
+ * Returns: %TRUE if traversal was terminated early.
+ **/
+gboolean
+gegl_visitor_traverse (GeglVisitor   *self,
+                       GeglVisitable *visitable)
+{
+  GHashTable *visited_set;
+  gboolean    result;
+
+  g_return_val_if_fail (GEGL_IS_VISITOR (self), FALSE);
+  g_return_val_if_fail (GEGL_IS_VISITABLE (visitable), FALSE);
+
+  visited_set = g_hash_table_new (NULL, NULL);
+
+  result = gegl_visitor_traverse_step (self, visitable, visited_set);
+
+  g_hash_table_unref (visited_set);
+
+  return result;
+}
+
+static gboolean
+gegl_visitor_traverse_step (GeglVisitor   *self,
+                            GeglVisitable *visitable,
+                            GHashTable    *visited_set)
+{
+  GSList *dependencies;
+  GSList *iter;
+
+  if (gegl_visitable_accept (visitable, self))
+    return TRUE;
+
+  dependencies = gegl_visitable_depends_on (visitable);
+
+  for (iter = dependencies; iter; iter = g_slist_next (iter))
+    {
+      GeglVisitable *dependency = iter->data;
+
+      if (! g_hash_table_contains (visited_set, dependency))
+        {
+          if (gegl_visitor_traverse_step (self, dependency, visited_set))
+            {
+              g_slist_free (dependencies);
+
+              return TRUE;
+            }
+        }
+    }
+
+  g_slist_free (dependencies);
+
+  g_hash_table_add (visited_set, visitable);
+
+  return FALSE;
+}
+
+/**
  * gegl_visitor_dfs_traverse:
  * @self: #GeglVisitor
  * @visitable: the start #GeglVisitable
diff --git a/gegl/graph/gegl-visitor.h b/gegl/graph/gegl-visitor.h
index 4e68634..c53a615 100644
--- a/gegl/graph/gegl-visitor.h
+++ b/gegl/graph/gegl-visitor.h
@@ -57,6 +57,8 @@ gboolean   gegl_visitor_visit_pad    (GeglVisitor   *self,
 gboolean   gegl_visitor_visit_node   (GeglVisitor   *self,
                                       GeglNode      *node);
 
+gboolean   gegl_visitor_traverse     (GeglVisitor   *self,
+                                      GeglVisitable *visitable);
 gboolean   gegl_visitor_dfs_traverse (GeglVisitor   *self,
                                       GeglVisitable *visitable);
 gboolean   gegl_visitor_bfs_traverse (GeglVisitor   *self,