topological_sort.h File Reference

Small directed-graph helper for constraint aggregation and topological sorting. More...

#include <glib.h>

Include dependency graph for topological_sort.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	dt_digraph_node_constraints_t
	One constraint set relative to the node that owns it. More...
struct	dt_digraph_node_t
	Directed graph node. More...

Typedefs
typedef typedefG_BEGIN_DECLS struct dt_digraph_node_t	dt_digraph_node_t
	Forward declaration of node type.
typedef void(*	dt_node_user_data_destroy_t) (void *data)
	Optional destructor for node payloads.

Functions
int	flatten_nodes (GList *input_nodes, GList **out_nodes)
	Canonicalize / merge duplicated nodes by id.
int	topological_sort (GList *nodes, GList **sorted, GList **cycle_out)
	Perform a topological sort using depth-first search (DFS).
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.
dt_digraph_node_t *	dt_digraph_node_new (const char *id)
	Allocate and initialize a new digraph node with the given id.

Detailed Description

Small directed-graph helper for constraint aggregation and topological sorting.

This module provides:

• A node model (dt_digraph_node_t) with per-node constraint sets.
• A "flatten" step that canonicalizes nodes by string id and aggregates constraints.
• A depth-first-search topological sort.
• A one-shot cleanup API to free all nodes/constraints/ids (and optionally node payloads).

Key concepts

Nodes

A node is identified by dt_digraph_node_t::id (a NUL-terminated UTF-8 string). Nodes also carry an opaque payload pointer dt_digraph_node_t::user_data.

Constraints

Constraints are stored per node as a list (dt_digraph_node_t::constraints) of dt_digraph_node_constraints_t*. Each constraint is interpreted relative to the node owning it:

• If constraint->previous is non-NULL: it means previous MUST be ordered before self. This creates a directed edge: previous -> self.
• If constraint->next is non-NULL: it means next MUST be ordered after self. This creates a directed edge: self -> next.

A node may have more than one constraint set, represented by multiple dt_digraph_node_constraints_t objects in its list.

Flattening / canonicalization

In some pipelines, nodes may be duplicated (same id) while each duplicate declares different constraints. flatten_nodes() merges (canonicalizes) such duplicates:

• Produces one canonical node per id.
• Aggregates all constraint objects onto the canonical node's constraint list.
• Ensures constraint endpoints (previous/next) point to canonical nodes as well.

The resulting node list is suitable for topological_sort().

Ownership and lifetime

This module assumes that canonical nodes created by flatten_nodes() own:

• node->id (duplicated with g_strdup())
• each dt_digraph_node_constraints_t object in node->constraints
• the node object itself

Pointers stored in dt_digraph_node_constraints_t::previous/next are non-owning references to other nodes; they must never be freed via the constraint object.

The cleanup helper dt_digraph_cleanup_full() frees canonical nodes, their ids, their constraint lists, and each constraint object. It can optionally free user_data using a callback.

dt_digraph_cleanup_full(flat, NULL, my_user_data_destroy);

Typedef Documentation

dt_digraph_node_t

typedef typedefG_BEGIN_DECLS struct dt_digraph_node_t dt_digraph_node_t

Forward declaration of node type.

dt_node_user_data_destroy_t

typedef void(* dt_node_user_data_destroy_t) (void *data)

Optional destructor for node payloads.

This callback is invoked by dt_digraph_cleanup_full() for each canonical node that has a non-NULL dt_digraph_node_t::user_data.

If you pass NULL, user_data is left untouched.

Function Documentation

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_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().