Yog.Property.Structure (YogEx v0.97.1)

Structural properties of graphs.

This module provides checks for various graph classes and regularities.

Algorithms

Problem	Function	Complexity
Tree check	`tree?/1`	O(V + E)
Arborescence check	`arborescence?/1`	O(V + E)
Forest check	`forest?/1`	O(V + E)
Branching check	`branching?/1`	O(V + E)
Complete graph check	`complete?/1`	O(V)
Regular graph check	`regular?/2`	O(V)
Connected check	`connected?/1`	O(V + E)
Strongly connected check	`strongly_connected?/1`	O(V + E)
Weakly connected check	`weakly_connected?/1`	O(V + E)
Chordal check	`chordal?/1`	O(V + E)

Key Concepts

Tree: Connected acyclic undirected graph.
Arborescence: Directed tree with a unique root.
Complete Graph (Kn): Every pair of distinct vertices is connected by an edge.
Regular Graph: Every vertex has the same degree k.

Structural Visualizations

Comparison of an undirected tree and a complete graph.

graph G { rankdir=LR; bgcolor="transparent"; node [shape=circle, fontname="inherit"]; edge [fontname="inherit", fontsize=10]; subgraph cluster_tree { label="Undirected Tree"; color="#6366f1"; style=rounded; T1 -- T2; T1 -- T3; T2 -- T4; T2 -- T5; } subgraph cluster_complete { label="Complete (K3)"; color="#f43f5e"; style=rounded; K1 -- K2; K2 -- K3; K3 -- K1; } }

iex> alias Yog.Property.Structure
iex> tree = Yog.from_edges(:undirected, [{"T1", "T2", 1}, {"T1", "T3", 1}, {"T2", "T4", 1}, {"T2", "T5", 1}])
iex> Structure.tree?(tree)
true
iex> complete = Yog.from_edges(:undirected, [{"K1", "K2", 1}, {"K2", "K3", 1}, {"K3", "K1", 1}])
iex> Structure.complete?(complete)
true

Arborescence Visualization

A directed tree with a unique root node.

digraph G { rankdir=TB; bgcolor="transparent"; node [shape=circle, fontname="inherit"]; edge [fontname="inherit", fontsize=10]; subgraph cluster_arb { label="Arborescence"; color="#10b981"; style=rounded; R -> A; R -> B; A -> C; A -> D; } }

iex> alias Yog.Property.Structure
iex> arb = Yog.from_edges(:directed, [{"R", "A", 1}, {"R", "B", 1}, {"A", "C", 1}, {"A", "D", 1}])
iex> Structure.arborescence?(arb)
true
iex> Structure.arborescence_root(arb)
"R"

Examples

# Simple tree
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_edge_ensure(1, 2, 1)
iex> Yog.Property.Structure.tree?(graph)
true

# Complete graph K3 (triangle)
iex> graph = Yog.undirected() |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(1, 2, 1) |> Yog.add_edge_ensure(2, 3, 1) |> Yog.add_edge_ensure(3, 1, 1)
iex> Yog.Property.Structure.complete?(graph)
true

Summary

Functions

arborescence?(graph)

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

arborescence_root(graph)

Finds the root of an arborescence.

branching?(graph)

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

chordal?(graph)

Checks if the graph is chordal using Maximum Cardinality Search.

complete?(graph)

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

connected?(graph)

Checks if the graph is connected.

forest?(graph)

Checks if the graph is a forest (a loopless undirected graph consisting entirely of disjoint trees).

minimum_degree(graph)

Returns the minimum degree of the graph.

regular?(graph, k)

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

strongly_connected?(graph)

Checks if a directed graph is strongly connected.

tree?(graph)

Checks if the graph is a tree (connected and acyclic). Works for undirected graphs.

weakly_connected?(graph)

Checks if a directed graph is weakly connected.

Functions

arborescence?(graph)

@spec arborescence?(Yog.graph()) :: boolean()

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

A directed graph is an arborescence iff:

It has n nodes and n-1 edges
Exactly one node has in-degree 0 (the root)
All other nodes have in-degree >= 1

When edges = n-1 and there's exactly one root, reachability is guaranteed (no need for explicit BFS check).

arborescence_root(graph)

@spec arborescence_root(Yog.graph()) :: Yog.node_id() | nil

Finds the root of an arborescence.

branching?(graph)

@spec branching?(Yog.graph()) :: boolean()

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

Evaluates to true if every node has an in-degree of 1 or 0, and the graph contains no directed cycles.

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.Structure.branching?(branch)
true

chordal?(graph)

@spec chordal?(Yog.graph()) :: boolean()

Checks if the graph is chordal using Maximum Cardinality Search.

complete?(graph)

@spec complete?(Yog.graph()) :: boolean()

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

connected?(graph)

@spec connected?(Yog.graph()) :: boolean()

Checks if the graph is connected.

For undirected graphs, every node is reachable from every other node. For directed graphs, this checks for strong connectivity.

forest?(graph)

@spec forest?(Yog.graph()) :: boolean()

Checks if the graph is a forest (a loopless undirected graph consisting entirely of disjoint trees).

A disconnected graph with multiple trees evaluates to true.

Examples

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

minimum_degree(graph)

@spec minimum_degree(Yog.graph()) :: non_neg_integer()

Returns the minimum degree of the graph.

Isolated vertices have degree 0. Returns 0 for an empty graph.

Examples

iex> graph = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}])
iex> Yog.Property.Structure.minimum_degree(graph)
1

iex> empty = Yog.undirected()
iex> Yog.Property.Structure.minimum_degree(empty)
0

regular?(graph, k)

@spec regular?(Yog.graph(), integer()) :: boolean()

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

strongly_connected?(graph)

@spec strongly_connected?(Yog.graph()) :: boolean()

Checks if a directed graph is strongly connected.

tree?(graph)

@spec tree?(Yog.graph()) :: boolean()

Checks if the graph is a tree (connected and acyclic). Works for undirected graphs.

Time Complexity

O(V + E)

weakly_connected?(graph)

@spec weakly_connected?(Yog.graph()) :: boolean()

Checks if a directed graph is weakly connected.