Dependency graph building and topological sorting for monorepo apps.
Builds a directed graph from internal path: dependencies and provides
topological ordering for correct publish order, dependency resolution,
and cascade planning.
New annotation helpers (for rendering):
level_map/1— inverts atopological_levels/1result into a%{name => level}map.dep_count/2— returns the count of direct project-internal deps for a given name.deep_count/2— shallow count of a name's direct deps that themselves have at least one dep.
Summary
Functions
Builds a dependency graph from a list of apps.
Shallow count of name's direct deps that themselves have at least one project-internal dep.
Returns the count of direct project-internal deps for a given app name.
Returns a map of %{app_name => [dependent_names]} (reverse graph).
Filters topological levels to only include the specified apps. Removes empty levels.
Inverts the topological_levels/1 result into a name-keyed map for O(1) level lookups.
Computes topological levels using Kahn's algorithm.
Resolves transitive dependents for a list of app names (reverse direction).
Resolves transitive dependencies for a list of app names.
Types
Functions
Builds a dependency graph from a list of apps.
Returns a map of %{app_name => [dependency_names]}.
@spec deep_count(name(), graph()) :: non_neg_integer()
Shallow count of name's direct deps that themselves have at least one project-internal dep.
SHALLOW count, NOT a recursive depth metric. For a chain a→b→c where c has no deps:
deep_count("a", graph)is1(b has deps)deep_count("b", graph)is0(c has no deps)
See ADR D4 in the design document.
Returns 0 for leaves and unknown names.
Examples
iex> graph = %{"a" => ["b"], "b" => ["c"], "c" => []}
iex> Graph.deep_count("a", graph)
1
iex> Graph.deep_count("b", graph)
0@spec dep_count(name(), graph()) :: non_neg_integer()
Returns the count of direct project-internal deps for a given app name.
Returns 0 for unknown names (not present in the graph).
Examples
iex> Graph.dep_count("a", %{"a" => ["b", "c"], "b" => ["c"], "c" => []})
2
iex> Graph.dep_count("z", %{"a" => ["b"]})
0Returns a map of %{app_name => [dependent_names]} (reverse graph).
For each app, lists which apps depend on it.
Filters topological levels to only include the specified apps. Removes empty levels.
@spec level_map(levels()) :: %{required(name()) => non_neg_integer()}
Inverts the topological_levels/1 result into a name-keyed map for O(1) level lookups.
Examples
iex> Graph.level_map([{0, ["c", "d"]}, {1, ["b"]}, {2, ["a"]}])
%{"a" => 2, "b" => 1, "c" => 0, "d" => 0}
iex> Graph.level_map([])
%{}Computes topological levels using Kahn's algorithm.
Returns [{level, [app_names]}] where level 0 has no internal deps,
level 1 depends only on level 0, etc.
Resolves transitive dependents for a list of app names (reverse direction).
Given an app, returns all apps that depend on it recursively (upstream).
For example, if cfdi_xml depends on cfdi_csd, then cfdi_xml is a
transitive dependent of cfdi_csd.
This is the inverse of transitive_deps/2.
Resolves transitive dependencies for a list of app names.
Returns a MapSet of all apps that need to be included (the requested apps plus all their transitive dependencies).