Move finding longest path to UfoGraph base class

1 files changed, 109 insertions, 6 deletions

diff --git a/ufo/ufo-graph.c b/ufo/ufo-graph.c
index aa5c2ed..faeb7e7 100644
--- a/ufo/ufo-graph.c
+++ b/ufo/ufo-graph.c
@@ -684,13 +684,14 @@ pickup_paths (UfoGraph *graph,
               UfoNode *current,
               UfoNode *last,
               GList  *current_path,
-              GList **paths)
+              GList **paths,
+              gpointer user)
 {
     GList *successors;
     GList *it;
 
-    if (pred (current, NULL)) {
-        if (!pred (last, NULL))
+    if (pred (current, user)) {
+        if (!pred (last, user))
             current_path = g_list_append (current_path, last);
 
         current_path = g_list_append (current_path, current);
@@ -707,7 +708,7 @@ pickup_paths (UfoGraph *graph,
     successors = ufo_graph_get_successors (graph, current);
 
     g_list_for (successors, it) {
-        pickup_paths (graph, pred, it->data, current, g_list_copy (current_path), paths);
+        pickup_paths (graph, pred, it->data, current, g_list_copy (current_path), paths, user);
     }
 
     g_list_free (successors);
@@ -717,6 +718,7 @@ pickup_paths (UfoGraph *graph,
  * ufo_graph_get_paths:
  * @graph: A #UfoGraph
  * @pred: (scope call): A predicate function
+ * @user_data: User-data passed to @pred
  *
  * Compute a list of lists that contain complete paths with nodes that match a
  * predicate function.
@@ -726,7 +728,8 @@ pickup_paths (UfoGraph *graph,
  */
 GList *
 ufo_graph_get_paths (UfoGraph *graph,
-                     UfoFilterPredicate pred)
+                     UfoFilterPredicate pred,
+                     gpointer user_data)
 {
     GList *roots;
     GList *it;
@@ -736,13 +739,113 @@ ufo_graph_get_paths (UfoGraph *graph,
 
     g_list_for (roots, it) {
         UfoNode *node = UFO_NODE (it->data);
-        pickup_paths (graph, pred, node, node, NULL, &paths);
+        pickup_paths (graph, pred, node, node, NULL, &paths, user_data);
     }
 
     g_list_free (roots);
     return paths;
 }
 
+static gboolean
+path_unvisited (GList *path,
+                GList **visited)
+{
+    GList *head;
+    GList *tail;
+
+    head = g_list_first (path);
+    tail = g_list_last (path);
+
+    for (GList *it = g_list_first (head); it != tail; it = g_list_next (it)) {
+        UfoNode *node = (UfoNode *) it->data;
+
+        if (g_list_find (*visited, node))
+            return FALSE;
+
+        *visited = g_list_append (*visited, node);
+    }
+
+    return TRUE;
+}
+
+static GList *
+remove_common_ancestry_paths (GList *paths)
+{
+    GList *result;
+    GList *visited;
+    GList *it;
+
+    result = NULL;
+    visited = NULL;
+
+    g_list_for (paths, it) {
+        GList *path = (GList *) it->data;
+
+        if (path_unvisited (it->data, &visited))
+            result = g_list_append (result, path);
+    }
+
+    g_list_free (visited);
+    g_list_free (paths);
+    return result;
+}
+
+static GList *
+find_longest_path (GList *paths)
+{
+    GList *longest = NULL;
+    GList *it;
+    guint max_length = 0;
+
+    g_list_for (paths, it) {
+        guint length;
+        GList *path;
+
+        path = (GList *) it->data;
+        length = g_list_length (path);
+
+        if (length > max_length) {
+            max_length = length;
+            longest = path;
+        }
+    }
+
+    return longest;
+}
+
+/**
+ * ufo_graph_find_longest_path:
+ * @graph: A #UfoGraph
+ * @pred: (scope call): Predicate function for which elements of the path must
+ *      evaluate to %TRUE.
+ * @user_data: User data passed to @pred.
+ *
+ * Find the longest path in @task_graph that fulfills @predicate.
+ *
+ * Returns: (transfer full) (element-type UfoNode): A list with nodes in
+ * subsequent order of the path. User must free it with g_list_free.
+ */
+GList *
+ufo_graph_find_longest_path (UfoGraph *graph,
+                             UfoFilterPredicate pred,
+                             gpointer user_data)
+{
+    GList *it;
+    GList *paths;
+    GList *result;
+
+    paths = ufo_graph_get_paths (graph, pred, user_data);
+    paths = remove_common_ancestry_paths (paths);
+    result = find_longest_path (paths);
+
+    g_list_for (paths, it) {
+        if (it->data != result)
+            g_list_free (it->data);
+    }
+
+    return result;
+}
+
 /**
  * ufo_graph_dump_dot:
  * @graph: A #UfoGraph