@spec complement(Yog.Graph.t(), term()) :: Yog.Graph.t()

Creates the complement of a graph.

The complement contains the same nodes but connects all pairs of nodes that are not connected in the original graph, and removes all edges that are present. Each new edge gets the supplied default_weight.

Self-loops are never added in the complement.

Time Complexity: O(V² + E)

Example

iex> graph =
...>   Yog.undirected()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> comp = Yog.Transform.complement(graph, 100)
iex> # Original: 1-2 connected, 1-3 and 2-3 not
iex> # Complement: 1-3 and 2-3 connected, 1-2 not
iex> {1, 100} in Yog.successors(comp, 3)
true

Use Cases

• Finding independent sets (cliques in the complement)
• Graph coloring via complement analysis
• Testing graph density (sparse ↔ dense complement)

@spec contract(
  Yog.Graph.t(),
  Yog.node_id(),
  Yog.node_id(),
  (term(), term() -> term())
) :: Yog.Graph.t()

Contracts an edge by merging node b into node a.

Node b is removed from the graph, and all edges connected to b are redirected to a. If both a and b had edges to the same neighbor, their weights are combined using with_combine.

Self-loops (edges from a node to itself) are removed during contraction.

Important for undirected graphs: Since undirected edges are stored bidirectionally, each logical edge is processed twice during contraction, causing weights to be combined twice. For example, if edge weights represent capacities, this effectively doubles them. Consider dividing weights by 2 or using a custom combine function if this behavior is undesired.

Time Complexity: O(deg(a) + deg(b)) - proportional to the combined degree of both nodes.

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
...>   |> Yog.add_edge_ensure(from: 2, to: 3, with: 20)
iex> contracted = Yog.Transform.contract(graph, 1, 2, fn w1, w2 -> w1 + w2 end)
iex> # Result: nodes [1, 3], edge 1->3 with weight 20
iex> # Node 2 is merged into node 1
iex> Yog.successors(contracted, 1)
[{3, 20}]

Combining Weights

When both a and b have edges to the same neighbor c:

iex> # Before: a->c (5), b->c (10)
iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge_ensure(from: 1, to: 3, with: 5)
...>   |> Yog.add_edge_ensure(from: 2, to: 3, with: 10)
iex> contracted = Yog.Transform.contract(graph, 1, 2, fn w1, w2 -> w1 + w2 end)
iex> # After: a->c (15) (5 + 10)
iex> Yog.successors(contracted, 1)
[{3, 15}]

Use Cases

• Stoer-Wagner algorithm for minimum cut
• Graph simplification by merging strongly connected nodes
• Community detection by contracting nodes in the same community
• Karger's algorithm for minimum cut (randomized)

@spec ego_graph(Yog.Graph.t(), Yog.node_id(), non_neg_integer(), keyword()) ::
  Yog.Graph.t()

Returns the ego graph of a node: the subgraph induced by the node and all nodes within radius hops.

For undirected graphs, neighbors are traversed in both directions. For directed graphs, the behavior is controlled by the :mode option:

• :successors (default) - Follow outgoing edges only. This aligns with the English notion of "ego" (who the node points to / influences).
• :neighbors - Follow both outgoing and incoming edges (the union of successors and predecessors).

Options

• :mode - :successors or :neighbors. Only affects directed graphs.

Examples

Radius 1 (default) on an undirected graph

iex> graph =
...>   Yog.undirected()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
...>   |> Yog.add_edge_ensure(from: 2, to: 3, with: 20)
iex> ego = Yog.Transform.ego_graph(graph, 2)
iex> Enum.sort(Yog.all_nodes(ego))
[1, 2, 3]

Directed graph with :successors mode (default)

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
...>   |> Yog.add_edge_ensure(from: 2, to: 3, with: 20)
iex> ego = Yog.Transform.ego_graph(graph, 2)
iex> Enum.sort(Yog.all_nodes(ego))
[2, 3]

Directed graph with :neighbors mode

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
...>   |> Yog.add_edge_ensure(from: 3, to: 2, with: 20)
iex> ego = Yog.Transform.ego_graph(graph, 2, 1, mode: :neighbors)
iex> Enum.sort(Yog.all_nodes(ego))
[1, 2, 3]

Radius 2

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_nodes_from([{1, nil}, {2, nil}, {3, nil}, {4, nil}])
...>   |> Yog.add_edges!([{1, 2, 1}, {2, 3, 1}, {3, 4, 1}])
iex> ego = Yog.Transform.ego_graph(graph, 1, 2)
iex> Enum.sort(Yog.all_nodes(ego))
[1, 2, 3]

@spec filter_edges(Yog.Graph.t(), (Yog.node_id(), Yog.node_id(), term() -> boolean())) ::
  Yog.Graph.t()

Filters edges by a predicate, preserving all nodes.

Returns a new graph with the same nodes but only the edges where the predicate returns true. The predicate receives (src, dst, weight).

Time Complexity: O(E) where E is the number of edges

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edges([{1, 2, 5}, {1, 3, 15}, {2, 3, 3}])
iex> # Keep only edges with weight >= 10
iex> heavy = Yog.Transform.filter_edges(graph, fn _src, _dst, w -> w >= 10 end)
iex> # Result: edges [1->3 (15)], edges 1->2 and 2->3 removed
iex> Yog.successors(heavy, 1)
[{3, 15}]

Use Cases

• Pruning low-weight edges in weighted networks
• Removing self-loops: filter_edges(g, fn(s, d, _) -> s != d end)
• Threshold-based graph sparsification

@spec filter_nodes(Yog.Graph.t(), (term() -> boolean())) :: Yog.Graph.t()

Filters nodes by a predicate, automatically pruning connected edges.

Returns a new graph containing only nodes whose data satisfies the predicate. All edges connected to removed nodes (both incoming and outgoing) are automatically removed to maintain graph consistency.

Time Complexity: O(V + E) where V is nodes and E is edges

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "apple")
...>   |> Yog.add_node(2, "banana")
...>   |> Yog.add_node(3, "apricot")
...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...>   |> Yog.add_edge_ensure(from: 2, to: 3, with: 2)
iex> # Keep only nodes starting with 'a'
iex> filtered = Yog.Transform.filter_nodes(graph, fn s ->
...>   String.starts_with?(s, "a")
...> end)
iex> # Result has nodes 1 and 3, edge 1->2 is removed (node 2 gone)
iex> map_size(filtered.nodes)
2

Use Cases

• Extract subgraphs based on node properties
• Remove inactive/disabled nodes from a network
• Filter by node importance/centrality

@spec filter_nodes_indexed(Yog.Graph.t(), (Yog.node_id(), term() -> boolean())) ::
  Yog.Graph.t()

Filters nodes by a predicate that also receives the node ID.

Returns a new graph containing only nodes for which the predicate returns true. Connected edges are automatically pruned.

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "apple")
...>   |> Yog.add_node(2, "apple")
...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> # Keep only even numbered nodes
iex> filtered = Yog.Transform.filter_nodes_indexed(graph, fn id, _data -> rem(id, 2) == 0 end)
iex> map_size(filtered.nodes)
1
iex> Map.has_key?(filtered.nodes, 2)
true

@spec map_edges(Yog.Graph.t(), (term() -> term())) :: Yog.Graph.t()

Transforms edge weights using a function, preserving graph structure.

This is a functor operation - it applies a function to every edge's weight/data while keeping all nodes and the graph topology unchanged.

Time Complexity: O(E) where E is the number of edges

Functor Law: map_edges(map_edges(g, f), h) == map_edges(g, fn x -> h.(f.(x)) end)

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edges([{1, 2, 10}, {2, 3, 20}])
iex> # Double all weights
iex> doubled = Yog.Transform.map_edges(graph, fn w -> w * 2 end)
iex> # Edges now have weights 20 and 40
iex> Yog.successors(doubled, 1)
[{2, 20}]

Type Changes

Can change the edge weight type:

iex> # Convert integer weights to floats
iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 10)
iex> float_graph = Yog.Transform.map_edges(graph, fn w -> w * 1.0 end)
iex> Yog.successors(float_graph, 1)
[{2, 10.0}]

iex> # Convert weights to labels
iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 5)
iex> labeled = Yog.Transform.map_edges(graph, fn w ->
...>   if w < 10, do: "short", else: "long"
...> end)
iex> Yog.successors(labeled, 1)
[{2, "short"}]

@spec map_edges_async(Yog.Graph.t(), (term() -> term()), keyword()) :: Yog.Graph.t()

Transforms edge weights using a function in parallel, preserving graph structure.

This is the async version of map_edges/2 that uses Task.async_stream/3 to process edge transformations concurrently. For large graphs with expensive transformation functions, this can provide significant speedups on multi-core systems.

The parallelization strategy processes nodes (and their outgoing edges) in parallel, transforming all edges from each node concurrently.

Time Complexity: O(E/cores) amortized, where E is the number of edges

When to use:

• Large graphs (100,000+ edges)
• Expensive transformation functions (I/O, database lookups, complex calculations)
• Multi-core systems where parallelism benefits outweigh overhead

When NOT to use:

• Small graphs (< 10,000 edges) - overhead dominates
• Trivial transformations (arithmetic) - spawning tasks costs more
• Already in a parallel context - avoid nested parallelism

Options

• :max_concurrency - Maximum concurrent tasks (default: System.schedulers_online())
• :timeout - Task timeout in milliseconds (default: 5000)
• :ordered - Preserve order (default: false, faster unordered)

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 10)
iex> doubled = Yog.Transform.map_edges_async(graph, fn w -> w * 2 end)
iex> Yog.successors(doubled, 1)
[{2, 20}]

Custom Options

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 5)
iex> opts = [max_concurrency: 8, timeout: 10_000]
iex> result = Yog.Transform.map_edges_async(graph, fn w -> w * 3 end, opts)
iex> Yog.successors(result, 1)
[{2, 15}]

Performance Example

# Sequential map_edges on 1M edges with moderate computation: ~6 seconds
graph |> Yog.Transform.map_edges(fn w -> expensive_transform(w) end)

# Parallel map_edges_async on 8-core system: ~1 second
graph |> Yog.Transform.map_edges_async(fn w -> expensive_transform(w) end)

@spec map_edges_indexed(Yog.Graph.t(), (Yog.node_id(), Yog.node_id(), term() ->
                                    term())) ::
  Yog.Graph.t()

Transforms edge weights using a function that also takes the source and destination IDs.

Example

iex> {:ok, graph} = Yog.directed()
...>   |> Yog.add_node(1, "A") |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 10)
iex> result = Yog.Transform.map_edges_indexed(graph, fn u, v, w -> u + v + w end)
iex> Yog.successors(result, 1)
[{2, 13}] # 1 + 2 + 10

@spec map_nodes(Yog.Graph.t(), (term() -> term())) :: Yog.Graph.t()

Transforms node data using a function, preserving graph structure.

This is a functor operation - it applies a function to every node's data while keeping all edges and the graph structure unchanged.

Time Complexity: O(V) where V is the number of nodes

Functor Law: map_nodes(map_nodes(g, f), h) == map_nodes(g, fn x -> h.(f.(x)) end)

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "alice")
...>   |> Yog.add_node(2, "bob")
iex> uppercased = Yog.Transform.map_nodes(graph, &String.upcase/1)
iex> # Nodes now contain "ALICE" and "BOB"
iex> uppercased.nodes[1]
"ALICE"

Type Changes

Can change the node data type:

iex> # Convert string node data to integers
iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "5")
...>   |> Yog.add_node(2, "10")
iex> int_graph = Yog.Transform.map_nodes(graph, fn s -> String.to_integer(s) end)
iex> int_graph.nodes[1]
5

@spec map_nodes_async(Yog.Graph.t(), (term() -> term()), keyword()) :: Yog.Graph.t()

Transforms node data using a function in parallel, preserving graph structure.

This is the async version of map_nodes/2 that uses Task.async_stream/3 to process node transformations concurrently. For large graphs with expensive transformation functions, this can provide significant speedups on multi-core systems.

Time Complexity: O(V/cores) amortized, where V is the number of nodes

When to use:

• Large graphs (10,000+ nodes)
• Expensive transformation functions (I/O, complex computations)
• Multi-core systems where parallelism benefits outweigh overhead

When NOT to use:

• Small graphs (< 1,000 nodes) - overhead dominates
• Trivial transformations - spawning tasks costs more than the work
• Already in a parallel context - avoid nested parallelism

Options

• :max_concurrency - Maximum concurrent tasks (default: System.schedulers_online())
• :timeout - Task timeout in milliseconds (default: 5000)
• :ordered - Preserve order (default: false, faster unordered)

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "alice")
...>   |> Yog.add_node(2, "bob")
iex> uppercased = Yog.Transform.map_nodes_async(graph, &String.upcase/1)
iex> uppercased.nodes[1]
"ALICE"

Custom Options

iex> graph = Yog.directed() |> Yog.add_node(1, "test")
iex> opts = [max_concurrency: 4, timeout: 10_000]
iex> result = Yog.Transform.map_nodes_async(graph, &String.upcase/1, opts)
iex> result.nodes[1]
"TEST"

Performance Example

# Sequential map_nodes on 1M nodes with moderate computation: ~6 seconds
graph |> Yog.Transform.map_nodes(fn x -> expensive_function(x) end)

# Parallel map_nodes_async on 8-core system: ~1 second
graph |> Yog.Transform.map_nodes_async(fn x -> expensive_function(x) end)

@spec map_nodes_indexed(Yog.Graph.t(), (Yog.node_id(), term() -> term())) ::
  Yog.Graph.t()

Transforms node data using a function that also takes the node ID.

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
iex> mapped = Yog.Transform.map_nodes_indexed(graph, fn id, data -> "#{id}:#{data}" end)
iex> mapped.nodes[1]
"1:A"

@spec merge(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()

Combines two graphs, with the second graph's data taking precedence on conflicts.

Merges nodes, out_edges, and in_edges from both graphs. When a node exists in both graphs, the node data from other overwrites base. When the same edge exists in both graphs, the edge weight from other overwrites base.

Importantly, edges from different nodes are combined - if base has edges 1->2 and 1->3, and other has edges 1->4 and 1->5, the result will have all four edges from node 1.

The resulting graph uses the kind (Directed/Undirected) from the base graph.

Time Complexity: O(V + E) for both graphs combined

Example

iex> base =
...>   Yog.directed()
...>   |> Yog.add_node(1, "Original")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
iex> other =
...>   Yog.directed()
...>   |> Yog.add_node(1, "Updated")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge_ensure(from: 1, to: 3, with: 20)
iex> merged = Yog.Transform.merge(base, other)
iex> # Node 1 has "Updated" (from other)
iex> # Node 1 has edges to: 2 and 3 (all edges combined)
iex> length(Yog.successors(merged, 1))
2

Use Cases

• Combining disjoint subgraphs
• Applying updates/patches to a graph
• Building graphs incrementally from multiple sources

@spec normalize_node_ids(Yog.Graph.t()) :: Yog.Graph.t()

Normalizes all node IDs to a continuous range of integers 0..n-1.

The mapping is deterministic, based on the sorted order of existing node IDs. This is useful for preparing graphs for formats like Graph6 or Sparse6, or for optimizing algorithms that benefit from integer indexing.

Time Complexity: O(V log V + E)

Example

iex> graph = Yog.undirected() |> Yog.add_node("B", nil) |> Yog.add_node("A", nil)
iex> normalized = Yog.Transform.normalize_node_ids(graph)
iex> Map.keys(normalized.nodes) |> Enum.sort()
[0, 1]

@spec quotient_graph(
  Yog.Graph.t(),
  %{required(Yog.node_id()) => Yog.node_id()},
  (term(), term() -> term()),
  (term(), term() -> term())
) :: Yog.Graph.t()

Contracts nodes according to a partition map, producing a quotient graph.

Each block in the partition becomes a single super-node. All edges between nodes in different blocks become edges between the corresponding super-nodes, with weights combined using combine_weight. Edges within the same block (self-loops) are dropped.

Nodes not present in partition are treated as singleton blocks (their block ID is the node itself).

Time Complexity: O(V + E)

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_node(4, "D")
...>   |> Yog.add_edge_ensure(1, 3, 1)
...>   |> Yog.add_edge_ensure(2, 3, 1)
...>   |> Yog.add_edge_ensure(3, 4, 1)
iex> partition = %{1 => :ab, 2 => :ab, 3 => :cd, 4 => :cd}
iex> q = Yog.Transform.quotient_graph(graph, partition, &Kernel.+/2)
iex> Yog.Model.node_count(q)
2
iex> Yog.successors(q, :ab)
[{:cd, 2}]

Use Cases

• Multilevel community detection: contract communities and re-run algorithms
• Hierarchical aggregation: summarize large graphs by role or cluster
• SCC condensation: collapse strongly connected components

@spec relabel_nodes(Yog.Graph.t(), (Yog.node_id() -> Yog.node_id())) :: Yog.Graph.t()

Relabels all node IDs in the graph using a mapping function.

This operation replaces every node ID u with fun.(u). It updates all node identifiers and all edge references (source and destination) to maintain graph consistency.

Warning: If the function is not injective (i.e., different IDs map to the same new ID), nodes will be merged. In such cases, the data of the last node processed will be kept, and edges will be combined (last edge weight wins).

Time Complexity: O(V + E)

Parameters

• graph - The graph to relabel
• fun - Function (node_id) -> new_node_id (default: :erlang.phash2/1)

Examples

String to Integer relabeling

iex> graph = Yog.directed() |> Yog.add_node("A", 1) |> Yog.add_node("B", 2)
iex> relabeled = Yog.Transform.relabel_nodes(graph, fn
...>   "A" -> 1
...>   "B" -> 2
...> end)
iex> Yog.Model.has_node?(relabeled, 1)
true

Default: hashing IDs to integers

iex> graph = Yog.directed() |> Yog.add_node("user_123", nil)
iex> hashed = Yog.Transform.relabel_nodes(graph)
iex> id = Map.keys(hashed.nodes) |> List.first()
iex> is_integer(id)
true

@spec subgraph(Yog.Graph.t(), [Yog.node_id()]) :: Yog.Graph.t()

Extracts a subgraph containing only the specified nodes and their connecting edges.

Returns a new graph with only the nodes whose IDs are in the provided list, along with any edges that connect nodes within this subset. Nodes not in the list are removed, and all edges touching removed nodes are pruned.

Time Complexity: O(V + E) where V is nodes and E is edges

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_node(4, "D")
...>   |> Yog.add_edges([{1, 2, 10}, {2, 3, 20}, {3, 4, 30}])
iex> # Extract only nodes 2 and 3
iex> sub = Yog.Transform.subgraph(graph, [2, 3])
iex> # Result has nodes 2, 3 and edge 2->3
iex> # Edges 1->2 and 3->4 are removed (endpoints outside subgraph)
iex> Yog.successors(sub, 2)
[{3, 20}]

Use Cases

• Extracting connected components found by algorithms
• Analyzing k-hop neighborhoods around specific nodes
• Working with strongly connected components (extract each SCC)
• Removing nodes found by some criteria (keep the inverse set)
• Visualizing specific portions of large graphs

Comparison with filter_nodes/2

• filter_nodes/2 - Filters by predicate on node data (e.g., "keep active users")
• subgraph/2 - Filters by explicit node IDs (e.g., "keep nodes [1, 5, 7]")

@spec to_directed(Yog.Graph.t()) :: Yog.Graph.t()

Converts an undirected graph to a directed graph.

Since yog internally stores undirected edges as bidirectional directed edges, this is essentially free — it just changes the kind flag. The resulting directed graph has two directed edges (A→B and B→A) for each original undirected edge.

If the graph is already directed, it is returned unchanged.

Time Complexity: O(1)

Example

iex> undirected =
...>   Yog.undirected()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
iex> directed = Yog.Transform.to_directed(undirected)
iex> # Has edges: 1->2 and 2->1 (both with weight 10)
iex> directed.kind
:directed

@spec to_undirected(Yog.Graph.t(), (term(), term() -> term())) :: Yog.Graph.t()

Converts a directed graph to an undirected graph.

For each directed edge A→B, ensures B→A also exists. If both A→B and B→A already exist with different weights, the resolve function decides which weight to keep.

If the graph is already undirected, it is returned unchanged.

Time Complexity: O(E) where E is the number of edges

Examples

When both directions exist, keep the smaller weight

iex> directed =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edges!([{1, 2, 10}, {2, 1, 20}])
iex> undirected = Yog.Transform.to_undirected(directed, &min/2)
iex> # Edge 1-2 has weight 10 (min of 10 and 20)
iex> Yog.successors(undirected, 1)
[{2, 10}]

One-directional edges get mirrored automatically

iex> directed =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 5)
iex> undirected = Yog.Transform.to_undirected(directed, &min/2)
iex> # Edge exists in both directions with weight 5
iex> Enum.sort(Yog.successors(undirected, 1))
[{2, 5}]

@spec transitive_closure(Yog.Graph.t()) :: Yog.Graph.t()

Computes the transitive closure of the graph.

The transitive closure adds an edge from node A to node C whenever there is a path from A to C. For a DAG, this uses a topological sorting optimization. For graphs with cycles, it uses a general path-reaching approach.

Time Complexity: O(V × (V + E))

Examples

iex> graph = Yog.directed()
...> |> Yog.add_edge_ensure(1, 2, 1, nil)
...> |> Yog.add_edge_ensure(2, 3, 1, nil)
iex> closure = Yog.Transform.transitive_closure(graph)
iex> Yog.Model.has_edge?(closure, 1, 3)
true

@spec transitive_reduction(Yog.Graph.t()) ::
  {:ok, Yog.Graph.t()} | {:error, :contains_cycle}

Computes the transitive reduction of a DAG.

Transitive reduction removes redundant edges that are implied by transitivity. For Directed Acyclic Graphs (DAGs), the result is unique and minimal.

If the graph contains cycles, this returns an error as transitive reduction is not uniquely defined for general graphs with cycles.

Time Complexity: O(V × (V + E))

Examples

iex> graph = Yog.directed()
...> |> Yog.add_edge_ensure(:a, :b, 1, nil)
...> |> Yog.add_edge_ensure(:b, :c, 1, nil)
...> |> Yog.add_edge_ensure(:a, :c, 1, nil)
iex> reduction = Yog.Transform.transitive_reduction(graph)
iex> {:ok, red} = reduction
iex> # Edge a->c is redundant because a->b->c exists
iex> Yog.Model.has_edge?(red, :a, :c)
false

@spec transpose(Yog.Graph.t()) :: Yog.Graph.t()

Reverses the direction of every edge in the graph (graph transpose).

Due to the dual-map representation (storing both out_edges and in_edges), this is an O(1) operation - just a pointer swap! This is dramatically faster than most graph libraries where transpose is O(E).

Time Complexity: O(1)

Property: transpose(transpose(G)) = G

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edges([{1, 2, 10}, {2, 3, 20}])
iex> reversed = Yog.Transform.transpose(graph)
iex> # Now has edges: 2->1 and 3->2
iex> Yog.successors(reversed, 2)
[{1, 10}]

Use Cases

• Computing strongly connected components (Kosaraju's algorithm)
• Finding all nodes that can reach a target node
• Reversing dependencies in a DAG

@spec update_edge(Yog.Graph.t(), Yog.node_id(), Yog.node_id(), term(), (term() ->
                                                                    term())) ::
  Yog.Graph.t()

Updates a specific edge's weight/metadata.

This is the "safe" way to perform the update, ensuring that both in_edges and out_edges stay in sync. It also handles undirected graphs properly.

If either node u or v does not exist in the graph, the original graph is returned unchanged.

Example

iex> {:ok, graph} = Yog.directed()
...>   |> Yog.add_node(1, "A") |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 10)
iex> updated = Yog.Transform.update_edge(graph, 1, 2, 0, fn w -> w + 5 end)
iex> Yog.successors(updated, 1)
[{2, 15}]

iex> {:ok, graph} = Yog.undirected()
...>   |> Yog.add_node(1, "A") |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 10)
iex> updated = Yog.Transform.update_edge(graph, 1, 2, 0, fn w -> w * 2 end)
iex> Yog.successors(updated, 1)
[{2, 20}]
iex> Yog.successors(updated, 2)
[{1, 20}]

@spec update_node(Yog.Graph.t(), Yog.node_id(), term(), (term() -> term())) ::
  Yog.Graph.t()

Updates a specific node's data using an updater function.

Similar to Map.update/4, it takes an initial value if the node doesn't exist, but since this is a graph transformation, it is typically used on existing nodes.

Example

iex> graph = Yog.directed() |> Yog.add_node(1, 100)
iex> updated = Yog.Transform.update_node(graph, 1, 0, fn x -> x + 50 end)
iex> Yog.Model.node(updated, 1)
150

iex> graph = Yog.directed()
iex> updated = Yog.Transform.update_node(graph, 1, 5, fn x -> x + 5 end)
iex> Yog.Model.node(updated, 1)
5