topological_sort.c File Reference

#include "common/darktable.h"
#include "common/topological_sort.h"
#include <stdio.h>
#include <string.h>

Include dependency graph for topological_sort.c:

Enumerations
enum	dt_visit_color_t {   DT_VISIT_WHITE = 0 ,   DT_VISIT_GRAY = 1 ,   DT_VISIT_BLACK = 2 }

Functions
static dt_digraph_node_t *	_get_or_create_node (GHashTable *by_id, const char *id)
dt_digraph_node_t *	dt_digraph_node_new (const char *id)
	Allocate and initialize a new digraph node with the given id.
int	flatten_nodes (GList *input_nodes, GList **out_nodes)
	Canonicalize / merge duplicated nodes by id.
static gboolean	_add_edge (GHashTable *outgoing, dt_digraph_node_t *from, dt_digraph_node_t *to)
static GList *	_toposort_extract_cycle_from_stack (const GList *dfs_stack, const dt_digraph_node_t *gray)
static gboolean	_dfs_visit (dt_digraph_node_t *n, GHashTable *outgoing, GHashTable *color, GList **result, int *dfs_count, GList **dfs_stack, GList **cycle_out)
int	topological_sort (GList *nodes, GList **sorted, GList **cycle_out)
	Perform a topological sort using depth-first search (DFS).
static void	dt_digraph_node_free_full (dt_digraph_node_t *node, dt_node_user_data_destroy_t user_destroy)
static void	_dt_digraph_nodes_free_full (GList *nodes, dt_node_user_data_destroy_t user_destroy)
static void	_dt_digraph_nodes_hashtable_free_full (GHashTable *ht, dt_node_user_data_destroy_t user_destroy)
void	dt_digraph_cleanup_full (GList *nodes, GHashTable *node_ht, dt_node_user_data_destroy_t user_destroy)
	Free a canonical graph (nodes, constraints, ids) in one call.

Enumeration Type Documentation

dt_visit_color_t

enum dt_visit_color_t

Enumerator
DT_VISIT_WHITE
DT_VISIT_GRAY
DT_VISIT_BLACK

Function Documentation

_add_edge()

static gboolean _add_edge ( GHashTable *  outgoing, dt_digraph_node_t *  from, dt_digraph_node_t *  to  )

static

References FALSE, and TRUE.

Referenced by topological_sort().

_dfs_visit()

static gboolean _dfs_visit ( dt_digraph_node_t *  n, GHashTable *  outgoing, GHashTable *  color, GList **  result, int *  dfs_count, GList **  dfs_stack, GList **  cycle_out  )

static

References _dfs_visit(), _toposort_extract_cycle_from_stack(), c, DT_VISIT_BLACK, DT_VISIT_GRAY, FALSE, m, n, and TRUE.

Referenced by _dfs_visit(), and topological_sort().

_dt_digraph_nodes_free_full()

static void _dt_digraph_nodes_free_full ( GList *  nodes, dt_node_user_data_destroy_t  user_destroy  )

static

References dt_digraph_node_free_full().

Referenced by dt_digraph_cleanup_full().

_dt_digraph_nodes_hashtable_free_full()

static void _dt_digraph_nodes_hashtable_free_full ( GHashTable *  ht, dt_node_user_data_destroy_t  user_destroy  )

static

References dt_digraph_node_free_full(), and key.

Referenced by dt_digraph_cleanup_full().

_get_or_create_node()

static dt_digraph_node_t * _get_or_create_node ( GHashTable *  by_id, const char *  id  )

static

References n.

Referenced by flatten_nodes().

_toposort_extract_cycle_from_stack()

static GList * _toposort_extract_cycle_from_stack ( const GList *  dfs_stack, const dt_digraph_node_t *  gray  )

static

References n.

Referenced by _dfs_visit().

dt_digraph_cleanup_full()

void dt_digraph_cleanup_full	(	GList *	nodes,
		GHashTable *	node_ht,
		dt_node_user_data_destroy_t	user_destroy
	)

Free a canonical graph (nodes, constraints, ids) in one call.

This is the recommended cleanup for canonical node graphs produced by flatten_nodes(). It frees, for each node in the provided set:

• every dt_digraph_node_constraints_t object in node->constraints
• the node->constraints GList container
• node->id (assumed owned; freed with g_free)
• the node itself
• optionally node->user_data via user_destroy

You may provide either:

• nodes: a GList of canonical nodes (unique pointers)
• node_ht: a hashtable mapping id->node (or any key->node), containing each canonical node exactly once as a value

If both are provided (non-NULL), node_ht is used as the authoritative set and nodes is ignored for node destruction (you may still free the list container yourself).

Parameters

[in]	nodes	Canonical node list (may be NULL if node_ht is provided).
[in]	node_ht	Hashtable containing canonical nodes as values (may be NULL).
[in]	user_destroy	Optional destructor for node->user_data; may be NULL.

Note

If you call this with a hashtable and you also keep a list of the same nodes, you must NOT free nodes twice. In that scenario, call:

• dt_digraph_cleanup_full(NULL, ht, ...)
• g_list_free(list) // container only

References _dt_digraph_nodes_free_full(), and _dt_digraph_nodes_hashtable_free_full().

Referenced by _hm_topo_merge_cleanup().

dt_digraph_node_free_full()

static void dt_digraph_node_free_full ( dt_digraph_node_t *  node, dt_node_user_data_destroy_t  user_destroy  )

static

References dt_free, dt_digraph_node_t::id, dt_digraph_node_t::previous, dt_digraph_node_t::tag, and dt_digraph_node_t::user_data.

Referenced by _dt_digraph_nodes_free_full(), and _dt_digraph_nodes_hashtable_free_full().

dt_digraph_node_new()

dt_digraph_node_t * dt_digraph_node_new

(

const char *

id

)

Allocate and initialize a new digraph node with the given id.

The returned node owns its id (g_strdup), has NULL previous and user_data.

Parameters

id	NUL-terminated string identifier (copied).

Returns

Newly allocated node, or NULL on allocation failure.

References n.

Referenced by _hm_build_input_nodes_from_ids(), _hm_build_input_nodes_from_ids_filtered(), _hm_build_isolated_nodes_from_modules(), _hm_build_raster_mask_nodes_from_modules(), and _iop_rules().

flatten_nodes()

int flatten_nodes	(	GList *	input_nodes,
		GList **	out_nodes
	)

Canonicalize / merge duplicated nodes by id.

Input may contain multiple dt_digraph_node_t objects with the same dt_digraph_node_t::id. Each duplicate can define an independent set of predecessors (i.e. multiple previous entries).

This function produces a flattened node list containing exactly one canonical node per id, with the following behavior:

• Creates one canonical node per distinct id, allocating it with g_new0().
• Duplicates each canonical id string with g_strdup().
• Aggregates predecessor lists (node->previous) from all input duplicates onto the canonical node’s previous list, merging duplicates (same id) so each predecessor appears only once.
• Remaps predecessor pointers to point to canonical nodes by matching ids.
• Copies payload: if multiple duplicates carry user_data, the first non-NULL user_data encountered for that id is kept (others are ignored).

The resulting list is suitable as input to topological_sort().

Parameters

[in]	input_nodes	GList of dt_digraph_node_t* (may contain duplicates by id).
[out]	out_nodes	Receives the canonical node list (unique by id). The list is newly allocated; the nodes inside are newly allocated canonical nodes.

Returns

0 on success, 1 on allocation failure or invalid arguments.

Warning

This function does NOT free or modify input_nodes or the nodes it contains. If those were heap-allocated, you must free them separately (or ensure they were owned elsewhere). Only the canonical nodes returned through out_nodes are owned by this module’s cleanup helper.

References _get_or_create_node(), dt_free, FALSE, dt_digraph_node_t::id, key, p, dt_digraph_node_t::previous, dt_digraph_node_t::tag, TRUE, and dt_digraph_node_t::user_data.

Referenced by _hm_topo_flatten_constraints().

topological_sort()

int topological_sort	(	GList *	nodes,
		GList **	sorted,
		GList **	cycle_out
	)

Perform a topological sort using depth-first search (DFS).

Builds the directed edges implied by each node's predecessor lists and produces a list in which every constraint is satisfied (when possible).

Edge interpretation (owner node = "self"):

• For each predecessor p in self->previous:
  • add edge p -> self

Then performs a standard DFS topological ordering (reverse postorder). Cycles are detected via a 3-color visitation scheme (WHITE/GRAY/BLACK). If a GRAY node is visited again, the constraint system is unsatisfiable (cycle).

Parameters

[in]	nodes	GList of dt_digraph_node_t* representing the graph nodes. Typically the output of flatten_nodes(). Nodes referenced only through predecessor lists are still considered during sorting if they are present in those lists.
[out]	sorted	Receives the sorted list (GList of dt_digraph_node_t*). The list container is newly allocated, but it contains the same node pointers from nodes.
[out]	cycle_out	Optional. When non-NULL and sorting fails due to a cycle, receives a newly allocated GList of dt_digraph_node_t* corresponding to the detected cycle (container ownership transferred to caller; nodes are not owned).

Returns

0 if sorting succeeded, 1 if the constraints contain at least one cycle.

Note

On success, *sorted must be freed with g_list_free() by the caller (container only). The nodes themselves are not freed by freeing the sorted list.

References _add_edge(), _dfs_visit(), c, DT_VISIT_WHITE, dt_digraph_node_t::id, key, n, p, and dt_digraph_node_t::previous.

Referenced by _hm_topo_sort_constraints().