yog - v5.1.1

yog/multi/model

⚠️ Experimental Module

This module is experimental and provides minimal, working functionality. The implementation is functional but may not be fully optimized for performance.

Expected changes:

Use with caution in production environments.

Types

EdgeId

</>

Unique identifier for an edge in a multigraph. Unlike node IDs, edge IDs are assigned automatically by add_edge.

pub type EdgeId =
  Int

MultiGraph

</>

A multigraph that can hold multiple (parallel) edges between the same pair of nodes. Both directed and undirected variants are supported.

  • node_data: Data stored at each node
  • edge_data: Data (weight) stored on each edge

The internal representation keeps three indices:

  • edges: EdgeId → #(from, to, data) – canonical edge store
  • out_edge_ids: NodeId → List(EdgeId) – outgoing edges per node
  • in_edge_ids: NodeId → List(EdgeId) – incoming edges per node
pub type MultiGraph(node_data, edge_data) {
  MultiGraph(
    kind: model.GraphType,
    nodes: dict.Dict(Int, node_data),
    edges: dict.Dict(Int, #(Int, Int, edge_data)),
    out_edge_ids: dict.Dict(Int, List(Int)),
    in_edge_ids: dict.Dict(Int, List(Int)),
    next_edge_id: Int,
  )
}

Constructors

Values

add_edge

</> 
pub fn add_edge(
  graph: MultiGraph(n, e),
  from src: Int,
  to dst: Int,
  with data: e,
) -> #(MultiGraph(n, e), Int)

Adds an edge from from to to with the given data.

Returns #(updated_graph, new_edge_id) so the caller can reference this specific edge later (e.g. for remove_edge).

For undirected graphs a single EdgeId is issued and the reverse direction is indexed automatically — removing by ID removes both directions.

Example

let graph = multi.directed()
let #(graph, e1) = multi.add_edge(graph, from: 1, to: 2, with: "flight")
let #(graph, e2) = multi.add_edge(graph, from: 1, to: 2, with: "train")
// e1 != e2 — two independent parallel edges

add_node

</> 
pub fn add_node(
  graph: MultiGraph(n, e),
  id: Int,
  data: n,
) -> MultiGraph(n, e)

Adds a node with the given ID and data. If the node already exists its data is replaced (edges are unaffected).

all_edge_ids

</> 
pub fn all_edge_ids(graph: MultiGraph(n, e)) -> List(Int)

Returns all edge IDs in the graph.

all_nodes

</> 
pub fn all_nodes(graph: MultiGraph(n, e)) -> List(Int)

Returns all node IDs in the graph.

directed

</> 
pub fn directed() -> MultiGraph(n, e)

Creates a new, empty directed multigraph.

edges_between

</> 
pub fn edges_between(
  graph: MultiGraph(n, e),
  from src: Int,
  to dst: Int,
) -> List(#(Int, e))

Returns all parallel edges between from and to as List(#(EdgeId, edge_data)).

has_edge

</> 
pub fn has_edge(graph: MultiGraph(n, e), edge_id: Int) -> Bool

Returns True if an edge with this ID exists in the graph.

in_degree

</> 
pub fn in_degree(graph: MultiGraph(n, e), id: Int) -> Int

Returns the in-degree of a node (number of incoming edges).

new

</> 
pub fn new(graph_type: model.GraphType) -> MultiGraph(n, e)

Creates a new, empty multigraph of the given type.

order

</> 
pub fn order(graph: MultiGraph(n, e)) -> Int

Returns the number of nodes (graph order).

out_degree

</> 
pub fn out_degree(graph: MultiGraph(n, e), id: Int) -> Int

Returns the out-degree of a node (number of outgoing edges). For undirected graphs this equals the total degree.

predecessors

</> 
pub fn predecessors(
  graph: MultiGraph(n, e),
  id: Int,
) -> List(#(Int, Int, e))

Returns all incoming edges to id as List(#(NodeId, EdgeId, e)).

remove_edge

</> 
pub fn remove_edge(
  graph: MultiGraph(n, e),
  edge_id: Int,
) -> MultiGraph(n, e)

Removes a single edge by its EdgeId. For undirected graphs both direction-index entries are removed.

remove_node

</> 
pub fn remove_node(
  graph: MultiGraph(n, e),
  id: Int,
) -> MultiGraph(n, e)

Removes a node and all edges connected to it.

size

</> 
pub fn size(graph: MultiGraph(n, e)) -> Int

Returns the total number of edges (graph size). For undirected graphs each physical edge is counted once.

successors

</> 
pub fn successors(
  graph: MultiGraph(n, e),
  id: Int,
) -> List(#(Int, Int, e))

Returns all outgoing edges from id as List(#(NodeId, EdgeId, e)).

to_simple_graph

</> 
pub fn to_simple_graph(
  graph: MultiGraph(n, e),
  combine_fn: fn(e, e) -> e,
) -> model.Graph(n, e)

Collapses the multigraph into a simple yog/model.Graph by combining parallel edges with combine_fn(existing, new).

Example

// Keep minimum weight among parallel edges
multi.to_simple_graph(mg, fn(a, b) { int.min(a, b) })

to_simple_graph_min_edges

</> 
pub fn to_simple_graph_min_edges(
  graph: MultiGraph(n, e),
  compare: fn(e, e) -> order.Order,
) -> model.Graph(n, e)

Collapses the multigraph by keeping the minimum weight among parallel edges.

Use this for: Shortest path, MST, and any algorithm where only the best (lowest cost) edge between two nodes matters.

Example

// Dijkstra's on multigraph
graph
|> multi.to_simple_graph_min_edges(int.compare)
|> dijkstra.shortest_path(from: 1, to: 5, ...)

// MST on multigraph  
graph
|> multi.to_simple_graph_min_edges(int.compare)
|> mst.kruskal(with_compare: int.compare)

to_simple_graph_sum_edges

</> 
pub fn to_simple_graph_sum_edges(
  graph: MultiGraph(n, e),
  add: fn(e, e) -> e,
) -> model.Graph(n, e)

Collapses the multigraph by summing weights of parallel edges.

Use this for: Min-cut, max-cut, max-flow, and any algorithm where all parallel edges contribute additively to the total capacity/cost.

Example

// S-T min cut / max flow on multigraph
graph
|> multi.to_simple_graph_sum_edges(int.add)
|> max_flow.edmonds_karp(from: source, to: sink, ...)

// Global min cut on multigraph
graph
|> multi.to_simple_graph_sum_edges(int.add)
|> min_cut.global_min_cut()

undirected

</> 
pub fn undirected() -> MultiGraph(n, e)

Creates a new, empty undirected multigraph.

✨ Search Document