diff options
Diffstat (limited to 'ufo/ufo-graph.c')
-rw-r--r-- | ufo/ufo-graph.c | 115 |
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 |