Graph operations - Set-theoretic operations, composition, and structural comparison.
This module implements binary operations that treat graphs as sets of nodes and edges, following NetworkX's "Graph as a Set" philosophy. These operations allow you to combine, compare, and analyze structural differences between graphs.
Set-Theoretic Operations
| Function | Complexity | Description | Use Case |
|---|---|---|---|
union/2 | $\mathcal{O}(V_1 + V_2 + E_1 + E_2)$ | All nodes and edges from both graphs | Combine graph data |
intersection/2 | $\mathcal{O}(V + E)$ | Only nodes and edges common to both | Find common structure |
difference/2 | $\mathcal{O}(V + E)$ | Nodes/edges in first but not second | Find unique structure |
symmetric_difference/2 | $\mathcal{O}(V_1 + V_2 + E_1 + E_2)$ | Edges in exactly one graph | Find differing structure |
Composition & Joins
| Function | Complexity | Description | Use Case |
|---|---|---|---|
disjoint_union/2 | $\mathcal{O}(V_1 + V_2 + E_1 + E_2)$ | Combine with automatic ID re-indexing | Safe graph combination |
cartesian_product/4 | $\mathcal{O}(V_1 V_2 + E_1 V_2 + E_2 V_1)$ | Multiply graphs (grids, hypercubes) | Generate complex structures |
tensor_product/2 | $\mathcal{O}(V_1 V_2 + E_1 E_2)$ | Kronecker direct product | Product graphs |
strong_product/4 | $\mathcal{O}(V_1 V_2 + E_1 V_2 + E_2 V_1 + E_1 E_2)$ | Strong product (grid + diagonals) | Spatial topologies |
lexicographic_product/4 | $\mathcal{O}(V_1 V_2 + E_1 V_2^2 + V_1 E_2)$ | Graph composition | Hierarchical substitution |
compose/2 | $\mathcal{O}(V_1 + V_2 + E_1 + E_2)$ | Merge overlapping graphs | Layered systems |
line_graph/2 | $\mathcal{O}(E^2)$ | Convert edges to nodes | Edge-centric analysis |
power/3 | $\mathcal{O}(V \cdot (V + E))$ | $k$-th power (distance $\le k$) | Reachability analysis |
Structural Comparison
| Function | Complexity | Description | Use Case |
|---|---|---|---|
subgraph?/2 | $\mathcal{O}(V_p + E_p)$ | Check if first is subset of second | Validation, pattern matching |
isomorphic?/2 | Exponential worst-case | Check if graphs are structurally identical | Structural equivalence |
Summary
Functions
Returns the Cartesian product of two graphs.
Composes two graphs by merging overlapping nodes and combining their edges.
Returns a graph containing nodes and edges that exist in the first graph but not in the second.
Computes the disjoint union of two graphs.
Returns a graph containing only nodes and edges that exist in both input graphs.
Checks if two graphs are isomorphic (structurally identical).
Returns the Lexicographic product (composition) of two graphs.
Returns the line graph of a graph.
Returns the $k$-th power of a graph (connecting nodes at distance $\le k$).
Returns the Strong product of two graphs.
Checks if the first graph is a subgraph of the second graph.
Returns a graph containing edges that exist in exactly one of the input graphs.
Returns the Tensor product (Kronecker product) of two graphs.
Returns a graph containing all nodes and edges from both input graphs.
Functions
@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.
Time Complexity: $\mathcal{O}(V_1 V_2 + E_1 V_2 + E_2 V_1)$
@spec compose(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()
Composes two graphs by merging overlapping nodes and combining their edges.
Time Complexity: $\mathcal{O}(V_1 + V_2 + E_1 + E_2)$
@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.
Both graphs must have the same kind (:directed or :undirected).
Time Complexity: $\mathcal{O}(V + E)$
Errors
- Raises
ArgumentErrorif input graphs have different kinds.
@spec disjoint_union(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()
Computes the disjoint union of two graphs.
Guarantees that nodes from Graph A and Graph B remain distinct by tagging their
IDs as {0, id} and {1, id}.
Time Complexity: $\mathcal{O}(V_1 + V_2 + E_1 + E_2)$
@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.
Both graphs must have the same kind (:directed or :undirected).
Time Complexity: $\mathcal{O}(V + E)$
Errors
- Raises
ArgumentErrorif input graphs have different kinds.
@spec isomorphic?(Yog.Graph.t(), Yog.Graph.t()) :: boolean()
Checks if two graphs are isomorphic (structurally identical).
Both graphs must have the same kind (:directed or :undirected).
Time Complexity: Exponential in worst case due to backtracking.
Errors
- Raises
ArgumentErrorif input graphs have different kinds.
@spec lexicographic_product(Yog.Graph.t(), Yog.Graph.t(), any(), any()) :: Yog.Graph.t()
Returns the Lexicographic product (composition) of two graphs.
Time Complexity: $\mathcal{O}(V_1 V_2 + E_1 V_2^2 + V_1 E_2)$
@spec line_graph(Yog.Graph.t(), term()) :: Yog.Graph.t()
Returns the line graph of a graph.
Time Complexity: $\mathcal{O}(E^2)$
@spec power(Yog.Graph.t(), integer(), any()) :: Yog.Graph.t()
Returns the $k$-th power of a graph (connecting nodes at distance $\le k$).
Time Complexity: $\mathcal{O}(V \cdot (V + E))$
Errors
- Raises
ArgumentErrorifkis not a positive integer ($ge 1$).
@spec strong_product(Yog.Graph.t(), Yog.Graph.t(), any(), any()) :: Yog.Graph.t()
Returns the Strong product of two graphs.
Time Complexity: $\mathcal{O}(V_1 V_2 + E_1 V_2 + E_2 V_1 + E_1 E_2)$
@spec subgraph?(Yog.Graph.t(), Yog.Graph.t()) :: boolean()
Checks if the first graph is a subgraph of the second graph.
Both graphs must have the same kind (:directed or :undirected).
Time Complexity: $\mathcal{O}(V_p + E_p)$
Errors
- Raises
ArgumentErrorif input graphs have different kinds.
@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.
Both graphs must have the same kind (:directed or :undirected).
Time Complexity: $\mathcal{O}(V_1 + V_2 + E_1 + E_2)$
Errors
- Raises
ArgumentErrorif input graphs have different kinds.
@spec tensor_product(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()
Returns the Tensor product (Kronecker product) of two graphs.
Time Complexity: $\mathcal{O}(V_1 V_2 + E_1 E_2)$
@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 be %Yog.Graph{} structs.
Time Complexity: $\mathcal{O}(V_1 + V_2 + E_1 + E_2)$