yog/operation

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	Description	Use Case
`union/2`	All nodes and edges from both graphs	Combine graph data
`intersection/2`	Only nodes and edges common to both	Find common structure
`difference/2`	Nodes/edges in first but not second	Find unique structure
`symmetric_difference/2`	Edges in exactly one graph	Find differing structure

Composition & Joins

Function	Description	Use Case
`disjoint_union/2`	Combine with automatic ID re-indexing	Safe graph combination
`cartesian_product/2`	Multiply graphs (grids, hypercubes)	Generate complex structures
`compose/2`	Merge overlapping graphs with combined edges	Layered systems
`power/2`	k-th power (connect nodes within distance k)	Reachability analysis

Structural Comparison

Function	Description	Use Case
`is_subgraph/2`	Check if first is subset of second	Validation, pattern matching
`is_isomorphic/2`	Check if graphs are structurally identical	Graph comparison

Example: Combining Graphs Safely

import yog
import yog/operation

// Two triangle graphs with overlapping IDs
let triangle1 = yog.from_simple_edges(Directed, [#(0, 1), #(1, 2), #(2, 0)])
let triangle2 = yog.from_simple_edges(Directed, [#(0, 1), #(1, 2), #(2, 0)])

// disjoint_union re-indexes the second graph automatically
let combined = operation.disjoint_union(triangle1, triangle2)
// Result: 6 nodes (0-5), two separate triangles

Example: Finding Common Structure

let common = operation.intersection(graph_a, graph_b)
// Returns only nodes and edges present in both graphs

Values

cartesian_product

</>

pub fn cartesian_product(
  first: model.Graph(n, e),
  second: model.Graph(m, f),
  with_first default_first: f,
  with_second default_second: e,
) -> model.Graph(#(n, m), #(e, f))

Returns the Cartesian product of two graphs.

Every node in the result is a pair #(u, v) where u is from the first graph and v is from the second graph. Node IDs in the result are integers calculated as u_index * order(second) + v_index.

Example

// Product of two paths of length 1 (single edge) is a 2x2 grid
let path = yog.from_simple_edges(Undirected, [#(0, 1)])
let grid = operation.cartesian_product(path, path, 0, 0)
// order(grid) == 4, edge_count(grid) == 4

compose

</>

pub fn compose(
  first: model.Graph(n, e),
  second: model.Graph(n, e),
) -> model.Graph(n, e)

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

This is a simple merge where nodes with the same ID are identified.

Example

let composed = operation.compose(g1, g2)

difference

</>

pub fn difference(
  first: model.Graph(n, e),
  second: model.Graph(n, e),
) -> model.Graph(n, e)

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

An edge is removed if it exists in both graphs. A node is removed if it exists in both graphs AND it has no remaining unique edges incident to it. If a node exists in the first graph but not the second, it is always kept.

Example

let g1 = yog.from_simple_edges(Directed, [#(1, 2), #(2, 3)])
let g2 = yog.from_simple_edges(Directed, [#(1, 2)])
let result = operation.difference(g1, g2)
// Result retains node 2, 3 and edge 2->3. Node 1 is removed.

disjoint_union

</>

pub fn disjoint_union(
  base: model.Graph(n, e),
  other: model.Graph(n, e),
) -> model.Graph(n, e)

Combines two graphs assuming they are separate entities with automatic re-indexing.

The second graph’s node IDs are shifted by order(base) to ensure they do not collide with IDs in the first graph.

Example

let g1 = yog.from_simple_edges(Directed, [#(0, 1)])
let g2 = yog.from_simple_edges(Directed, [#(0, 1)])
let result = operation.disjoint_union(g1, g2)
// Result has nodes 0, 1, 2, 3 and edges 0->1, 2->3

intersection

</>

pub fn intersection(
  first: model.Graph(n, e),
  second: model.Graph(n, e),
) -> model.Graph(n, e)

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

For an edge to be present in the intersection, it must exist between the same nodes in both graphs.

Example

let g1 = yog.from_simple_edges(Directed, [#(1, 2), #(2, 3)])
let g2 = yog.from_simple_edges(Directed, [#(2, 3), #(3, 4)])
let result = operation.intersection(g1, g2)
// Result contains node 2, 3 and edge 2->3

is_isomorphic

</>

pub fn is_isomorphic(
  first: model.Graph(n, e),
  second: model.Graph(n, e),
) -> Bool

Checks if two graphs are isomorphic (structurally identical).

Two graphs are isomorphic if there exists a bijection between their vertices that preserves adjacency. This function uses a backtracking algorithm with degree-sequence pruning.

Note: Graph isomorphism is a computationally hard problem. This implementation is suitable for small to medium-sized graphs.

Example

// Triangle (0-1-2) is isomorphic to (10-20-30)
let g1 = yog.from_simple_edges(Undirected, [#(0, 1), #(1, 2), #(2, 0)])
let g2 = yog.from_simple_edges(Undirected, [#(10, 20), #(20, 30), #(30, 10)])
operation.is_isomorphic(g1, g2) // True

is_subgraph

</>

pub fn is_subgraph(
  potential: model.Graph(n, e),
  container: model.Graph(n, e),
) -> Bool

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

Returns true if every node in the first graph exists in the second, and every edge in the first graph also exists in the second.

Example

let g1 = yog.from_simple_edges(Directed, [#(1, 2)])
let g2 = yog.from_simple_edges(Directed, [#(1, 2), #(2, 3)])
operation.is_subgraph(g1, g2) // True

power

</>

pub fn power(
  graph: model.Graph(n, e),
  k: Int,
  default_weight: e,
) -> model.Graph(n, e)

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.

New edges are created with the provided default_weight.

Time Complexity: O(V * (V + E))

symmetric_difference

</>

pub fn symmetric_difference(
  first: model.Graph(n, e),
  second: model.Graph(n, e),
) -> model.Graph(n, e)

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

Also includes all nodes that are incident to these unique edges, or nodes that exist in only one of the graphs.

Example

let g1 = yog.from_simple_edges(Directed, [#(1, 2)])
let g2 = yog.from_simple_edges(Directed, [#(2, 3)])
let result = operation.symmetric_difference(g1, g2)
// Result contains edges 1->2 and 2->3

union

</>

pub fn union(
  base: model.Graph(n, e),
  other: model.Graph(n, e),
) -> model.Graph(n, e)

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

If a node or edge exists in both graphs, the one from other takes precedence for data/weights.

Example

let g1 = yog.from_simple_edges(Directed, [#(1, 2)])
let g2 = yog.from_simple_edges(Directed, [#(2, 3)])
let result = operation.union(g1, g2)
// order(result) == 3, edge_count(result) == 2