structure

Structural properties of graphs.

This module provides checks for various graph classes and regularities.

Algorithms

Problem	Function	Complexity
Tree check	`is_tree/1`	O(V + E)
Arborescence check	`is_arborescence/1`	O(V + E)
Complete graph check	`is_complete/1`	O(V)
Regular graph check	`is_regular/2`	O(V)
Connected check	`is_connected/1`	O(V + E)
Strongly connected check	`is_strongly_connected/1`	O(V + E)
Weakly connected check	`is_weakly_connected/1`	O(V + E)
Planar check	`is_planar/1`	O(V + E)
Chordal check	`is_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.

Values

arborescence_root

</>

pub fn arborescence_root(
  graph: model.Graph(n, e),
) -> option.Option(Int)

Finds the root of an arborescence.

Returns Some(root) if the graph is an arborescence, None otherwise.

is_arborescence

</>

pub fn is_arborescence(graph: model.Graph(n, e)) -> Bool

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

Time Complexity: O(V + E)

is_chordal

</>

pub fn is_chordal(graph: model.Graph(n, e)) -> Bool

Checks if the graph is chordal using Maximum Cardinality Search.

A chordal graph is one where every induced cycle has length 3.

Time Complexity: O(V + E)

is_complete

</>

pub fn is_complete(graph: model.Graph(n, e)) -> Bool

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

Time Complexity: O(V)

is_connected

</>

pub fn is_connected(graph: model.Graph(n, e)) -> Bool

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.

Time Complexity: O(V + E)

is_planar

</>

pub fn is_planar(graph: model.Graph(n, e)) -> Bool

Checks if the graph is planar (necessary conditions only).

Implements necessary checks: |E| ≤ 3|V| - 6 and bipartite |E| ≤ 2|V| - 4.

Time Complexity: O(V + E)

is_regular

</>

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

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

For directed graphs, both in-degree and out-degree must equal k.

Time Complexity: O(V)

is_strongly_connected

</>

pub fn is_strongly_connected(graph: model.Graph(n, e)) -> Bool

Checks if a directed graph is strongly connected.

For undirected graphs, falls back to is_connected/1.

Time Complexity: O(V + E)

is_tree

</>

pub fn is_tree(graph: model.Graph(n, e)) -> Bool

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

Time Complexity: O(V + E)

is_weakly_connected

</>

pub fn is_weakly_connected(graph: model.Graph(n, e)) -> Bool

Checks if a directed graph is weakly connected.

For undirected graphs, falls back to is_connected/1.

Time Complexity: O(V + E)