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

let graph =
  model.new(Undirected)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_edge(from: 1, to: 2, with: 1)

let comp = transform.complement(graph, default_weight: 1)
// Original: 1-2 connected, 1-3 and 2-3 not
// Complement: 1-3 and 2-3 connected, 1-2 not

Use Cases

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

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

let graph =
  model.new(Undirected)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_edge(from: 1, to: 2, with: 5)
  |> model.add_edge(from: 2, to: 3, with: 10)

let contracted = transform.contract(
  in: graph,
  merge: 1,
  with: 2,
  combine_weights: int.add,
)
// Result: nodes [1, 3], edge 1-3 with weight 10
// Node 2 is merged into node 1

Combining Weights

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

// Before: a-[5]->c, b-[10]->c
let contracted = transform.contract(
  in: graph,
  merge: a,
  with: b,
  combine_weights: int.add,
)
// After: a-[15]->c (5 + 10)

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)

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

let graph =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_edge(from: 1, to: 2, with: 5)
  |> model.add_edge(from: 1, to: 3, with: 15)
  |> model.add_edge(from: 2, to: 3, with: 3)

// Keep only edges with weight >= 10
let heavy = transform.filter_edges(graph, fn(_src, _dst, w) { w >= 10 })
// Result: edges [1->3 (15)], edges 1->2 and 2->3 removed

Use Cases

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

Creates a new graph containing only the nodes that satisfy the predicate.

Nodes are filtered based on both their ID and their associated data. Removing a node automatically removes all of its incident edges (both inbound and outbound).

Time Complexity: O(V + E)

Use Cases

• Filter nodes by ID range or specific identifiers
• Complex filtering requiring both identity and data
• Efficiently removing common nodes between two graphs

Transforms edge weights using a function, preserving graph structure.

This is a functor-like operation that applies a function to every edge’s weight while keeping all nodes and the graph topology unchanged. The transformation function receives the source node ID, destination node ID, and the edge weight.

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

Example

let graph =
  model.new(Directed)
  |> model.add_edge(from: 1, to: 2, with: 10)
  |> model.add_edge(from: 2, to: 3, with: 20)

// Double all weights
let doubled = transform.map_edges(graph, fn(_u, _v, w) { w * 2 })
// Edges now have weights 20 and 40

Accessing Identifiers

The function can use endpoint identifiers to calculate new weights:

// Include path context in edge data
let result = transform.map_edges(graph, fn(u, v, _w) {
  int.to_string(u) <> "->" <> int.to_string(v)
})

Transforms node data using a function, preserving graph structure.

This is a functor-like operation that applies a function to every node’s data while keeping all edges and the graph structure unchanged. The transformation function receives both the NodeId and the node data.

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

Example

let graph =
  model.new(Directed)
  |> model.add_node(1, "alice")
  |> model.add_node(2, "bob")

let uppercased = transform.map_nodes(graph, fn(_id, name) { string.uppercase(name) })
// Nodes now contain "ALICE" and "BOB"

Accessing Identifiers

The function can use the node ID to calculate new values:

// Prefix node values with their IDs
transform.map_nodes(graph, fn(id, name) {
  int.to_string(id) <> ": " <> name
})

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

let base =
  model.new(Directed)
  |> model.add_node(1, "Original")
  |> model.add_edge(from: 1, to: 2, with: 10)
  |> model.add_edge(from: 1, to: 3, with: 15)

let other =
  model.new(Directed)
  |> model.add_node(1, "Updated")
  |> model.add_edge(from: 1, to: 4, with: 20)
  |> model.add_edge(from: 2, to: 3, with: 25)

let merged = transform.merge(base, other)
// Node 1 has "Updated" (from other)
// Node 1 has edges to: 2, 3, and 4 (all edges combined)
// Node 2 has edge to: 3

Use Cases

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

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

let graph =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_node(4, "D")
  |> model.add_edge(from: 1, to: 2, with: 10)
  |> model.add_edge(from: 2, to: 3, with: 20)
  |> model.add_edge(from: 3, to: 4, with: 30)

// Extract only nodes 2 and 3
let sub = transform.subgraph(graph, keeping: [2, 3])
// Result has nodes 2, 3 and edge 2->3
// Edges 1->2 and 3->4 are removed (endpoints outside subgraph)

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

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

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

let undirected =
  model.new(Undirected)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_edge(from: 1, to: 2, with: 10)

let directed = transform.to_directed(undirected)
// Has edges: 1->2 and 2->1 (both with weight 10)

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

Example

let directed =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_edge(from: 1, to: 2, with: 10)
  |> model.add_edge(from: 2, to: 1, with: 20)

// When both directions exist, keep the smaller weight
let undirected = transform.to_undirected(directed, resolve: int.min)
// Edge 1-2 has weight 10 (min of 10 and 20)

// One-directional edges get mirrored automatically
let directed =
  model.new(Directed)
  |> model.add_edge(from: 1, to: 2, with: 5)

let undirected = transform.to_undirected(directed, resolve: int.min)
// Edge exists in both directions with weight 5

Computes the transitive closure of a graph.

The transitive closure adds edges between all pairs of nodes where a path exists in the original graph. If u can reach v through any path, the closure will have a direct edge u -> v.

The merge_fn is used to combine edge weights when multiple paths exist between the same pair of nodes.

Complexity:

• For DAGs: O(V × E) using topological sort
• For general graphs: O(V × (V + E)) using multiple traversals

Example

// Original edges: A->B (weight 2), B->C (weight 3)
// Closure adds: A->C (weight 5 = 2+3)
let closure = transform.transitive_closure(graph, int.add)

Computes the transitive reduction of a graph.

The transitive reduction removes all edges that are redundant - i.e., edges u -> v where there exists an indirect path from u to v through other nodes.

Note: For graphs with cycles (non-DAGs), the transitive reduction is not always unique and can be more complex to compute. This implementation focuses on the DAG case.

Time Complexity: O(V × E)

Example

// Original: A->B, B->C, A->C (A->C is implied by A->B->C)
// Reduction removes: A->C
// Result: A->B, B->C
let minimal = transform.transitive_reduction(graph, int.add)

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 that makes transposing large graphs extremely fast.

Time Complexity: O(1)

Property: transpose(transpose(G)) = G

Example

let graph =
  model.new(Directed)
  |> model.add_edge(from: 1, to: 2, with: 10)
  |> model.add_edge(from: 2, to: 3, with: 20)

let reversed = transform.transpose(graph)
// Now has edges: 2->1 and 3->2

Use Cases

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

Updates a specific edge’s weight/metadata safely.

Ensures both in_edges and out_edges stay in sync. Properly handles undirected graphs by updating both directions.

If either node src or dst does not exist, the graph is returned unchanged.

Time Complexity: O(1)

Example

let graph =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_edge(1, 2, 10)

let updated = transform.update_edge(graph, 1, 2, 0, fn(w) { w + 5 })
// Edge 1->2 now has weight 15

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

Similar to dict.upsert, but specialized for graphs. If the node doesn’t exist, it is created with the default value.

Time Complexity: O(1)

Example

let graph = model.new(Directed) |> model.add_node(1, 100)
let updated = transform.update_node(graph, 1, 0, fn(x) { x + 50 })
// Node 1 now has data 150