Yog.Functional.Model (YogEx v1.0.0)

Inductive graph representation based on Martin Erwig's Functional Graph Library (FGL).

Unlike the adjacency-list representation in Yog.Graph, an inductive graph is viewed recursively: a graph is either empty, or a node context "patched" into a smaller graph.

The central operation is match/2: it removes one node from the graph and returns both that node's full context and the remaining graph. Recursing on the remaining graph gives algorithms a natural "visited set": a matched node is no longer present and cannot be matched again.

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 incident references to it from the remaining graph. This enables recursive algorithms that naturally terminate without an external visited set for matched nodes.
Embed: The inverse of match when used with the matching remaining graph — restores a node context and reconnects it to neighbors that are present.

Example Use Cases

Recursive algorithms: DFS, BFS, Dijkstra, SCC — implemented via repeated match/2 calls 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

Types

direction()

edge_label()

node_id()

node_label()

t()

Functions

add_edge(graph, from_id, to_id, label \\ nil)

Adds an edge, respecting the graph's directionality.

add_edge!(graph, from_id, to_id, label \\ nil)

Adds an edge, raising on error.

add_undirected_edge(graph, u, v, label \\ nil)

Adds an undirected edge between two nodes.

add_undirected_edge!(graph, u, v, label \\ nil)

Adds an undirected edge, raising on error.

degree(model, id)

Returns the total degree of a node (in_degree + out_degree).

edges(model)

Returns all edges in the graph as a list of tuples {from_id, to_id, label}.

embed(ctx, graph)

Embeds (patches) a node context back into a graph.

empty()

Creates an empty directed graph.

empty?(model)

Checks if the graph is empty.

ensure_node(graph, id, label \\ nil)

Ensures a node exists in the graph.

from_adjacency_graph(graph)

Converts an adjacency-based Yog.Graph into a functional inductive model.

get_edge(model, from_id, to_id)

Gets the label of an edge between two nodes.

get_node(model, id)

Gets a node's context from the graph.

get_node!(model, id)

Gets a node's context from the graph, raising KeyError if not found.

has_edge?(model, from_id, to_id)

Checks if an edge exists between two nodes.

has_node?(model, id)

Checks if a node exists in the graph.

in_degree(model, id)

Returns the in-degree of a node.

in_neighbors(model, id)

Returns the incoming neighbors of a node as %{neighbor_id => edge_label}.

match(graph, id)

Matches a node in the graph, returning its context and the remaining graph.

match_any(graph)

Matches an arbitrary node from the graph.

neighbors(model, id)

Returns all unique neighbors of a node, combining incoming and outgoing edges.

new(direction \\ :directed)

Creates a new graph with specified direction (defaults to :directed).

node_ids(model)

Returns all node IDs in the graph.

nodes(model)

Returns all nodes (contexts) in the graph.

out_degree(model, id)

Returns the out-degree of a node.

out_neighbors(model, id)

Returns the outgoing neighbors of a node as %{neighbor_id => edge_label}.

put_node(graph, id, label)

Adds or updates a node in the graph.

remove_edge(graph, u, v)

Removes an edge, respecting graph directionality.

remove_edge!(graph, from_id, to_id)

Removes an edge and returns the updated graph.

remove_node(graph, id)

Removes a node and all its edges from the graph.

remove_node!(graph, id)

Removes a node and all its edges from the graph, raising on error.

remove_undirected_edge(graph, u, v)

Removes an undirected edge between two nodes.

remove_undirected_edge!(graph, u, v)

Removes an undirected edge and returns the updated graph.

size(model)

Returns the number of nodes in the graph.

to_adjacency_graph(graph)

Converts a functional inductive model into an adjacency-based Yog.Graph.

Types

direction()

@type direction() :: :directed | :undirected

edge_label()

@type edge_label() :: any()

node_id()

@type node_id() :: any()

node_label()

@type node_label() :: any()

t()

@type t() :: %Yog.Functional.Model{
  direction: direction(),
  nodes: %{required(node_id()) => Yog.Functional.Model.Context.t()}
}

Functions

add_edge(graph, from_id, to_id, label \\ nil)

@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.

For directed graphs, only from_id -> to_id is added. For undirected graphs, both directions are represented internally so neighbor queries remain simple.

Returns {:error, :source_not_found} or {:error, :target_not_found} if either endpoint is missing.

add_edge!(graph, from_id, to_id, label \\ nil)

@spec add_edge!(t(), node_id(), node_id(), edge_label()) :: t()

Adds an edge, raising on error.

add_undirected_edge(graph, u, v, label \\ nil)

@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.

add_undirected_edge!(graph, u, v, label \\ nil)

@spec add_undirected_edge!(t(), node_id(), node_id(), edge_label()) :: t()

Adds an undirected edge, raising on error.

degree(model, id)

@spec degree(t(), node_id()) :: {:ok, non_neg_integer()} | {:error, :not_found}

Returns the total degree of a node (in_degree + out_degree).

edges(model)

@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}.

embed(ctx, graph)

@spec embed(Yog.Functional.Model.Context.t(), t()) :: t()

Embeds (patches) a node context back into a graph.

This is the inverse of match/2 when used with the remaining graph returned by that same match. It restores the node and reconnects incident edges to neighbor nodes that are present in the target graph.

If the context references neighbors that are absent from the target graph, those reverse references are not recreated, but the context itself is still inserted.

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, :edge)
iex> {:ok, ctx, remaining} = Yog.Functional.Model.match(graph, 1)
iex> restored = Yog.Functional.Model.embed(ctx, remaining)
iex> Yog.Functional.Model.has_edge?(restored, 1, 2)
true

empty()

@spec empty() :: t()

Creates an empty directed graph.

Examples

iex> graph = Yog.Functional.Model.empty()
iex> Yog.Functional.Model.empty?(graph)
true

empty?(model)

@spec empty?(t()) :: boolean()

Checks if the graph is empty.

ensure_node(graph, id, label \\ nil)

@spec ensure_node(t(), node_id(), node_label()) :: t()

Ensures a node exists in the graph.

from_adjacency_graph(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

get_edge(model, from_id, to_id)

@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"}

get_node(model, id)

@spec get_node(t(), node_id()) ::
  {:ok, Yog.Functional.Model.Context.t()} | {:error, :not_found}

Gets a node's context from the graph.

Returns {:ok, context} when the node exists, or {:error, :not_found} when it does not.

get_node!(model, id)

@spec get_node!(t(), node_id()) :: Yog.Functional.Model.Context.t()

Gets a node's context from the graph, raising KeyError if not found.

has_edge?(model, from_id, to_id)

@spec has_edge?(t(), node_id(), node_id()) :: boolean()

Checks if an edge exists between two nodes.

has_node?(model, id)

@spec has_node?(t(), node_id()) :: boolean()

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

in_degree(model, id)

@spec in_degree(t(), node_id()) :: {:ok, non_neg_integer()} | {:error, :not_found}

Returns the in-degree of a node.

in_neighbors(model, id)

@spec in_neighbors(t(), node_id()) ::
  {:ok, %{required(node_id()) => edge_label()}} | {:error, :not_found}

Returns the incoming neighbors of a node as %{neighbor_id => edge_label}.

Returns {:error, :not_found} if the target node is missing.

match(graph, id)

@spec match(t(), node_id()) ::
  {:ok, Yog.Functional.Model.Context.t(), t()} | {:error, :not_found}

Matches a node in the graph, returning its context and the remaining graph.

This is the defining inductive operation. It extracts the node's Context and removes the node plus all incident edge references from the returned graph. Recursing on the remaining graph means this node cannot be visited again.

If the node is found, returns {:ok, context, remaining_graph}. Otherwise, returns {:error, :not_found}.

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, :edge)
iex> {:ok, ctx, remaining} = Yog.Functional.Model.match(graph, 1)
iex> ctx.id
1
iex> Yog.Functional.Model.has_node?(remaining, 1)
false
iex> Yog.Functional.Model.has_edge?(remaining, 1, 2)
false
iex> Yog.Functional.Model.has_node?(remaining, 2)
true

match_any(graph)

@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)
true

neighbors(model, id)

@spec neighbors(t(), node_id()) :: {:ok, [node_id()]} | {:error, :not_found}

Returns all unique neighbors of a node, combining incoming and outgoing edges.

For directed graphs this is the union of predecessors and successors. For undirected graphs the incoming and outgoing maps are symmetric by convention.

new(direction \\ :directed)

@spec new(direction()) :: t()

Creates a new graph with specified direction (defaults to :directed).

Examples

iex> graph = Yog.Functional.Model.new(:directed)
iex> graph.direction
:directed

node_ids(model)

@spec node_ids(t()) :: [node_id()]

Returns all node IDs in the graph.

nodes(model)

@spec nodes(t()) :: [Yog.Functional.Model.Context.t()]

Returns all nodes (contexts) in the graph.

out_degree(model, id)

@spec out_degree(t(), node_id()) :: {:ok, non_neg_integer()} | {:error, :not_found}

Returns the out-degree of a node.

out_neighbors(model, id)

@spec out_neighbors(t(), node_id()) ::
  {:ok, %{required(node_id()) => edge_label()}} | {:error, :not_found}

Returns the outgoing neighbors of a node as %{neighbor_id => edge_label}.

Returns {:error, :not_found} if the source node is missing.

put_node(graph, id, label)

@spec put_node(t(), node_id(), node_label()) :: t()

Adds or updates a node in the graph.

remove_edge(graph, u, v)

@spec remove_edge(t(), node_id(), node_id()) :: {:ok, t()}

Removes an edge, respecting graph directionality.

Missing endpoints or missing edges are ignored; the function always returns {:ok, graph}.

remove_edge!(graph, from_id, to_id)

@spec remove_edge!(t(), node_id(), node_id()) :: t()

Removes an edge and returns the updated graph.

remove_node(graph, id)

@spec remove_node(t(), node_id()) :: {:ok, t()}

Removes a node and all its edges from the graph.

remove_node!(graph, id)

@spec remove_node!(t(), node_id()) :: t()

Removes a node and all its edges from the graph, raising on error.

remove_undirected_edge(graph, u, v)

@spec remove_undirected_edge(t(), node_id(), node_id()) :: {:ok, t()}

Removes an undirected edge between two nodes.

Missing endpoints or missing edges are ignored; the function always returns {:ok, graph}.

remove_undirected_edge!(graph, u, v)

@spec remove_undirected_edge!(t(), node_id(), node_id()) :: t()

Removes an undirected edge and returns the updated graph.

size(model)

@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

to_adjacency_graph(graph)

@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"