Metadata-Version: 2.4
Name: graphlimpy
Version: 0.1.0
Summary: A lightweight Python toolkit for exploring graphons, graph limits, and cut distance.
Author: Ishaan Goel
License: MIT
Project-URL: Homepage, https://github.com/igoeldc/graphlimpy
Keywords: graphons,graph limits,graph theory,networks
Classifier: Programming Language :: Python :: 3
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy
Requires-Dist: matplotlib
Dynamic: license-file

# Graphon Playground

> **Disclaimer:** This entire project was **vibecoded**. It was built in a single afternoon through high-signal dialogue with an AI assistant. It prioritizes conceptual clarity, rapid experimentation, and mathematical intuition over production-grade engineering.

A lightweight Python toolkit for **exploring graphons, graph limits, and cut distance**.

The goal is not to build a production library, but rather a **small interactive sandbox** useful for reading groups following Lovász’s *Large Networks and Graph Limits*. The focus is on visualization, sampling, and intuition-building experiments.


## Goals

This project should make it easy to:

- Define graphons $W:[0,1]^2 \to [0,1]$
- Visualize graphons
- Sample graphs $G(n,W)$
- Convert graphs into **step graphons**
- Compute **subgraph densities**
- Estimate **cut norm and cut distance**
- Experiment with **vertex relabelings and measure-preserving transformations**

The emphasis is on **clarity and interactivity**, not efficiency.


## Design Philosophy

Graph limit theory is naturally expressed in terms of **matrices and functions**, not graph objects.
For this reason the library is built around **NumPy arrays** rather than graph libraries such as NetworkX.

Core objects:

| Object | Representation |
|------|------|
| Graphon | Python callable `W(x,y)` |
| Graph | adjacency matrix `A` |
| Step graphon | block matrix `B` |
| Vertex ordering | permutation array |

This matches the mathematical notation used throughout *Large Networks and Graph Limits*, where graphs are represented by adjacency matrices $A_{ij}$ and graphons are measurable functions $W(x,y)$.

Using NumPy allows:

- vectorized operations
- efficient dense graph handling
- simple mathematical correspondence with the theory

NetworkX may still be used optionally for visualization or graph algorithms, but it is **not a dependency of the core library**.


## Repository Structure

```
graphlimpy/
│
├── graphlimpy/
│   │
│   ├── __init__.py
│   │
│   ├── graphons.py
│   │   Built-in graphon constructors and examples.
│   │
│   ├── sample.py
│   │   Sampling graphs G(n,W) from graphons.
│   │
│   ├── viz.py
│   │   Visualization utilities for graphons and adjacency matrices.
│   │
│   ├── step.py
│   │   Step-function graphon approximations and block models.
│   │
│   ├── stats.py
│   │   Subgraph densities and simple graph statistics.
│   │
│   ├── cut.py
│   │   Approximate cut norm and cut distance algorithms.
│   │
│   ├── rearrange.py
│   │   Measure-preserving graphon transformations.
│   │
│   └── utils.py
│       Small shared utilities (sampling grids, permutations, helpers).
│
├── demos/
│   │
│   ├── demo_sampling.py
│   ├── demo_stats_convergence.py
│   ├── demo_step_graphon.py
│   ├── demo_cut_reorder.py
│   └── demo_rearrange_graphon.py
│
├── notebooks/
│   │
│   ├── graphon_playground.ipynb
│   └── cut_distance_experiments.ipynb
│
└── README.md
```


## Core Concepts

### Graphon

A graphon is a symmetric measurable function

$$
W : [0,1]^2 \to [0,1]
$$

representing the limit of a dense graph sequence.

In this project, graphons are represented simply as **callable Python functions**:

```python
def W(x, y):
    return (x + y > 1).astype(float)
```

This makes it easy to experiment with arbitrary graphons without introducing additional class abstractions.


## Module Overview

### graphons.py

Graphon constructors and common examples.

Functions:

```
constant(p)
half_graphon()
bipartite(split, p_in, p_out)
sbm(P, splits)
ramp()
rank1(f)
```

Example:

```python
from graphlimpy.graphons import sbm

W = sbm(
    P=[[0.1, 0.5],
       [0.5, 0.2]],
    splits=[0.4, 0.6]
)
```


### viz.py

Visualization tools.

Functions:

```
plot_graphon(W, m=400)
plot_adj(A, order=None)
plot_step(B)
plot_sampling_4panel(W, n=300, k=20)
```

Example:

```python
plot_graphon(W)
```

Produces a heatmap of the graphon.


### sample.py

Sampling graphs from graphons.

Functions:

```
sample_GnW(W, n, seed=None)
```

Algorithm:

1. Sample latent variables  
   $u_i \sim \text{Uniform}[0,1]$

2. Compute probabilities

$$
P_{ij} = W(u_i, u_j)
$$

3. Sample

$$
A_{ij} \sim \text{Bernoulli}(P_{ij})
$$

Example:

```python
A, u = sample_GnW(W, n=300)
```


### step.py

Step graphon approximations.

Given a graph $G$, produce a block-averaged approximation.

Functions:

```
empirical_step_graphon(A, order=None, k=20)
```

Returns a $k \times k$ block density matrix.

This approximates the graphon associated with the graph and is closely related to the **weak regularity lemma**.


### stats.py

Subgraph densities.

Functions:

```
edge_density_graph(A)
triangle_density_graph(A)

edge_density_graphon(W)
triangle_density_graphon(W)
```

Graphon densities are computed using Monte Carlo integration.


### cut.py

Cut norm and cut distance.

Exact computation is NP-hard, so we implement approximate algorithms based on alternating maximization.

Functions:

```
cut_norm(A)

cut_distance_graphs(A, B)

cut_distance_graphons(W1, W2)
```

Graphon distance is estimated by sampling a grid of points.


### rearrange.py

Measure-preserving transformations.

Used to illustrate the fact that graphons are equivalent up to rearrangement.

Functions:

```
rearrange_graphon(W, phi)
swap_intervals(...)
random_rearrangement(...)
```

Example:

```python
W2 = rearrange_graphon(W, phi)
```

Then

```
cut_distance_graphons(W, W2) ≈ 0
```

even though the heatmaps look different.


## Planned Experiments

### 1. Graphon → Graph sampling

```
plot_graphon(W)

A, u = sample_GnW(W, 400)

plot_adj(A)
plot_adj(A, order=u.argsort())
```

Demonstrates how sampled graphs reflect the graphon structure.

Better yet, use the 4-panel sampling visualization to see the full pipeline:

```python
from graphlimpy.viz import plot_sampling_4panel
plot_sampling_4panel(W, n=400, k=25)
```


### 2. Relabelings

Permuting vertices changes adjacency matrix appearance but not structure.

Experiment:

```
A_perm = permute(A)

cut_distance_graphs(A, A_perm)
```

Distance $\approx 0$.


### 3. Graph sequence convergence

Fix a graphon and sample larger graphs.

```
for n in [50, 100, 200, 400]:
    A, _ = sample_GnW(W, n)
```

Observe:

- adjacency matrices stabilize  
- subgraph densities converge  
- cut distance to graphon decreases  


### 4. Step graphon approximations

```
B = empirical_step_graphon(A, k=20)
```

Increasing $k$ improves approximation.

Related to the **weak regularity lemma**.


## Dependencies

The core library intentionally has **minimal dependencies**:

```
numpy
matplotlib
```

This keeps the code lightweight and easy to read.

Optional integrations (not required):

```
networkx
ipywidgets
scipy
```

These may be useful for visualization, experimentation, or optimization.


## Future Extensions

Possible later additions:

- stochastic block model inference
- spectral graphon estimation
- cut-distance visualization
- graphon fitting algorithms
- sparse graphon models


## Example Session

```python
from graphlimpy.graphons import half_graphon
from graphlimpy.sample import sample_GnW
from graphlimpy.viz import plot_graphon, plot_adj
from graphlimpy.cut import cut_distance_graphons

W = half_graphon()

plot_graphon(W)

A, u = sample_GnW(W, 400)

plot_adj(A)
plot_adj(A, order=u.argsort())

print(cut_distance_graphons(W, W))
```


## Purpose

This repository is meant as a **graphon playground for experimentation and learning**, particularly useful for reading groups working through Lovász’s *Large Networks and Graph Limits*.
