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()
3Summary
Functions
Checks if the graph is a Directed Acyclic Graph (DAG) or has no cycles.
Finds all maximal cliques in an undirected graph.
Checks if the graph is an arborescence (directed tree with a single root).
Finds the root of an arborescence. Returns nil if none exists.
Determines if a graph is bipartite (2-colorable).
Checks if a directed graph is a branching (directed forest).
Checks if the graph is chordal (no induced cycles longer than 3). Uses Maximum Cardinality Search (MCS).
Finds a 2-coloring of a graph if it is bipartite.
DSatur heuristic for graph coloring.
Exact graph coloring with default 5-second timeout.
Exact graph coloring using backtracking with pruning and an optional timeout.
Greedy graph coloring using Welsh-Powell ordering.
Checks if the graph is complete (every pair of distinct nodes is connected).
Checks if the graph is connected (undirected) or strongly connected (directed).
Checks if the graph contains at least one cycle.
Finds an Eulerian circuit in the graph using Hierholzer's algorithm.
Finds an Eulerian path in the graph using Hierholzer's algorithm.
Checks if the graph is a forest (disjoint collection of trees).
Checks if the graph contains an Eulerian circuit (visits every edge once).
Checks if the graph contains an Eulerian path.
Returns a deterministic structural hash of the graph. Uses the Weisfeiler-Lehman topological graph hashing algorithm.
Returns a deterministic structural hash of the graph with custom options.
Checks if two graphs are structurally isomorphic.
Finds all cliques of exactly size k in an undirected graph.
Identifies a Kuratowski witness that proves the graph is non-planar.
Finds the maximum clique in an undirected graph.
Finds a maximum matching in a bipartite graph.
Returns the minimum degree of the graph.
Returns the two partitions of a bipartite graph, or an error if not bipartite.
Checks if the graph is planar. Uses density heuristics (necessary conditions).
Returns a combinatorial embedding if the graph is planar.
Checks if the graph is k-regular (every node has degree exactly k).
Finds a stable matching given preference lists for two groups.
Checks if a directed graph is strongly connected.
Checks if the graph is a tree (connected and acyclic).
Returns a tree decomposition with default :min_degree heuristic.
Returns a tree decomposition of the graph using heuristic elimination ordering.
Returns an upper bound on the treewidth with default :min_degree heuristic.
Returns an upper bound on the treewidth using heuristic elimination ordering.
Checks if a directed graph is weakly connected.
Functions
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)
trueFinds 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()
1Checks 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)
trueFinds 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)
nilDetermines 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)
trueChecks 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)
trueChecks 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)
trueFinds 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]
trueDSatur 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
trueExact 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
4Exact 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
trueGreedy 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
trueChecks 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)
trueChecks 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)
trueChecks 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)
falseFinds 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)
5Finds 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)
3Checks 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)
trueChecks 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)
falseChecks 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)
falseReturns 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)
trueReturns 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
trueChecks 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)
falseFinds 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()
4Identifies 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)
:planarFinds 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()
3Finds 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))
2Returns 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)
0Returns 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}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$.
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)
trueChecks 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)
trueFinds 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]
101Checks 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)
falseChecks 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)
trueReturns 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)
trueReturns 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)
trueReturns 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
trueReturns 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
trueChecks 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