Finds shortest path using A* search algorithm.

Finds the shortest path from start node to target node using A* algorithm. The scorer function converts edge relations to numerical costs (weights), and the heuristic function estimates the cost from any node to the target. A* is typically faster than Dijkstra when a good heuristic is available.

Returns Ok with a list of node IDs representing the path (inclusive of both start and target), or Error if no path exists.

Examples

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_edge(new_edge(from: 0, to: 1) |> with_relation(5))
|> add_edge(new_edge(from: 1, to: 2) |> with_relation(3))
let assert Ok(path) = a_star(
  graph,
  from: 0,
  to: 2,
  using: fn(r) { int.to_float(r) },
  with: fn(id) { 0.0 }, // simple heuristic: estimate 0 to any node
)
// path is [0, 1, 2]

Graph Representation

0[A] --5--> 1[B] --3--> 2[C]

A* from 0 to 2: finds shortest path [0, 1, 2]

Adds an edge to the graph.

Adds the specified edge to the graph. If an edge with the same source, target, and relation already exists, the graph is returned unchanged. If the source or target nodes don’t exist, they will be created automatically.

Examples

let graph1 = new_graph()
add_node(new_node(0) |> with_value("A"))
add_node(new_node(1) |> with_value("B"))
let edge = new_edge(from: 0, to: 1) |> with_relation(5)
let graph2 = add_edge(graph1, edge)

Graph Representation

graph1: 0[A]    1[B]

graph2:  0[A] --5--> 1[B]

Adds a node to the graph.

If a node with the same ID already exists, it will be updated with the new node’s value. Any existing edges connected to the node ID are preserved.

Examples

import gleam/set

let node = new_node(0) |> with_value("A")
let graph = new_graph()
|> add_node(node)

Graph Representation

Before: {}
After:  {0[A]}

Adds a node to the graph and connects it to existing nodes.

This function adds a node and automatically creates edges from the specified source nodes to this node, and from this node to the specified target nodes. If a node with the same ID already exists, its connections are updated.

Examples

import gleam/set

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(2) |> with_value("C"))
let graph2 = add_node_connected(graph1,
  new_node(1) |> with_value("B"),
  from: set.from_list([0]),
  to: set.from_list([2]),
)
// Now node 1 has an incoming edge from 0 and an outgoing edge to 2

Graph Representation

graph1: 0[A]    2[C]

graph2:  0[A] --> 1[B] --> 2[C]

Performs a breadth-first search (BFS) on the graph.

Traverses the graph starting from the specified node, visiting nodes level by level (all neighbors before their neighbors). The callback is called for each visited node with the edge relation used to reach it and the node itself. The callback can return Continue to continue searching or Stop to stop early.

The edge_selector parameter allows choosing which edge to follow when multiple edges exist between the same pair of nodes. If None, any edge may be chosen.

Returns a tuple where the first element indicates whether traversal was stopped early (True) or completed (False), and the second element is the final accumulator.

Examples

import gleam/list
import gleaph/search.{Continue, Stop}
import gleam/option

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_node(new_node(3) |> with_value("D"))
|> add_node(new_node(4) |> with_value("E"))
|> add_node(new_node(5) |> with_value("F"))
|> add_edge(new_edge(from: 0, to: 1))
|> add_edge(new_edge(from: 0, to: 2))
|> add_edge(new_edge(from: 1, to: 3))
|> add_edge(new_edge(from: 1, to: 4))
|> add_edge(new_edge(from: 1, to: 5))
let #(stopped, nodes) = search.bfs(graph, start: 0, from: [], callback: fn(_rel, node, acc) {
  let ret = list.append(acc, [node.value])
  case node.id {
    4 -> Stop(ret)
    _ -> Continue(ret)
  }
}, using: option.None)
// stopped is `True`; nodes is [Some("A"), Some("B"), Some("C"), Some("D"), Some("E")]

Graph Representation

0[A] --> 1[B]
0[A] --> 2[C]
1[B] --> 3[D]
1[B] --> 4[E]
1[B] --> 5[F]

BFS starting from 0 visits: 0[A] → 1[B] → 2[C] → 3[D] → 4[E]

Performs a depth-first search (DFS) traversal of graph.

Traverses the graph starting from the specified node using DFS order, going as deep as possible before backtracking. The callback function is called for each visited node, receiving the edge relation used to reach the node, the node itself, and the current accumulator. The callback can return Continue to continue traversal or Stop to stop early.

The edge_selector parameter allows choosing which edge to follow when multiple edges exist between the same pair of nodes. If None, any edge may be chosen.

Returns a tuple where the first element indicates whether traversal was stopped early (True) or completed (False), and the second element is the final accumulator.

Examples

import gleaph/search.{Continue, Stop}
import gleam/option

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_node(new_node(3) |> with_value("D"))
|> add_node(new_node(4) |> with_value("E"))
|> add_edge(new_edge(from: 0, to: 1))
|> add_edge(new_edge(from: 0, to: 4))
|> add_edge(new_edge(from: 1, to: 2))
|> add_edge(new_edge(from: 1, to: 3))
let #(stopped, nodes) = dfs(graph, start: 0, from: [], callback: fn(_rel, node, acc) {
  let ret = list.append(acc, [node.value])
  case node.id {
    3 -> Stop(ret)
    _ -> Continue(ret)
}
}, using: option.None)
// stopped is `True`, nodes is [Some("A"), Some("B"), Some("C"), Some("D")]

Graph Representation

0[A] --> 1[B]
0[A] --> 4[E]
1[B] --> 2[C]
1[B] --> 3[D]

DFS from 0 visits: 0[A] → 1[B] → 2[C] → 3[D]

Computes difference of two graphs.

Returns a graph containing the union of nodes in in both input graphs, and the difference of their edges. The combiner determines how vales of nodes with identical id shall be combined.

Examples

import gleam/option

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_edge(new_edge(from: 0, to: 1))
|> add_edge(new_edge(from: 1, to: 2))

let graph2 = new_graph()
|> add_node(graph2, new_node(1) |> with_value("B"))
|> add_edge(graph2, new_edge(from: 1, to: 2))

// Remove nodes that exist in both graphs
let diff = difference(graph1, graph2, with: fn(_, _) { None })
// diff contains only node 0[A]

Graph Representation

graph1:
0[A] --> 1[B] --> 2[C]

graph2:
1[B] --> 2[C]

diff:
0[A] --> 1[B]
2[C]

Finds shortest path using Dijkstra’s algorithm.

Finds the shortest path from start node to target node using Dijkstra’s algorithm. The scorer function converts edge relations to numerical costs (weights). Returns Ok with a list of node IDs representing the path (inclusive of both start and target), or Error if no path exists.

Note: This is a wrapper around a_star with zero heuristic function.

Examples

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_edge(new_edge(from: 0, to: 1) |> with_relation(5))
|> add_edge(new_edge(from: 1, to: 2) |> with_relation(3))
let assert Ok(path) = djikstra(graph, from: 0, to: 2, using: fn(r) {
  int.to_float(r)
})
// path is [0, 1, 2] (total cost: 8)

Graph Representation

0[A] --5--> 1[B] --3--> 2[C]

Dijkstra from 0 to 2: shortest path is [0, 1, 2] with total weight 8

Computes the disjoint union of two graphs.

Combines two graphs into one, assuming they have no overlapping nodes (disjoint). All nodes and edges from both graphs are included in the result. If nodes with the same ID exist in both graphs, they will be merged.

Examples

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1))

let graph2 = new_graph()
|> add_node(new_node(0) |> with_value("A'"))
|> add_node(new_node(1) |> with_value("B'"))
|> add_edge(new_edge(from: 0, to: 1))

let combined = disjoint_union(graph1, graph2)

Graph Representation

graph1:     Graph 2:     Result:
0[A] --> 1[B]

graph2:
0[A'] --> 1[B'] 

combined:
0[A] --> 1[B]
2[A'] --> 3[B']

Folds over all edge relations in the graph.

Applies the given function to each edge’s relation, accumulating a result. The function receives the current accumulator, source node, target node, and the edge’s relation (wrapped in Option), and returns the new accumulator.

Examples

import gleam/int

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1) |> with_relation(5))
let sum = fold_relations(graph, 0, fn(acc, from, to, rel) {
  acc + option.unwrap(rel, 0)
})
// sum is 5

Graph Representation

0[A] --5--> 1[B]
0[A] --3--> 2[C]

fold_relations(graph, +): 5 + 3 = 8

Folds over all node values in the graph.

Applies the given function to each node’s value, accumulating a result. The function receives the current accumulator and the node’s value (wrapped in Option), and returns the new accumulator value.

Examples

import gleam/int

let graph = new_graph()
|> add_node(new_node(0) |> with_value(10))
|> add_node(new_node(1) |> with_value(20))
|> add_node(new_node(2)) // no value
let sum = fold_values(graph, 0, fn(acc, val) {
  acc + option.unwrap(val, 0)
})
// sum: 30

Graph Representation

0[10] --> 1[20] --> 2[]

fold_values(graph, +): 10 + 20 + 0 = 30

Gets all directed edges from a source node to a target node.

Returns a set of edges that go from the source node to the target node. Multiple edges can exist between the same pair of nodes with different relations. If no edges exist, returns an error.

Examples

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1) |> with_relation(5))
let assert Ok(edges) = get_directed_edges(graph, from: 0, to: 1)

Graph Representation

0[A] --5--> 1[B]
0[A] --3--> 1[B]

get_directed_edges(0, 1): Ok({Edge(0->1, 5), Edge(0->1, 3)})
get_directed_edges(1, 0): Error(Nil)

Gets all disconnected nodes in the graph.

Returns a set of nodes that have no incoming or outgoing edges. These are isolated nodes that are not connected to any other nodes.

Examples

import gleam/set

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_edge(new_edge(from: 0, to: 1))
let disconnected = get_disconnected_nodes(graph)
// disconnected contains node 2[C]

Graph Representation

0[A] --> 1[B]    2[C]

disconnected: {2[C]}

Gets all edges in the graph as a set.

Returns a set containing all edges currently in the graph.

Examples

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1) |> with_relation(5))
let edges = get_edges(graph)
// edges contains the edge from 0 to 1 with relation 5

Graph Representation

0[A] --5--> 1[B]

edges: {Edge(from: 0, to: 1, relation: Some(5))}

Gets all incoming edges of a node.

Returns a set of all edges that point to the specified node. If the node doesn’t exist, returns an error. Each edge in the set will have the target node ID equal to the specified node.

Examples

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_edge(new_edge(from: 0, to: 1) |> with_relation(5))
|> add_edge(new_edge(from: 2, to: 1) |> with_relation(3))
let assert Ok(incoming) = get_incoming_edges(graph, 1)
// incoming contains edges from 0->1 and 2->1

Graph Representation

0[A] --5--> 1[B]
2[C] --3--> 1[B]

get_incoming_edges(graph, 1): Ok({Edge(0->1, 5), Edge(2->1, 3)})
get_incoming_edges(graph, 0): Ok({})  (no incoming edges)

Gets the indegree (number of incoming edges) of a node.

Returns the count of edges pointing to the specified node. If the node doesn’t exist, returns an error.

Examples

let graph = new_graph()
|> add_node(graph, new_node(0) |> with_value("A"))
|> add_node(graph, new_node(1) |> with_value("B"))
|> add_edge(graph, new_edge(from: 0, to: 1))
let assert Ok(indeg) = get_indegree(graph, 1)
// indeg is 1 (one edge from node 0)

Graph Representation

0[A] --> 1[B]

get_indegree(graph, 0): Ok(0)
get_indegree(graph, 1): Ok(1)

Gets a specific node by its ID.

Returns the node with the given ID, or an error if the node doesn’t exist.

Examples

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
let assert Ok(node) = get_node(graph, 0)
// node is 0[A]

Graph Representation

0[A] --> 1[B] --> 2[C]

get_node(graph, 0): Ok(0[A])
get_node(graph, 3): Error(Nil)

Gets all nodes in the graph as a set.

Returns a set containing all nodes currently in the graph.

Examples

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
let nodes = get_nodes(graph)

Graph Representation

Graph: 0[A] --> 1[B] --> 2[C]

nodes: {0[A], 1[B], 2[C]}

Gets the outdegree (number of outgoing edges) of a node.

Returns the count of edges originating from the specified node. If the node doesn’t exist, returns an error.

Examples

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1))
let assert Ok(outdeg) = get_outdegree(graph, 0)
// outdeg is 1 (one edge to node 1)

Graph Representation

0[A] --> 1[B]

get_outdegree(graph, 0): Ok(1)
get_outdegree(graph, 1): Ok(0)

Gets all outgoing edges of a node.

Returns a set of all edges that originate from the specified node. If the node doesn’t exist, returns an error. Each edge in the set will have the source node ID equal to the specified node.

Examples

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_edge(new_edge(from: 0, to: 1) |> with_relation(5))
|> add_edge(new_edge(from: 0, to: 2) |> with_relation(3))
let assert Ok(outgoing) = get_outgoing_edges(graph, 0)
// outgoing contains edges from 0->1 and 0->2

Graph Representation

0[A] --5--> 1[B]
0[A] --3--> 2[C]

get_outgoing_edges(graph, 0): Ok({Edge(0->1, 5), Edge(0->2, 3)})
get_outgoing_edges(graph, 1): Ok({})  (no outgoing edges)

Gets all predecessor nodes of a node.

Returns a set of all nodes that have edges pointing to the specified node. Predecessors are nodes from which you can reach the specified node by following an edge. If the node doesn’t exist, returns an error.

Examples

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_edge(new_edge(from: 0, to: 1))
|> add_edge(new_edge(from: 2, to: 1))
let assert Ok(preds) = get_predecessors(graph, 1)
// preds contains nodes 0[A] and 2[C]

Graph Representation

0[A] --> 1[B]
2[C] --> 1[B]

get_predecessors(graph, 1): Ok({0[A], 2[C]})
get_predecessors(graph, 0): Ok({})  (no predecessors)

Gets all successor nodes of a node.

Returns a set of all nodes that can be reached from the specified node by following an edge. Successors are nodes to which the specified node has edges pointing. If the node doesn’t exist, returns an error.

Examples

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_edge(new_edge(from: 0, to: 1))
|> add_edge(new_edge(from: 0, to: 2))
let assert Ok(succs) = get_successors(graph, 0)
// succs contains nodes 1[B] and 2[C]

Graph Representation

0[A] --> 1[B]
0[A] --> 2[C]

get_successors(graph, 0): Ok({1[B], 2[C]})
get_successors(graph, 1): Ok({})  (no successors)

Checks if the graph contains any loops (self-edges).

Returns True if the graph has at least one edge where the source and target nodes are the same (a loop). Returns False if no such edges exist.

Examples

// Graph with a loop
let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_edge(new_edge(from: 0, to: 0) |> with_relation(5))
let has_loop1 = has_loop(graph1)
// has_loop1 is True

// Graph without a loop
let graph2 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1))
let has_loop2 = has_loop(graph2)
// has_loop2 is False

Graph Representation

graph1 (has loop):
  0[A] --5--> 0[A]  (loop)
  has_loop returns True

graph2 (no loop):
  0[A] --> 1[B]
  has_loop returns False

Computes intersection of two graphs.

Returns a graph containing the union of nodes in both input graphs, and the intersection of their edges. The combiner determines how the values of nodes with identical IDs shall be combined.

Examples

import gleam/option

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_edge(new_edge(from: 0, to: 1))
|> add_edge(new_edge(from: 1, to: 2))

let graph2 = new_graph()
|> add_node(new_node(1) |> with_value("B2"))
|> add_node(new_node(2) |> with_value("C2"))
|> add_node(new_node(3) |> with_value("D"))
|> add_edge(new_edge(from: 1, to: 2))

// Combine values of common nodes
let inter = intersection(graph1, graph2, with: fn(v1, v2) {
  option.map2(v1, v2, fn(s1, s2) { s1 <> "&" <> s2 })
})
// inter contains nodes 1[B&B2] and 2[C&C2] with edge between them

Graph Representation

graph1:
0[A] --> 1[B] --> 2[C]

graph2:
1[B2] --> 2[C2] --> 3[D]

inter:
0[A]
1[B&B2] --> 2[C&C2]
3[D]

Checks if graph is acyclic (contains no cycles).

Returns True if graph has no cycles, False otherwise. A directed graph is acyclic if there is no way to start from a node and follow a sequence of edges to return to that node.

Examples

// Acyclic graph
let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1))
let is_dag1 = is_acyclic(graph1)
// is_dag1 is True

// Graph with cycle
let graph2 = add_edge(graph1, new_edge(from: 1, to: 0))
let is_dag2 = is_acyclic(graph2)
// is_dag2 is False

Graph Representation

graph1 (acyclic):
  0[A] --> 1[B]

graph2 (cyclic):
  0[A] --> 1[B] --> 0[A]

Checks if graph is a tree.

Returns True if graph is acyclic AND has exactly (n-1) edges where n is the number of nodes. For a graph to be a tree, it must be connected and acyclic.

Examples

// Tree
let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_edge(new_edge(from: 0, to: 1))
|> add_edge(new_edge(from: 1, to: 2))
let is_tree1 = is_tree(graph1)
// is_tree1 is `True` (acyclic, 3 nodes, 2 edges)

// Not a tree (disconnected)
let graph2 = new_graph()
|> add_node(graph2, new_node(0) |> with_value("A"))
|> add_node(graph2, new_node(1) |> with_value("B"))
let is_tree2 = is_tree(graph2)
// is_tree2 is False (disconnected, 2 nodes, 0 edges)

Graph Representation

graph1 (tree):
  0[A] --> 1[B] --> 2[C]
  is_tree returns `True`

graph2 (disconnected):
  0[A]    1[B]
  is_tree returns `False`

Checks if an undirected edge exists between two nodes.

Returns True if there are edges in both directions between the two nodes (i.e., at least one edge from source to target AND at least one edge from target to source). Returns False if only one direction exists. Returns an error if no edges exist between the nodes.

Examples

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1))
let assert Ok(result) = is_undirected_edge(graph, from: 0, to: 1)
// result is False (only one direction)

Graph Representation

0[A] --> 1[B]      is_undirected_edge(0, 1): Ok(False)

0[A] <---> 1[B]    is_undirected_edge(0, 1): Ok(True)

0[A]     1[B]      is_undirected_edge(0, 1): Error(Nil)

Transforms the relations of all edges in the graph.

Applies the given mapping function to each edge’s relation. The mapping function receives the source node, target node, and the current relation (wrapped in Option) and returns a new relation (also wrapped in Option). If the function returns None, the edge will have no relation. This can also change the type of relations stored in the graph.

Examples

import gleam/option

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1) |> with_relation(5))
let graph2 = map_relations(graph1, with: fn(from, to, rel) {
  option.map(rel, fn(n) { n * 2 })
})
// All relations are now doubled

Graph Representation

graph1: 0[A] --5--> 1[B]

graph2:  0[A] --10--> 1[B]

Transforms the values of all nodes in the graph.

Applies the given mapping function to each node’s value. The mapping function receives the current value (wrapped in Option) and returns a new value (also wrapped in Option). If the function returns None, the node will have no value. This can also change the type of values stored in the graph.

Examples

import gleam/option

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
let graph2 = map_values(graph1, with: fn(val) {
  option.map(val, fn(s) { s <> "!" })
})
// All values now have "!" appended

Graph Representation

graph1: 0[A] --> 1[B]     2[C]

graph2:  0[A!] --> 1[B!]   2[C!]

Creates a new directed edge from a source node to a target node.

An edge represents a relationship or connection between two nodes in the graph. The edge is directed, meaning it goes from the source to the target. Edges can optionally store a relation of any type.

Examples

let edge = new_edge(from: 0, to: 1)
// edge goes from node 0 to node 1, with no relation

Graph Representation

0 --> 1

Creates a new empty graph.

The graph can store nodes with values of type value_t and edges with relations of type relation_t. Initially, the graph contains no nodes or edges.

Examples

let graph = new_graph()
// graph is empty

Graph Representation

{}

Creates a new node with the given ID and no associated value.

A node is a basic building block of a graph, identified by a unique ID. Nodes can optionally store a value of any type.

Examples

let node = new_node(0)
// node has ID 0 and no value

Graph Representation

0

Removes all disconnected nodes from the graph.

Removes nodes that have no incoming or outgoing edges. This cleans up isolated nodes from the graph.

Examples

import gleam/set

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_edge(new_edge(from: 0, to: 1))
let graph2 = prune_disconnected_nodes(graph)
// node 2[C] is removed

Graph Representation

graph1: 0[A] --> 1[B]    2[C]

graph2:  0[A] --> 1[B]

Removes an edge from the graph.

Removes the specified edge from the graph. If the edge doesn’t exist, the graph is returned unchanged.

Examples

let graph = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
let edge = new_edge(from: 0, to: 1)
let graph1 = add_edge(graph, edge)
let graph2 = remove_edge(graph, edge)

Graph Representation

graph1: 0[A] --> 1[B]

graph2:  0[A]    1[B]

Removes all loops (self-edges) from the graph.

Loops are edges where the source and target are the same node. This function removes all such edges from the graph.

Examples

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 0) |> with_relation(5))
|> add_edge(new_edge(from: 0, to: 1))
let graph2 = remove_loops(graph)
// The loop on 0 is removed

Graph Representation

graph1: 0[A] --5--> 0[A]  (loop)
        0[A] ---------> 1[B]

graph2: 0[A] ---------> 1[B]

Removes a node from the graph.

Removes the specified node and all edges connected to it. If the node doesn’t exist, the graph is returned unchanged.

Examples

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1))
let graph2 = remove_node(graph1, 0)
// node 0 and the edge are removed

Graph Representation

graph1: 0[A] --> 1[B]

graph2:  1[B]

Reverses a single edge in the graph.

Creates a new graph where the specified edge’s direction is flipped. If the edge goes from node A to node B, it will now go from node B to node A. The edge’s relation is preserved. If the edge doesn’t exist, returns an error.

Examples

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1) |> with_relation(5))
let edge = new_edge(from: 0, to: 1) |> with_relation(5)
let assert Ok(graph2) = reverse(graph1, edge)
// Now the edge goes from 1 to 0

Graph Representation

graph1: 0[A] --5--> 1[B]

graph2:  0[A] <--5-- 1[B]

Reverses all edges in the graph.

Creates a new graph where all edge directions are flipped. If an edge goes from node A to node B, it will now go from node B to node A. Node values and edge relations are preserved.

Examples

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1) |> with_relation(5))
let graph2 = reverse_all(graph1)
// Now edge goes from 1 to 0

Graph Representation

graph1: 0[A] --5--> 1[B]

graph2:  0[A] <--5-- 1[B]

Performs topological sort on the graph.

Returns a linear ordering of nodes such that for every directed edge from node A to node B, node A comes before node B in the ordering. This is only possible for Directed Acyclic Graphs (DAGs). If the graph contains cycles, returns an error.

Examples

// Acyclic graph
let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_node(new_node(2) |> with_value("C"))
|> add_edge(new_edge(from: 0, to: 1))
|> add_edge(new_edge(from: 1, to: 2))
let assert Ok(ordering) = topological_sort(graph1)
// ordering is [0, 1, 2]

// Graph with cycle
let graph2 = add_edge(graph1, new_edge(from: 2, to: 0))
let assert Error(Nil) = topological_sort(graph2)

Graph Representation

graph1 (acyclic):
  0[A] --> 1[B] --> 2[C]
  topological order: Ok([0, 1, 2])

graph2 (cyclic):
  0 --> 1 --> 2 --> 0  (cycle!)
  topological order: Error(Nil)

Transforms multiedges in the graph.

Applies the transformer function to each multiedge. The transformer receives the source node, target node, and all relations between them, and returns a new set of edges. This is useful for operations like removing duplicate edges or merging multiple edges.

Examples

import gleam/set
import gleam/int
import gleam/list

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1) |> with_relation(3))
|> add_edge(new_edge(from: 0, to: 1) |> with_relation(5))
// Keep only the edge with the minimum relation
let graph2 = transform_edges(graph, by: fn(from, to, edges) {
  let relations = set.map(edges, fn(e) { e.relation })
  let min_rel = list.sort(set.to_list(relations), int.compare) |> list.first
  case min_rel {
    Ok(r) -> set.from_list([new_edge(from: from.id, to: to.id) |> with_relation(r)])
    Error(_) -> set.new()
  }
})

Graph Representation

graph1: 0[A] --3--> 1[B]
        0[A] --5--> 1[B]

graph2:  0[A] --3--> 1[B]  (keeps minimum)

Computes the union of two graphs.

Combines two graphs into one, merging nodes that exist in both graphs. The combiner function determines how to merge node values when the same node ID exists in both graphs. Edges from both graphs are included.

Examples

import gleam/option

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
|> add_node(new_node(1) |> with_value("B"))
|> add_edge(new_edge(from: 0, to: 1) |> with_relation(3))

let graph2 = new_graph()
|> add_node(new_node(1) |> with_value("B2"))
|> add_node(new_node(2) |> with_value("C"))
|> add_edge(new_edge(from: 1, to: 2) |> with_relation(5))

// Combine node 1 values by concatenating
let combined = union(graph1, graph2, with: fn(v1, v2) {
  option.map2(v1, v2, fn(s1, s2) { s1 <> "+" <> s2 })
})

Graph Representation

graph1:
0[A] --3--> 1[B]

graph2:
1[B2] --5--> 2[C]

combined:
0[A] --3--> 1[B+B2] --5--> 2[C]

Updates the value of a specific node.

Applies the given modifier function to the node’s current value. The modifier receives the current value (wrapped in Option) and returns a new value (also wrapped in Option). If the node doesn’t exist, the graph is returned unchanged.

Examples

import gleam/option

let graph1 = new_graph()
|> add_node(new_node(0) |> with_value("A"))
let graph2 = update_node_value(graph1, 0, with: fn(val) {
  option.map(val, fn(s) { s <> "!" })
})
// node 0 now has value "A!"

Graph Representation

graph1: 0[A] --> 1[B]

graph2:  0[A!] --> 1[B]

Associates a relation with an edge.

This function takes an existing edge and returns a new edge with the same source and target but with an associated relation. The original edge is not modified.

Examples

let edge = new_edge(from: 0, to: 1)
|> with_relation(5)
// edge goes from node 0 to node 1 with relation 5

Graph Representation

0 --5--> 1

Associates a value with a node.

This function takes an existing node and returns a new node with the same ID but with an associated value. The original node is not modified.

Examples

let node = new_node(0)
|> with_value("Hello")
// node has ID 0 and value "Hello"

Graph Representation

0[Hello]