Unified facade for multigraph operations.
A multigraph allows multiple (parallel) edges between the same pair of nodes.
This module provides creation, modification, query, traversal, conversion, and algorithmic
analysis for multigraphs by delegating to specialized submodules (Yog.Multi.Model,
Yog.Multi.Traversal, Yog.Multi.Eulerian).
Multigraph Representation & Edge IDs
Unlike simple graphs where edges are uniquely identified by their {from, to} endpoints,
multigraph edges are assigned unique sequential non-negative integer EdgeId identifiers
starting from 0.
Adding an edge via add_edge/4 returns a {updated_graph, edge_id} tuple:
iex> multi = Yog.Multi.directed()
iex> {multi, e1} = Yog.Multi.add_edge(multi, :a, :b, "route 1")
iex> {multi, e2} = Yog.Multi.add_edge(multi, :a, :b, "route 2")
iex> Yog.Multi.edge_count(multi, :a, :b)
2
iex> e1 != e2
trueCollapsing to Simple Graphs
Multigraphs can be collapsed into simple Yog.Graph structures using to_simple_graph/1,
to_simple_graph/2, to_simple_graph_min_edges/1, to_simple_graph_max_edges/1, or
to_simple_graph_sum_edges/1.
Directed vs Undirected Multigraphs
- Directed: Edges have a specific direction (
from->to). In-degree and out-degree are separate. - Undirected: Edges operate bidirectionally. Incident self-loops contribute 2 to node degree.
Summary
Functions
Adds an edge to the multigraph, returning {updated_graph, edge_id}.
Adds a node to the multigraph with optional custom payload.
Returns all edge IDs in the graph.
Returns all edges as [{edge_id, from, to, data}] sorted by edge_id.
Returns all node IDs in the multigraph.
Performs a Breadth-First Search from source.
Returns the total degree of a node.
Performs a Depth-First Search from source.
Creates a new empty directed multigraph.
Returns {from, to, data} for an EdgeId, or nil if not found.
Synonym for size/1.
Returns the number of parallel edges between from and to.
Returns edge data payload for an EdgeId, or nil if not found.
Returns all parallel edges between from and to as [{edge_id, data}].
Fetches details for an EdgeId as {:ok, {from, to, data}} or :error.
Fetches node data for a given node ID as {:ok, data} or :error.
Finds an Eulerian circuit using Hierholzer's algorithm.
Finds an Eulerian path using Hierholzer's algorithm.
Folds over nodes during multigraph traversal with metadata.
Checks if the multigraph contains at least one cycle.
Checks if a specific EdgeId exists in the multigraph.
Predicate synonym for has_edge/2.
Synonym for has_edge_between?/3.
Checks if at least one edge exists between from and to.
Checks if the multigraph has an Eulerian circuit.
Checks if the multigraph has an Eulerian path.
Checks if a node ID exists in the multigraph.
Returns the in-degree of a node.
Synonym for type/1.
Creates a new empty multigraph of the given type (:directed or :undirected).
Returns data associated with a node, or nil if not found.
Synonym for order/1.
Synonym for node/2.
Returns the number of nodes (order) in the multigraph.
Returns the out-degree of a node.
Returns all incoming edges to id as [{from_node, edge_id, data}].
Removes a single edge by its EdgeId.
Removes a node and all incident edges connected to it.
Returns the total number of physical edges (size) in the multigraph.
Returns all outgoing edges from id as [{to_node, edge_id, data}].
Collapses the multigraph into a simple graph, keeping the earliest edge between each pair.
Collapses the multigraph into a simple graph using a combining function.
Collapses parallel edges, keeping the maximum weight.
Collapses parallel edges, keeping the minimum weight.
Collapses parallel edges, summing weights.
Collapses parallel edges, combining weights with the provided function.
Returns a topological ordering of nodes (directed multigraphs only).
Returns the type of the multigraph (:directed or :undirected).
Creates a new empty undirected multigraph.
Types
@type edge_id() :: Yog.Multi.Model.edge_id()
@type graph() :: Yog.Multi.Model.t()
Functions
Adds an edge to the multigraph, returning {updated_graph, edge_id}.
Adds a node to the multigraph with optional custom payload.
Returns all edge IDs in the graph.
Returns all edges as [{edge_id, from, to, data}] sorted by edge_id.
Returns all node IDs in the multigraph.
Performs a Breadth-First Search from source.
Returns the total degree of a node.
Performs a Depth-First Search from source.
Creates a new empty directed multigraph.
Returns {from, to, data} for an EdgeId, or nil if not found.
Synonym for size/1.
Returns the number of parallel edges between from and to.
Returns edge data payload for an EdgeId, or nil if not found.
Returns all parallel edges between from and to as [{edge_id, data}].
Fetches details for an EdgeId as {:ok, {from, to, data}} or :error.
Fetches node data for a given node ID as {:ok, data} or :error.
Finds an Eulerian circuit using Hierholzer's algorithm.
Finds an Eulerian path using Hierholzer's algorithm.
Folds over nodes during multigraph traversal with metadata.
Checks if the multigraph contains at least one cycle.
Collapses parallel edges internally before checking.
Checks if a specific EdgeId exists in the multigraph.
Predicate synonym for has_edge/2.
Synonym for has_edge_between?/3.
Checks if at least one edge exists between from and to.
Checks if the multigraph has an Eulerian circuit.
Checks if the multigraph has an Eulerian path.
Checks if a node ID exists in the multigraph.
Returns the in-degree of a node.
Synonym for type/1.
Creates a new empty multigraph of the given type (:directed or :undirected).
Returns data associated with a node, or nil if not found.
Synonym for order/1.
Synonym for node/2.
Returns the number of nodes (order) in the multigraph.
Returns the out-degree of a node.
Returns all incoming edges to id as [{from_node, edge_id, data}].
Removes a single edge by its EdgeId.
Removes a node and all incident edges connected to it.
Returns the total number of physical edges (size) in the multigraph.
Returns all outgoing edges from id as [{to_node, edge_id, data}].
Collapses the multigraph into a simple graph, keeping the earliest edge between each pair.
Collapses the multigraph into a simple graph using a combining function.
Collapses parallel edges, keeping the maximum weight.
Collapses parallel edges, keeping the minimum weight.
Collapses parallel edges, summing weights.
Collapses parallel edges, combining weights with the provided function.
@spec topological_sort(graph()) :: {:ok, [Yog.node_id()]} | {:error, :contains_cycle}
Returns a topological ordering of nodes (directed multigraphs only).
Collapses parallel edges internally, then applies Kahn's algorithm.
Returns {:ok, [node_id]} or {:error, :contains_cycle}.
Returns the type of the multigraph (:directed or :undirected).
Creates a new empty undirected multigraph.