aonyx_graph
A functional graph library for Gleam.
gleam add aonyx_graphFeatures
- Add, remove, and update nodes and edges
- List neighbors of a node, including incoming and outgoing edges
- Find paths between nodes
Example
import aonyx/graph
import aonyx/graph/edge
import aonyx/graph/node
import aonyx/graph/path/astar
import aonyx/graph/path/dijkstra
import gleam/dict
import gleam/float
import gleam/list
import gleam/option
import gleam/result
import gleam/set
import gleeunit/should
pub fn main() {
creating_and_modifying_a_graph()
|> path_finding()
path_finding_with_a_star()
graph_traversal_examples()
}
fn creating_and_modifying_a_graph() {
let g = graph.new()
let g =
[
node.new("A", option.None),
node.new("B", option.None),
node.new("C", option.None),
node.new("D", option.Some("Some value")),
// you can also add nodes with incoming or outgoing edges.
// the edges will be created automatically as well as the target nodes.
node.new("E", option.None)
|> node.with_incoming(["B"])
|> node.with_outgoing(["F"]),
]
|> list.fold(g, graph.insert_node)
g |> graph.get_nodes() |> list.length() |> should.equal(6)
let g =
[
edge.new("A", "B"),
edge.new("B", "C"),
edge.new("C", "A") |> edge.with_label("Some label"),
edge.new("A", "D") |> edge.with_weight(0.5),
edge.new("D", "F"),
// you can also add edges to non-existing nodes.
// the nodes will be created automatically.
edge.new("G", "H"),
]
|> list.fold(Ok(g), fn(g, e) { result.try(g, graph.try_insert_edge(_, e)) })
|> should.be_ok()
g |> graph.get_edges() |> list.length() |> should.equal(8)
g |> graph.get_nodes() |> list.length() |> should.equal(8)
// the graph now looks like this:
// ┌── C
// ▼ ▲
// A ► B ► E
// ▼ ▼
// D ────► F
//
// G ► H
g
|> graph.get_node("A")
|> should.be_ok()
|> node.get_neighbors_out()
|> should.equal(set.from_list(["B", "D"]))
g
|> graph.get_node("B")
|> should.be_ok()
|> node.get_neighbors_in()
|> should.equal(set.from_list(["A"]))
g
|> graph.get_node("B")
|> should.be_ok()
|> node.get_neighbors()
|> should.equal(set.from_list(["A", "C", "E"]))
g
}
fn path_finding(g: graph.Graph(String, _, _)) {
g
|> dijkstra.find_path("A", "F")
|> should.be_some()
|> should.equal(["A", "D", "F"])
g
|> dijkstra.find_path("B", "F")
|> should.be_some()
|> should.equal(["B", "E", "F"])
let g = g |> graph.remove_edge(edge.new("A", "D"))
g
|> dijkstra.find_path("A", "F")
|> should.be_some()
|> should.equal(["A", "B", "E", "F"])
let g = g |> graph.remove_node(node.NodeKey("E"))
g
|> dijkstra.find_path("A", "F")
|> should.be_none()
let g =
g
|> graph.get_node("D")
|> should.be_ok()
|> node.with_incoming(["A"])
|> node.with_outgoing(["G"])
|> graph.insert_node(g, _)
g
|> dijkstra.find_path("A", "H")
|> should.be_some()
|> should.equal(["A", "D", "G", "H"])
}
fn path_finding_with_a_star() {
// A* is a pathfinding algorithm that uses heuristics to find the shortest path in a graph.
// It is more efficient than Dijkstra's algorithm in many cases, especially when the graph is large and sparse.
// The A* algorithm uses a heuristic function to estimate the cost of reaching the goal from a given node.
// The heuristic function must be admissive, meaning it never overestimates the cost.
// A common heuristic function is the Euclidean distance between two points in a 2D space.
// In this example, we will use the Euclidean distance as the heuristic function for A*.
// The heuristic function takes two values (in this case, 2D coordinates) and returns the Euclidean distance between them.
let euclidean_distance = fn(a, b) {
let #(ax, ay) = a
let #(bx, by) = b
let dx = ax -. bx
let dy = ay -. by
let assert Ok(d) = float.square_root(dx *. dx +. dy *. dy)
d
}
let g =
[
node.new("A", #(0.0, 0.0)),
node.new("B", #(0.0, 1.0)),
node.new("C", #(0.5, 0.5)),
node.new("D", #(1.0, 1.0)),
]
|> list.fold(graph.new(), graph.insert_node)
|> Ok
// add edges with approximate weights (rounded up from the euclidean distance)
|> result.try(fn(g) {
g |> graph.try_insert_edge(edge.new("A", "B") |> edge.with_weight(1.0))
})
|> result.try(fn(g) {
g |> graph.try_insert_edge(edge.new("A", "C") |> edge.with_weight(0.8))
})
|> result.try(fn(g) {
g |> graph.try_insert_edge(edge.new("B", "D") |> edge.with_weight(1.0))
})
|> result.try(fn(g) {
g |> graph.try_insert_edge(edge.new("C", "D") |> edge.with_weight(0.8))
})
// this builds a graph with node values representing 2D coordinates:
// A
// |\
// | C
// | \
// B - D
let path =
g
|> should.be_ok()
|> astar.find_path("A", "D", euclidean_distance)
path
|> should.be_some()
|> should.equal(["A", "C", "D"])
}
fn graph_traversal_examples() {
// Create a simple tree-like graph for traversal examples
// A
// / \
// B C
// / \ \
// D E F
let g =
graph.new()
|> graph.insert_edge(edge.new("A", "B"), Nil)
|> graph.insert_edge(edge.new("A", "C"), Nil)
|> graph.insert_edge(edge.new("B", "D"), Nil)
|> graph.insert_edge(edge.new("B", "E"), Nil)
|> graph.insert_edge(edge.new("C", "F"), Nil)
// Example 1: Collect node keys for each depth level
let visit = fn(acc, node: node.Node(String, _), depth) {
graph.Continue(
acc
|> dict.upsert(depth, fn(x) {
case x {
option.None -> [node.key] |> set.from_list()
option.Some(xs) -> xs |> set.insert(node.key)
}
}),
)
}
let breadth_first_result =
g
|> graph.fold_breadth_first_until("A", dict.new(), visit)
|> should.be_ok()
// In breadth-first traversal, we visit nodes level by level
// A (level 0), then B, C (level 1), then D, E, F (level 2)
// The exact order within a level may vary depending on implementation
breadth_first_result
|> should.equal(
[
#(0, set.from_list(["A"])),
#(1, set.from_list(["B", "C"])),
#(2, set.from_list(["D", "E", "F"])),
]
|> dict.from_list(),
)
// Example 2: Collect node keys in depth-first order
let depth_first_result =
g
|> graph.fold_depth_first_until("A", dict.new(), visit)
|> should.be_ok()
// In depth-first traversal, we explore as far as possible along each branch before backtracking
// The exact order depends on implementation but could be A -> B -> D -> E -> C -> F
// The depth levels will be the same as in breadth-first traversal
depth_first_result
|> should.equal(
[
#(0, set.from_list(["A"])),
#(1, set.from_list(["B", "C"])),
#(2, set.from_list(["D", "E", "F"])),
]
|> dict.from_list(),
)
// Example 3: Early termination with Stop
// We'll stop when we find a node with key "C"
let stop_at_c = fn(acc, node: node.Node(String, _), _depth) {
case node.key {
"C" -> graph.Stop
_ -> graph.Continue([node.key, ..acc])
}
}
let partial_traversal =
g
|> graph.fold_breadth_first_until("A", [], stop_at_c)
// We should have only visited A and possibly B (depending on traversal order)
// but definitely not visited nodes after C
partial_traversal
|> should.be_ok()
|> list.contains("F")
|> should.be_false()
}