Inductive graph representation based on Martin Erwig's Functional Graph Library (FGL).
Unlike the adjacency-list representation in Yog.Graph, an inductive graph is
defined recursively: a graph is either empty, or a node context "patched" into
an existing graph.
Core Operations
| Operation | Function | Description |
|---|---|---|
| Decompose | match/2 | Extract a node + its edges, returning the shrunken graph |
| Compose | embed/2 | Insert a node context back into a graph |
| Inspect | match_any/1 | Decompose an arbitrary node |
| Interop | from_adjacency_graph/1 | Convert from adjacency-based Yog.Graph |
| Interop | to_adjacency_graph/1 | Convert back to adjacency-based Yog.Graph |
Key Concepts
- Context: A node's identity, label, and its incident edges (
in_edges,out_edges) - Match: The primary operation — extracts a node and removes all its edges from the graph. This enables recursive algorithms that naturally terminate without explicit visited sets.
- Embed: The inverse of
match— restores a node and its edges into a graph.
Example Use Cases
- Recursive algorithms: DFS, BFS, Dijkstra, SCC — all implemented via
repeated
match/2calls that shrink the graph at each step - Functional transformations: Map over nodes/edges, filter, reverse
- Teaching: The inductive structure makes graph algorithm correctness proofs straightforward
References
Summary
Functions
Adds an edge, respecting the graph's directionality.
Adds an edge, raising on error.
Adds an undirected edge between two nodes.
Adds an undirected edge, raising on error.
Returns the total degree of a node (in_degree + out_degree).
Returns all edges in the graph as a list of tuples {from_id, to_id, label}.
Embeds (patches) a node context back into the graph.
Creates an empty directed graph.
Checks if the graph is empty.
Ensures a node exists in the graph.
Converts an adjacency-based Yog.Graph into a functional inductive model.
Gets the label of an edge between two nodes.
Gets a node's context from the graph.
Gets a node's context from the graph, raising if not found.
Checks if an edge exists between two nodes.
Checks if a node exists in the graph.
Returns the in-degree of a node.
Returns the incoming neighbors of a node.
Matches a node in the graph, returning its context and the remaining graph.
Matches an arbitrary node from the graph.
Returns all unique neighbors (both incoming and outgoing) of a node.
Creates a new graph with specified direction (defaults to :directed).
Returns all node IDs in the graph.
Returns all nodes (contexts) in the graph.
Returns the out-degree of a node.
Returns the outgoing neighbors of a node.
Adds or updates a node in the graph.
Removes an edge, respecting graph directionality.
Removes an edge, raising on error.
Removes a node and all its edges from the graph.
Removes a node and all its edges from the graph, raising on error.
Removes an undirected edge between two nodes.
Removes an undirected edge, raising on error.
Returns the number of nodes in the graph.
Converts a functional inductive model into an adjacency-based Yog.Graph.
Types
Functions
@spec add_edge(t(), node_id(), node_id(), edge_label()) :: {:ok, t()} | {:error, :source_not_found | :target_not_found}
Adds an edge, respecting the graph's directionality.
@spec add_edge!(t(), node_id(), node_id(), edge_label()) :: t()
Adds an edge, raising on error.
@spec add_undirected_edge(t(), node_id(), node_id(), edge_label()) :: {:ok, t()} | {:error, :source_not_found | :target_not_found}
Adds an undirected edge between two nodes.
@spec add_undirected_edge!(t(), node_id(), node_id(), edge_label()) :: t()
Adds an undirected edge, raising on error.
@spec degree(t(), node_id()) :: {:ok, non_neg_integer()} | {:error, :not_found}
Returns the total degree of a node (in_degree + out_degree).
@spec edges(t()) :: [{node_id(), node_id(), edge_label()}]
Returns all edges in the graph as a list of tuples {from_id, to_id, label}.
Embeds (patches) a node context back into the graph.
This operation restores the node and all the incident edges described in the provided context. Note that it assumes the neighbors referenced in the context already exist in the target graph.
@spec empty() :: t()
Creates an empty directed graph.
Examples
iex> graph = Yog.Functional.Model.empty()
iex> Yog.Functional.Model.empty?(graph)
trueChecks if the graph is empty.
@spec ensure_node(t(), node_id(), node_label()) :: t()
Ensures a node exists in the graph.
@spec from_adjacency_graph(Yog.Graph.t()) :: t()
Converts an adjacency-based Yog.Graph into a functional inductive model.
Examples
iex> alias Yog.Functional.Model
iex> eg = Yog.Model.new(:directed) |> Yog.Model.add_node(1, "A")
iex> fg = Model.from_adjacency_graph(eg)
iex> Model.size(fg)
1@spec get_edge(t(), node_id(), node_id()) :: {:ok, edge_label()} | {:error, :not_found}
Gets the label of an edge between two nodes.
Examples
iex> graph = Yog.Functional.Model.empty()
...> |> Yog.Functional.Model.put_node(1, "A")
...> |> Yog.Functional.Model.put_node(2, "B")
...> |> Yog.Functional.Model.add_edge!(1, 2, "weight")
iex> Yog.Functional.Model.get_edge(graph, 1, 2)
{:ok, "weight"}@spec get_node(t(), node_id()) :: {:ok, Yog.Functional.Model.Context.t()} | {:error, :not_found}
Gets a node's context from the graph.
@spec get_node!(t(), node_id()) :: Yog.Functional.Model.Context.t()
Gets a node's context from the graph, raising if not found.
Checks if an edge exists between two nodes.
Checks if a node exists in the graph.
Examples
iex> graph = Yog.Functional.Model.empty() |> Yog.Functional.Model.put_node(1, "A")
iex> Yog.Functional.Model.has_node?(graph, 1)
true
iex> Yog.Functional.Model.has_node?(graph, 2)
false@spec in_degree(t(), node_id()) :: {:ok, non_neg_integer()} | {:error, :not_found}
Returns the in-degree of a node.
@spec in_neighbors(t(), node_id()) :: {:ok, %{required(node_id()) => edge_label()}} | {:error, :not_found}
Returns the incoming neighbors of a node.
Matches a node in the graph, returning its context and the remaining graph.
This operation extracts the node and all its incident edges (both incoming and
outgoing). If the node is found, it returns {:ok, context, remaining_graph}.
Otherwise, it returns {:error, :not_found}.
@spec match_any(t()) :: {:ok, Yog.Functional.Model.Context.t(), t()} | {:error, :empty}
Matches an arbitrary node from the graph.
Examples
iex> graph = Yog.Functional.Model.empty() |> Yog.Functional.Model.put_node(1, "A")
iex> {:ok, ctx, remaining} = Yog.Functional.Model.match_any(graph)
iex> ctx.id
1
iex> Yog.Functional.Model.empty?(remaining)
trueReturns all unique neighbors (both incoming and outgoing) of a node.
Creates a new graph with specified direction (defaults to :directed).
Examples
iex> graph = Yog.Functional.Model.new(:directed)
iex> graph.direction
:directedReturns all node IDs in the graph.
@spec nodes(t()) :: [Yog.Functional.Model.Context.t()]
Returns all nodes (contexts) in the graph.
@spec out_degree(t(), node_id()) :: {:ok, non_neg_integer()} | {:error, :not_found}
Returns the out-degree of a node.
@spec out_neighbors(t(), node_id()) :: {:ok, %{required(node_id()) => edge_label()}} | {:error, :not_found}
Returns the outgoing neighbors of a node.
@spec put_node(t(), node_id(), node_label()) :: t()
Adds or updates a node in the graph.
Removes an edge, respecting graph directionality.
Removes an edge, raising on error.
Removes a node and all its edges from the graph.
Removes a node and all its edges from the graph, raising on error.
Removes an undirected edge between two nodes.
Removes an undirected edge, raising on error.
@spec size(t()) :: non_neg_integer()
Returns the number of nodes in the graph.
Examples
iex> graph = Yog.Functional.Model.empty() |> Yog.Functional.Model.put_node(1, "A")
iex> Yog.Functional.Model.size(graph)
1@spec to_adjacency_graph(t()) :: Yog.Graph.t()
Converts a functional inductive model into an adjacency-based Yog.Graph.
Examples
iex> alias Yog.Functional.Model
iex> fg = Model.empty() |> Model.put_node(1, "A")
iex> eg = Model.to_adjacency_graph(fg)
iex> eg.nodes[1]
"A"