RustGTea

A Rust port of CGTea — Graph Theory Exploration and Analysis.

Backed by petgraph for graph structure and nalgebra for spectral computations.

---

Quick start

use rust_gtea::{generators, reports, actions, g6format};

let g = generators::cycle(6);
println!("{}", reports::wiener_index(&g));          // 27
println!("{}", reports::diameter(&g));              // 3
println!("{}", reports::girth(&g));                 // 6
println!("{:.4}", reports::graph_energy(&g));       // 8.0000
println!("{:.4}", reports::algebraic_connectivity(&g)); // 1.0000

let colors = actions::greedy_coloring(&g);         // [1,2,1,2,1,2]
let lg     = actions::line_graph(&g);              // L(C6) ≅ C6

let s  = g6format::to_g6(&g);                     // "EhEG"
let g2 = g6format::from_g6(&s);                   // round-trip

---

Generators (24 families)

Function	Parameters	Description
antiprism(n)	n	Two n-cycles connected by a band of triangles (2n vertices)
banana(n)	n	Complete graph K_n (CGTea alias)
circulant_product(n,m)	n, m	Cartesian product C_n × C_m
cocktail_party(n)	n	K_{2n} minus a perfect matching
complete(n)	n	Complete graph K_n
complete_bipartite(n,k)	n, k	K_{n,k}
crown(n)	n	n spokes + inner n-cycle (2n vertices)
cycle(n)	n	Cycle C_n
flower(n)	n	Two concentric n-cycles + central hub (2n+1 vertices)
friendship(n)	n	n triangles sharing one vertex (2n+1 vertices)
gear(n)	n	Wheel with inserted tooth vertices (2n+1 vertices)
generalized_petersen(n,k)	n, k	GP(n,k)
grid(n,m)	n, m	P_n × P_m grid
heawood()	—	Fixed 14-vertex cage
helm(n)	n	Wheel + pendant vertices (2n+1 vertices)
lollipop(n,k)	n, k	K_n with path P_k attached
path(n)	n	Path P_n
petersen()	—	GP(5,2)
prism(n)	n	Two parallel n-cycles + spokes (2n vertices)
regular(n,k)	n, k	k-regular circulant graph
star(n)	n	K_{1,n−1}
tadpole(n,k)	n, k	C_n with path P_k attached
web(n,k)	n, k	k concentric n-cycles + hub
wheel(n)	n	C_{n−1} rim + central hub

---

Reports (30 metrics)

General

Function	Description
num_vertices(g)	|V|
num_edges(g)	|E|
max_degree(g)	Maximum vertex degree
min_degree(g)	Minimum vertex degree
average_degree(g)	2|E|/|V|
density(g)	2|E|/(n(n−1))
num_connected_components(g)	BFS component count
num_triangles(g)	Triangle count
num_quadrangles(g)	4-cycle count
num_stars(g)	Σ C(deg(v),2)
edge_degree(g)	Σ_{uv∈E} (deg_u+deg_v)

Distance-based

Function	Formula
wiener_index(g)	Σ_{u<v} d(u,v)
hyper_wiener_index(g)	(1/2) Σ_{u<v} [d+d²]
harary_index(g)	Σ_{u<v} 1/d(u,v)
additive_harary(g)	Σ_{uv∈E} 1/(deg_u+deg_v)
gutman_index(g)	Σ_{u<v} deg_u·deg_v·d(u,v)
szeged_index(g)	Σ_{uv∈E} n_u·n_v
mostar_index(g)	Σ_{uv∈E} |n_u−n_v|
total_eccentricity(g)	Σ_v ecc(v)
wiener_polarity_index(g)	# pairs with d=3
multiplicative_wiener_index(g)	ln Π d(u,v)
multiplicative_harary_index(g)	ln Π 1/d(u,v)
diameter(g)	max d(u,v)
radius(g)	min ecc(v)
girth(g)	length of shortest cycle (0 if acyclic)

Spectral

Function	Description
max_eigenvalue(g)	Spectral radius of adjacency matrix
min_eigenvalue(g)	Smallest adjacency eigenvalue
sum_eigenvalues(g)	Sum of adjacency eigenvalues (= trace = 0)
graph_energy(g)	Σ |λ_i|
algebraic_connectivity(g)	Fiedler value (2nd-smallest Laplacian eigenvalue)

---

Actions

Function	Description
greedy_coloring(g) → Vec<usize>	First-fit sequential vertex coloring
line_graph(g) → CGraph	Line graph L(G)

---

Graph6 I/O

let s  = g6format::to_g6(&g);    // encode to Graph6 string
let g2 = g6format::from_g6(&s);  // decode Graph6 string

---

Building

cargo build --release
cargo run
cargo test

---

Dependencies

Crate	Purpose
petgraph	Graph data structure and algorithms
nalgebra	Dense linear algebra, eigenvalue computation

---

Project structure

src/
├── lib.rs          Public API, CGraph type alias
├── main.rs         Demo (all generators + all reports on C6 and Petersen)
├── generators.rs   24 graph generator functions
├── reports.rs      30 graph metric functions
├── actions.rs      greedy_coloring, line_graph
├── g6format.rs     Graph6 encoder / decoder
└── utils.rs        BFS distances, adjacency/Laplacian matrices, eigenvalues