Utility functions for working with directed acyclic graphs (DAGs).
This module provides functions for validating and analyzing graph structures, particularly for ensuring that filter graphs are properly formed as DAGs without cycles, which is a requirement for FFmpeg filter chains.
Functions:
| Name | Description |
|---|---|
is_dag |
Determine if a graph is a directed acyclic graph (DAG) using topological sorting. |
is_dag(graph: dict[str, set[str]]) -> bool
Determine if a graph is a directed acyclic graph (DAG) using topological sorting.
This function implements Kahn's algorithm for topological sorting to check if the given graph is a DAG. A graph is a DAG if it has no directed cycles. The algorithm works by repeatedly removing nodes with no incoming edges and their outgoing edges. If all nodes can be removed this way, the graph is a DAG; otherwise, it contains at least one cycle.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
graph
|
dict[str, set[str]]
|
A dictionary representing the graph, where keys are node IDs and values are sets of node IDs that the key node points to |
required |
Returns:
| Type | Description |
|---|---|
bool
|
True if the graph is a DAG (has no cycles), False otherwise |
Example
# A simple linear graph (A -> B -> C)
graph = {"A": {"B"}, "B": {"C"}, "C": set()}
assert is_dag(graph) == True
# A graph with a cycle (A -> B -> C -> A)
graph = {"A": {"B"}, "B": {"C"}, "C": {"A"}}
assert is_dag(graph) == False