Metadata-Version: 2.4
Name: blackhole-diffusion
Version: 0.1.0
Summary: Pure Python full-rank chordless cycle basis — zero dependencies
Author: @m15154178071-cmyk
License: MIT
Project-URL: Homepage, https://github.com/m15154178071-cmyk/blackhole-diffusion
Project-URL: Repository, https://github.com/m15154178071-cmyk/blackhole-diffusion
Project-URL: Issues, https://github.com/m15154178071-cmyk/blackhole-diffusion/issues
Keywords: graph,cycle,cycle-basis,chordless-cycle,minimum-cycle-basis,graph-theory,topology,zero-dependencies,pure-python
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Topic :: Scientific/Engineering :: GIS
Classifier: Topic :: Scientific/Engineering :: Physics
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Dynamic: license-file

# Blackhole Diffusion（黑洞弥散）

> A pure-Python graph engine for extracting full-rank chordless cycle bases. Zero dependencies — runs anywhere Python runs.
>
> 纯 Python 标准库实现的图算法引擎，专注于提取满秩无弦环基。零外部依赖，即插即用。

---

## 💡 Core Features / 核心特性

- **Zero External Dependencies**：100% Python 标准库构建。无 C 编译、无 wheel 文件、无第三方包。任何 Python 3.x 环境即插即用。
- **Full-Rank Correctness Guarantee**：输出结果 100% 满秩解构，所有环代数独立且绝对无弦。30 个基准数据集（5000-15000 边）全部验证通过。
- **Deployment Flexibility**：专为 AWS Lambda、Docker 精简镜像、金融审计集群、在线编程平台等无法编译 C 扩展的环境设计。
- **Dense to Sparse**：支持从纯 3-环稠密图到纯 4-环网格再到混合环长大规模图的全谱系拓扑。

---

## 📦 Versions / 版本

| 特性 | 基础版 (Base) | 优化版 (Pro) | 完美版 (Enterprise) |
|---|---|---|---|
| **开源** | ✅ MIT | ❌ 闭源商业 | ❌ 闭源商业 |
| **环长自定义** | ❌ | ✅ 3-6 环 | ✅ 3-8 环 |
| **近似 MCB** | 部分图类 ≤1% | ❌ | ✅ 全数据集 ≤1% |
| **边数上限** | 不限 | ~15000 | ~20000 |
| **定价** | 免费 | 商业授权 | 商业授权 |

**基础版（本仓库）**：满秩无弦环基，零依赖，MIT 开源。短环稠密图和纯网格图上输出接近或等于 MCB 精度。

**优化版 (Pro)**：环长自定义 3-6 环。窄窗口 + 激进截断，适合分子拓扑、电路网表分析等需要特定环长区间的场景。

**完美版 (Enterprise)**：环长自定义 3-8 环 + 全基准 MCB 误差 ≤1%。宽窗口 + 宽松覆盖，适合需要精确最小环基但装不了 igraph 的场景。

> 📖 完整对比与定价详见 [技术说明文档]()

---

## 🛠 Algorithmic Architecture / 算法架构

### 边向扩展 vs 生成树

传统环搜索算法（包括 igraph）依赖最短生成树的动态维护。Blackhole Diffusion 采用**边向扩展 + 碰撞消元**：不维护全局生成树，按环长维度逐维搜索无弦环，边搜边消元，用当前基的最长环作为动态剪枝上界。

### 语言税

Python 相对于 C++ 有 ~15x 的字节码层面固有开销（可测下界）。实际消元过程中，亿次级 XOR + 随机内存访问 + Python 对象分配的真实开销远超此值。因此直接对比 BH 和 igraph 的耗时不能等价反映算法本身效率。

但在纯 4-环网格上，这一差距被算法效率完全逆转：

| 数据集 | BH·基础版 (Py) | igraph (C) |
|--------|:-----:|:--------:|
| edge007 (5k边) | **5.1s** | 8.7s |
| edge017 (10k边) | **22.5s** | 51.5s |
| edge027 (15k边) | **55.3s** | 198.8s |

规模越大反越狠，从 1.7x 到 3.6x。

> 📖 完整 30 数据集基准、语言税分析及 MCB 精度对比见 [技术说明文档 / 独立基准测试报告]()

---

## 📊 Quick Benchmark / 快速基准

以下为 5000 边级别 10 组经典数据集的简要对比（基础版 vs igraph C 实现）：

| Dataset | V / E / R | Lang Gap | iGraph (C) | BH·Base (Py) | Ratio |
|---------|-----------|:-------:|:--------:|:----------:|:----:|
| edge001 | 141/4964/4824 | 14.8× | 0.39s | 2.50s | 6.4× |
| edge002 | 223/4970/4748 | 17.5× | 0.64s | 7.68s | 12.0× |
| edge003 | 1666/4989/3324 | 15.5× | 3.05s | 42.39s | 13.9× |
| edge004 | 1000/4975/3976 | 17.1× | 2.20s | 55.09s | 25.1× |
| edge005 | 1666/4998/3333 | 14.9× | 3.35s | 21.93s | 6.5× |
| edge006 | 1000/5000/4001 | 16.7× | 2.13s | 25.00s | 11.7× |
| **edge007** | 2500/4900/2401 | 15.7× | 8.64s | **5.12s** | **0.59× 🔥** |
| edge008 | 2500/5400/2901 | 13.6× | 5.17s | 36.77s | 7.1× |
| edge009 | 2500/5000/2501 | 14.6× | 5.86s | 56.25s | 9.6× |
| edge010 | 1250/5000/3751 | 19.5× | 4.84s | 39.74s | 8.2× |

> **注**：语言税列是微基准测得的 Python vs C++ 原子操作差距（下界），不等同于端到端耗时比。除 edge007 外，igraph 在计时上更快——这在 Python 实现中是预期内的。完整 30 数据集（含 5k/10k/15k 三级规模）及三版对比见独立基准测试报告。

---

## 📐 Mathematical Guarantees / 数学保证

- **满秩无弦环基**：每个环是简单的、无弦的、代数独立的。秩 = E − V + C（连通分量数）。30 基准全部验证通过。
- **安全上界定理**：已有一个满秩无弦环基 B，其最长环长度为 M。所有可能存在的更优基的环长均 ≤ M。M 是后续所有环搜索的精确剪枝上界（存在性证明保证，非启发式）。

---

## 🎯 典型应用场景

- **GIS 自动化**：空间拓扑重建、矢量线转面、地籍地块属性映射
- **无服务器 & 微服务**：AWS Lambda、Cloud Functions 即插即用
- **电路网表分析**：反馈回路追踪、回路检查、拓扑块隔离
- **分子拓扑环提取**：零依赖流水线中直接识别二级结构环
- **金融隔离集群**：纯 Python 代码秒级审计通过

---

## ⚖️ FAQ

### Q: 为什么不直接用 igraph？

igraph 需要编译 C 核心。在 AWS Lambda、Docker 精简镜像、金融审计集群等环境中，安装编译二进制往往被禁止或需数周审批。Blackhole Diffusion 解决的正是 igraph 进不去的场景。两者互补，非替代。

### Q: 基础版、优化版、完美版怎么选？

- 图以 3-4 环为主 → **基础版（免费）**，最快，结果精确
- 图以 4 环网格为主 → **基础版（免费）**，比 igraph C 实现还快
- 需要特定环长区间（如 5-6 环）→ **Pro**（环长 3-6）
- 环长跨度大、需要 MCB 精度 → **Enterprise**（环长 3-8 + MCB ≤1%）

不确定先用免费基础版跑一下，看环长分布和基总边数是否满足需求。

### Q: 为什么环长分布与 igraph 偶尔不同？

两者都是数学上有效的满秩基。基础版的边向扩展策略倾向于找到更长、更多样的环——这是刻意设计选择，追求环长多样性而非绝对最短总环长。商业版在此之上通过约束环长窗口逼近 MCB。

---

## 📜 License

基础版：MIT License — 自由使用、修改、分发。

优化版 & 完美版：闭源商业授权。详见 [技术文档 / 商业授权咨询]()。

---

## 🔗 Links

- 📖 [完整技术说明文档]()
- 📊 [30 数据集独立基准测试报告]()
- 💼 [商业授权咨询]()
