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

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.

<div class="graphviz">
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;
  }
}
</div>

    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.

<div class="graphviz">
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;
  }
}
</div>

    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

# `arborescence?`

```elixir
@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`

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

Finds the root of an arborescence.

# `branching?`

```elixir
@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?`

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

Checks if the graph is chordal using Maximum Cardinality Search.

# `complete?`

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

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

# `connected?`

```elixir
@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?`

```elixir
@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`

```elixir
@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?`

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

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

# `strongly_connected?`

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

Checks if a directed graph is strongly connected.

# `tree?`

```elixir
@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?`

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

Checks if a directed graph is weakly connected.

---

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