# `Yog.Property`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/property.ex#L1)

Unified facade for assessing graph structures and invariant properties.

This module provides a convenient entry point for querying whether a graph
satisfies certain topological or algorithmic properties (e.g., connectivity,
planarity, chordality).

## Categories

### Structure
Predicates for tree structures, connectivity, and topological density.

### Eulerian Properties
Algorithms for discovering paths or circuits that visit every edge exactly once.

### Bipartite & Matching
Checks for 2-colorability and finding maximum matchings in bipartite configurations.

### Cliques & Communities
Finding complete subgraphs (maximal, maximum, or of specific size k).

### Cyclicity
Acyclicity (DAG) and general cycle detection.

### Treewidth & Decompositions
Heuristic upper bounds and tree decomposition construction.

## Examples

    iex> graph = Yog.undirected()
    ...> |> Yog.add_edge_ensure(1, 2, 1, nil)
    ...> |> Yog.add_edge_ensure(2, 3, 1, nil)
    ...> |> Yog.add_edge_ensure(3, 1, 1, nil)
    iex> Yog.Property.connected?(graph)
    true
    iex> Yog.Property.complete?(graph)
    true
    iex> Yog.Property.max_clique(graph) |> MapSet.size()
    3

# `acyclic?`

Checks if the graph is a Directed Acyclic Graph (DAG) or has no cycles.

## Examples

    iex> dag = Yog.directed() |> Yog.add_edge_ensure(1, 2, 1, nil)
    iex> Yog.Property.acyclic?(dag)
    true

# `all_maximal_cliques`

Finds all maximal cliques in an undirected graph.

## Examples

    iex> triangle = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 1, 1}])
    iex> Yog.Property.all_maximal_cliques(triangle) |> length()
    1

# `arborescence?`

Checks if the graph is an arborescence (directed tree with a single root).

## Examples

    iex> arb = Yog.directed()
    ...> |> Yog.add_edge_ensure(1, 2, 1, nil)
    ...> |> Yog.add_edge_ensure(1, 3, 1, nil)
    iex> Yog.Property.arborescence?(arb)
    true

# `arborescence_root`

Finds the root of an arborescence. Returns nil if none exists.

## Examples

    iex> arb = Yog.from_edges(:directed, [{"R", "A", 1}, {"R", "B", 1}, {"A", "C", 1}])
    iex> Yog.Property.arborescence_root(arb)
    "R"
    iex> not_arb = Yog.from_edges(:directed, [{1, 2, 1}, {2, 1, 1}])
    iex> Yog.Property.arborescence_root(not_arb)
    nil

# `bipartite?`

Determines if a graph is bipartite (2-colorable).

## Examples

    iex> square = Yog.undirected()
    ...> |> Yog.add_edge_ensure(1, 2, 1, nil)
    ...> |> Yog.add_edge_ensure(2, 3, 1, nil)
    ...> |> Yog.add_edge_ensure(3, 4, 1, nil)
    ...> |> Yog.add_edge_ensure(4, 1, 1, nil)
    iex> Yog.Property.bipartite?(square)
    true

# `branching?`

Checks if a directed graph is a branching (directed forest).

## Examples

    iex> branch = Yog.directed()
    ...> |> Yog.add_edge_ensure(1, 2, 1, nil)
    ...> |> Yog.add_edge_ensure(1, 3, 1, nil)
    ...> |> Yog.add_edge_ensure(4, 5, 1, nil)
    iex> Yog.Property.branching?(branch)
    true

# `chordal?`

Checks if the graph is chordal (no induced cycles longer than 3).
Uses Maximum Cardinality Search (MCS).

## Examples

    iex> g = Yog.undirected()
    ...> |> Yog.add_edge_ensure(1, 2, 1, nil)
    ...> |> Yog.add_edge_ensure(2, 3, 1, nil)
    ...> |> Yog.add_edge_ensure(3, 1, 1, nil) # triangle
    iex> Yog.Property.chordal?(g)
    true

# `coloring`

Finds a 2-coloring of a graph if it is bipartite.

## Examples

    iex> path = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}])
    iex> {:ok, colors} = Yog.Property.coloring(path)
    iex> colors[1] != colors[2]
    true

# `coloring_dsatur`

DSatur heuristic for graph coloring.

Usually produces better colorings than simple greedy ordering.

## Examples

    iex> graph = Yog.Generator.Classic.cycle(5)
    iex> {upper, _colors} = Yog.Property.coloring_dsatur(graph)
    iex> upper == 3
    true

# `coloring_exact`

Exact graph coloring with default 5-second timeout.

## Examples

    iex> k4 = Yog.Generator.Classic.complete(4)
    iex> {:ok, chi, _colors} = Yog.Property.coloring_exact(k4)
    iex> chi
    4

# `coloring_exact`

Exact graph coloring using backtracking with pruning and an optional timeout.

Returns `{:ok, chromatic_number, coloring}` on success, or `{:timeout, best_result}`
if the timeout is reached.

## Examples

    iex> graph = Yog.Generator.Classic.complete(4)
    iex> {:ok, chi, _colors} = Yog.Property.coloring_exact(graph)
    iex> chi == 4
    true

# `coloring_greedy`

Greedy graph coloring using Welsh-Powell ordering.

Returns a tuple `{upper_bound, color_map}` where `upper_bound` is the number
of colors used and `color_map` maps each node to its assigned color.

## Examples

    iex> graph = Yog.Generator.Classic.complete(3)
    iex> {upper, _colors} = Yog.Property.coloring_greedy(graph)
    iex> upper == 3
    true

# `complete?`

Checks if the graph is complete (every pair of distinct nodes is connected).

## Examples

    iex> k3 = Yog.undirected()
    ...> |> Yog.add_edge_ensure(1, 2, 1, nil)
    ...> |> Yog.add_edge_ensure(2, 3, 1, nil)
    ...> |> Yog.add_edge_ensure(3, 1, 1, nil)
    iex> Yog.Property.complete?(k3)
    true

# `connected?`

Checks if the graph is connected (undirected) or strongly connected (directed).

## Examples

    iex> g = Yog.directed() |> Yog.add_edge_ensure(1, 2, 1, nil) |> Yog.add_edge_ensure(2, 1, 1, nil)
    iex> Yog.Property.connected?(g)
    true

# `cyclic?`

Checks if the graph contains at least one cycle.

## Examples

    iex> cycle = Yog.from_edges(:directed, [{"A", "B", 1}, {"B", "C", 1}, {"C", "A", 1}])
    iex> Yog.Property.cyclic?(cycle)
    true
    iex> dag = Yog.from_edges(:directed, [{1, 2, 1}, {2, 3, 1}])
    iex> Yog.Property.cyclic?(dag)
    false

# `eulerian_circuit`

Finds an Eulerian circuit in the graph using Hierholzer's algorithm.

## Examples

    iex> square = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 4, 1}, {4, 1, 1}])
    iex> {:ok, circuit} = Yog.Property.eulerian_circuit(square)
    iex> length(circuit)
    5

# `eulerian_path`

Finds an Eulerian path in the graph using Hierholzer's algorithm.

## Examples

    iex> path = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}])
    iex> {:ok, p} = Yog.Property.eulerian_path(path)
    iex> length(p)
    3

# `forest?`

Checks if the graph is a forest (disjoint collection of trees).

## Examples

    iex> forest = Yog.undirected()
    ...> |> Yog.add_edge_ensure(1, 2, 1, nil)
    ...> |> Yog.add_edge_ensure(3, 4, 1, nil)
    iex> Yog.Property.forest?(forest)
    true

# `has_eulerian_circuit?`

Checks if the graph contains an Eulerian circuit (visits every edge once).

Degrees must be even (undirected) or balanced (directed).

## Examples

    iex> square = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 4, 1}, {4, 1, 1}])
    iex> Yog.Property.has_eulerian_circuit?(square)
    true
    iex> path = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}])
    iex> Yog.Property.has_eulerian_circuit?(path)
    false

# `has_eulerian_path?`

Checks if the graph contains an Eulerian path.

## Examples

    iex> path = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}])
    iex> Yog.Property.has_eulerian_path?(path)
    true
    iex> two_paths = Yog.from_edges(:undirected, [{1, 2, 1}, {3, 4, 1}])
    iex> Yog.Property.has_eulerian_path?(two_paths)
    false

# `hash`

Returns a deterministic structural hash of the graph.
Uses the Weisfeiler-Lehman topological graph hashing algorithm.

Graphs with identical structural arrangements return the same hash.

## Examples

    iex> g1 = Yog.undirected()
    ...> |> Yog.add_edge_ensure(1, 2, 1, nil)
    ...> |> Yog.add_edge_ensure(2, 3, 1, nil)
    iex> g2 = Yog.undirected()
    ...> |> Yog.add_edge_ensure(:a, :b, 1, nil)
    ...> |> Yog.add_edge_ensure(:b, :c, 1, nil)
    iex> Yog.Property.hash(g1) == Yog.Property.hash(g2)
    true

# `hash`

Returns a deterministic structural hash of the graph with custom options.

## Examples

    iex> g = Yog.Generator.Classic.cycle(4)
    iex> hash = Yog.Property.hash(g, iterations: 5)
    iex> is_binary(hash) and byte_size(hash) == 32
    true

# `isomorphic?`

Checks if two graphs are structurally isomorphic.

## Examples

    iex> g1 = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}])
    iex> g2 = Yog.from_edges(:undirected, [{:a, :b, 1}, {:b, :c, 1}])
    iex> Yog.Property.isomorphic?(g1, g2)
    true
    iex> triangle = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 1, 1}])
    iex> Yog.Property.isomorphic?(g1, triangle)
    false

# `k_cliques`

Finds all cliques of exactly size k in an undirected graph.

## Examples

    iex> k4 = Yog.Generator.Classic.complete(4)
    iex> Yog.Property.k_cliques(k4, 3) |> length()
    4

# `kuratowski_witness`

Identifies a Kuratowski witness that proves the graph is non-planar.

## Examples

    iex> k5 = Yog.Generator.Classic.complete(5)
    iex> {:ok, witness} = Yog.Property.kuratowski_witness(k5)
    iex> witness.type
    :k5
    iex> square = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 4, 1}, {4, 1, 1}])
    iex> Yog.Property.kuratowski_witness(square)
    :planar

# `max_clique`

Finds the maximum clique in an undirected graph.

## Examples

    iex> graph = Yog.undirected()
    ...> |> Yog.add_edge_ensure(1, 2, 1, nil)
    ...> |> Yog.add_edge_ensure(1, 3, 1, nil)
    ...> |> Yog.add_edge_ensure(2, 3, 1, nil)
    iex> Yog.Property.max_clique(graph) |> MapSet.size()
    3

# `maximum_matching`

Finds a maximum matching in a bipartite graph.

## Examples

    iex> g = Yog.from_edges(:undirected, [{"w1", "t1", 1}, {"w1", "t2", 1}, {"w2", "t1", 1}])
    iex> {:ok, p} = Yog.Property.partition(g)
    iex> length(Yog.Property.maximum_matching(g, p))
    2

# `minimum_degree`

Returns the minimum degree of the graph.

## Examples

    iex> graph = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}])
    iex> Yog.Property.minimum_degree(graph)
    1
    iex> isolated = Yog.undirected() |> Yog.add_node(1, nil) |> Yog.add_node(2, nil)
    iex> Yog.Property.minimum_degree(isolated)
    0

# `partition`

Returns the two partitions of a bipartite graph, or an error if not bipartite.

## Examples

    iex> path = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 4, 1}])
    iex> {:ok, %{left: left, right: right}} = Yog.Property.partition(path)
    iex> MapSet.size(left) + MapSet.size(right)
    4
    iex> triangle = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 1, 1}])
    iex> Yog.Property.partition(triangle)
    {:error, :not_bipartite}

# `planar?`

Checks if the graph is planar. Uses density heuristics (necessary conditions).

For graphs with $V ge 3$, validates $|E| le 3|V| - 6$.
If bipartite, validates $|E| le 2|V| - 4$.

# `planar_embedding`

Returns a combinatorial embedding if the graph is planar.

## Examples

    iex> square = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 4, 1}, {4, 1, 1}])
    iex> {:ok, embedding} = Yog.Property.planar_embedding(square)
    iex> is_map(embedding)
    true

# `regular?`

Checks if the graph is k-regular (every node has degree exactly k).

## Examples

    iex> c4 = Yog.undirected()
    ...> |> Yog.add_edge_ensure(1, 2, 1, nil)
    ...> |> Yog.add_edge_ensure(2, 3, 1, nil)
    ...> |> Yog.add_edge_ensure(3, 4, 1, nil)
    ...> |> Yog.add_edge_ensure(4, 1, 1, nil)
    iex> Yog.Property.regular?(c4, 2)
    true

# `stable_marriage`

Finds a stable matching given preference lists for two groups.

## Examples

    iex> residents = %{1 => [101, 102], 2 => [102, 101]}
    iex> hospitals = %{101 => [1, 2], 102 => [2, 1]}
    iex> matches = Yog.Property.stable_marriage(residents, hospitals)
    iex> matches[1]
    101

# `strongly_connected?`

Checks if a directed graph is strongly connected.

## Examples

    iex> cycle = Yog.from_edges(:directed, [{"A", "B", 1}, {"B", "C", 1}, {"C", "A", 1}])
    iex> Yog.Property.strongly_connected?(cycle)
    true
    iex> path = Yog.from_edges(:directed, [{1, 2, 1}, {2, 3, 1}])
    iex> Yog.Property.strongly_connected?(path)
    false

# `tree?`

Checks if the graph is a tree (connected and acyclic).

## Examples

    iex> tree = Yog.undirected()
    ...> |> Yog.add_edge_ensure(1, 2, 1, nil)
    ...> |> Yog.add_edge_ensure(2, 3, 1, nil)
    iex> Yog.Property.tree?(tree)
    true

# `tree_decomposition`

Returns a tree decomposition with default `:min_degree` heuristic.

## Examples

    iex> graph = Yog.Generator.Classic.cycle(5)
    iex> {:ok, td} = Yog.Property.tree_decomposition(graph)
    iex> is_map(td.bags)
    true

# `tree_decomposition`

Returns a tree decomposition of the graph using heuristic elimination ordering.

Returns `{:ok, Yog.Property.TreeDecomposition.t()}` on success.

## Examples

    iex> graph = Yog.Generator.Classic.cycle(5)
    iex> {:ok, td} = Yog.Property.tree_decomposition(graph, heuristic: :min_degree)
    iex> is_map(td.bags)
    true

# `treewidth_upper_bound`

Returns an upper bound on the treewidth with default `:min_degree` heuristic.

## Examples

    iex> graph = Yog.Generator.Classic.cycle(5)
    iex> Yog.Property.treewidth_upper_bound(graph) <= 2
    true

# `treewidth_upper_bound`

Returns an upper bound on the treewidth using heuristic elimination ordering.

## Options
- `:heuristic` - `:min_degree` (default) or `:min_fill`

## Examples

    iex> graph = Yog.Generator.Classic.cycle(5)
    iex> Yog.Property.treewidth_upper_bound(graph) <= 2
    true

# `weakly_connected?`

Checks if a directed graph is weakly connected.

## Examples

    iex> g = Yog.from_edges(:directed, [{"A", "B", 1}, {"C", "B", 1}])
    iex> Yog.Property.weakly_connected?(g)
    true
    iex> disconnected = Yog.from_edges(:directed, [{1, 2, 1}, {3, 4, 1}])
    iex> Yog.Property.weakly_connected?(disconnected)
    false

---

*Consult [api-reference.md](api-reference.md) for complete listing*