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

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

let graph =
  model.new(Directed)
  |> model.add_node(1, "apple")
  |> model.add_node(2, "banana")
  |> model.add_node(3, "apricot")
  |> model.add_edge(from: 1, to: 2, with: 1)
  |> model.add_edge(from: 2, to: 3, with: 2)

// Keep only nodes starting with 'a'
let filtered = transform.filter_nodes(graph, fn(s) {
  string.starts_with(s, "a")
})
// Result has nodes 1 and 3, edge 1->2 is removed (node 2 gone)

Use Cases

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

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

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(w) { w * 2 })
// Edges now have weights 20 and 40

Type Changes

Can change the edge weight type:

// Convert integer weights to floats
transform.map_edges(graph, int.to_float)

// Convert weights to labels
transform.map_edges(graph, fn(w) {
  case w < 10 {
    True -> "short"
    False -> "long"
  }
})

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

Example

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

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

Type Changes

Can change the node data type:

// Convert string node data to integers
transform.map_nodes(graph, fn(s) {
  case int.parse(s) {
    Ok(n) -> n
    Error(_) -> 0
  }
})

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

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

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