@spec cartesian_product(Yog.Graph.t(), Yog.Graph.t(), any(), any()) :: Yog.Graph.t()

Returns the Cartesian product of two graphs.

Creates a new graph where each node represents a pair of nodes from the input graphs. Useful for generating grids, hypercubes, and other complex structures.

Time Complexity: O(V₁ × V₂ + E₁ × V₂ + E₂ × V₁)

Parameters

• first - First input graph
• second - Second input graph
• default_first - Default edge data for edges derived from first
• default_second - Default edge data for edges derived from second

Examples

iex> g1 = Yog.undirected()
...> |> Yog.add_node(0, nil)
...> |> Yog.add_node(1, nil)
...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 1)
iex> g2 = Yog.undirected()
...> |> Yog.add_node(0, nil)
...> |> Yog.add_node(1, nil)
...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 1)
iex> product = Yog.Operation.cartesian_product(g1, g2, 0, 0)
iex> # 2x2 grid structure: 4 nodes
...> Yog.Model.order(product)
4

@spec compose(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()

Composes two graphs by merging overlapping nodes and combining their edges.

This is equivalent to union/2 - both graphs are merged together with other's data taking precedence on conflicts.

Time Complexity: O(V₁ + V₂ + E₁ + E₂)

Examples

iex> g1 = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> g2 = Yog.undirected()
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> composed = Yog.Operation.compose(g1, g2)
iex> Yog.Model.order(composed)
3

@spec difference(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()

Returns a graph containing nodes and edges that exist in the first graph but not in the second.

Any node that appears in second is removed from the result, along with all its incident edges. Of the remaining nodes, only edges that do not appear in second are kept.

Time Complexity: O(V + E)

Examples

iex> g1 = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> g2 = Yog.undirected()
...> |> Yog.add_node(3, nil)
iex> diff = Yog.Operation.difference(g1, g2)
iex> Yog.Model.order(diff)
2
iex> Yog.Model.has_edge?(diff, 1, 2)
true

@spec disjoint_union(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()

Computes the disjoint union of two graphs.

Unlike a simple join, this function guarantees that nodes from Graph A and Graph B remain distinct by tagging their IDs as {0, id} and {1, id}, even if they share the same original ID.

The resulting graph uses the kind (:directed or :undirected) from graph_a. Combining graphs of different kinds may lead to unexpected edge behavior.

Time Complexity: O(V₁ + V₂ + E₁ + E₂)

Example

iex> g1 = Yog.directed() |> Yog.add_node("root", "Data A")
iex> g2 = Yog.directed() |> Yog.add_node("root", "Data B")
iex> union = Yog.Operation.disjoint_union(g1, g2)
iex> Yog.Model.node_count(union)
2
iex> Yog.Model.node(union, {0, "root"})
"Data A"

@spec intersection(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()

Returns a graph containing only nodes and edges that exist in both input graphs.

For directed graphs, a directed edge must exist in both graphs to be kept. For undirected graphs, an undirected edge must exist in both graphs.

Time Complexity: O(V + E)

Examples

iex> g1 = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> g2 = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> intersection = Yog.Operation.intersection(g1, g2)
iex> Yog.Model.order(intersection)
3

@spec isomorphic?(Yog.Graph.t(), Yog.Graph.t()) :: boolean()

Checks if two graphs are isomorphic (structurally identical).

Two graphs are isomorphic if there exists a bijection between their node sets that preserves adjacency. This implementation uses degree sequence comparison and backtracking to test for isomorphism.

Time Complexity: O(V log V + E) for the fast checks; exponential in the worst case due to backtracking (not recommended for large graphs).

Examples

# Two identical triangles are isomorphic
iex> g1 = Yog.undirected()
...> |> Yog.add_node(0, nil)
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 1)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 0, with: 1)
iex> g2 = Yog.undirected()
...> |> Yog.add_node(10, nil)
...> |> Yog.add_node(20, nil)
...> |> Yog.add_node(30, nil)
...> |> Yog.add_edge_ensure(from: 10, to: 20, with: 1)
...> |> Yog.add_edge_ensure(from: 20, to: 30, with: 1)
...> |> Yog.add_edge_ensure(from: 30, to: 10, with: 1)
iex> Yog.Operation.isomorphic?(g1, g2)
true
iex> # Triangle is not isomorphic to a path
iex> path = Yog.undirected()
...> |> Yog.add_node(0, nil)
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 1)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> Yog.Operation.isomorphic?(g1, path)
false

@spec line_graph(Yog.Graph.t(), term()) :: Yog.Graph.t()

Returns the line graph of a graph.

The line graph L(G) is a graph where each node represents an edge of G, and two nodes are adjacent if and only if their corresponding edges share a common endpoint in G.

For directed graphs, two edges (u, v) and (x, y) are adjacent in the line graph if and only if v == x (the head of the first edge matches the tail of the second edge). This is the standard line digraph definition.

For undirected graphs, two edges {u, v} and {x, y} are adjacent if and only if they share at least one endpoint.

Line graph nodes are represented as {u, v} tuples. For undirected graphs, the tuple follows the same ordering convention as Yog.Model.all_edges/1 (u <= v using Erlang term ordering).

Time Complexity: O(E²) where E is the number of edges in the original graph

Parameters

• graph - The input graph
• default_weight - Weight for edges in the line graph (default: 1)

Examples

iex> path = Yog.undirected()
...> |> Yog.add_node(0, nil)
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 10)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 20)
iex> lg = Yog.Operation.line_graph(path, 1)
iex> # Line graph of a path has 2 nodes ({0,1} and {1,2}) and 1 edge
iex> Yog.Model.order(lg)
2
iex> Yog.Model.has_edge?(lg, {0, 1}, {1, 2})
true

@spec power(Yog.Graph.t(), integer(), any()) :: Yog.Graph.t()

Returns the k-th power of a graph.

The k-th power of a graph G, denoted G^k, is a graph where two nodes are adjacent if and only if their distance in G is at most k.

Self-loops are never added.

Time Complexity: O(V × (V + E)) in the worst case

Parameters

• graph - The input graph
• k - The power (distance threshold)
• default_weight - Weight for newly created edges

Examples

iex> path = Yog.undirected()
...> |> Yog.add_node(0, nil)
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 1)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> # G^2 connects nodes at distance <= 2
...> power = Yog.Operation.power(path, 2, 1)
iex> # Node 0 and 2 should now be connected (distance 2 in original)
...> Yog.Model.has_edge?(power, 0, 2)
true

@spec subgraph?(Yog.Graph.t(), Yog.Graph.t()) :: boolean()

Checks if the first graph is a subgraph of the second graph.

Returns true if all nodes and edges in the first graph exist in the second.

Time Complexity: O(Vₚ + Eₚ) where Vₚ and Eₚ are the nodes and edges of the potential subgraph

Examples

iex> container = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> potential = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> Yog.Operation.subgraph?(potential, container)
true
iex> not_subgraph = Yog.undirected()
...> |> Yog.add_node(4, nil)
...> |> Yog.add_node(5, nil)
...> |> Yog.add_edge_ensure(from: 4, to: 5, with: 1)
iex> Yog.Operation.subgraph?(not_subgraph, container)
false

@spec symmetric_difference(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()

Returns a graph containing edges that exist in exactly one of the input graphs.

The result is the union of difference(first, second) and difference(second, first). Nodes that have no incident unique edges will not appear in the result.

Time Complexity: O(V₁ + V₂ + E₁ + E₂)

Examples

iex> g1 = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> g2 = Yog.undirected()
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> sym_diff = Yog.Operation.symmetric_difference(g1, g2)
iex> Yog.Model.order(sym_diff)
1
iex> Yog.Model.edge_count(sym_diff)
0

@spec union(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()

Returns a graph containing all nodes and edges from both input graphs.

Node data and edge weights from other take precedence on conflicts. Both graphs must have the same kind (:directed or :undirected); the result inherits the kind from base.

Time Complexity: O(V₁ + V₂ + E₁ + E₂)

Examples

iex> g1 = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> g2 = Yog.undirected()
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> union = Yog.Operation.union(g1, g2)
iex> Yog.Model.order(union)
3