Metadata-Version: 2.4
Name: blackhole-diffusion
Version: 0.1.1
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% 满秩解构，所有环代数独立且绝对无弦。20 个基准数据集（5000-10000 边）全部验证通过。
- **Deployment Flexibility**：专为 AWS Lambda、Docker 精简镜像、金融审计集群、在线编程平台等无法编译 C 扩展的环境设计。
- **Dense to Sparse**：支持从纯 3-环稠密图到纯 4-环网格再到混合环长大规模图的全谱系拓扑。

---

## 📦 Versions / 版本

| 特性 | 基础版 (Base) | 优化版 (Pro) | 完美版 (Enterprise) |
|---|---|---|---|
| **开源** | ✅ MIT | ❌ 闭源商业 | ❌ 闭源商业 |
| **消元引擎** | CSR | Adaptive（动态策略切换） | Adaptive（动态策略切换） |
| **环长窗口** | 不限 | 3–6 | 3–8 |
| **近似 MCB** | 部分图类 ≤1% | ❌ | ✅ 全数据集 ≤1% |
| **边数上限** | 不限 | ~15000 | ~20000 |
| **定价** | 免费 | 商业授权 | 商业授权 |

**基础版（本仓库）**：满秩无弦环基，零依赖，MIT 开源。纯 CSR 消元引擎（含黑洞边界检测与交替湮灭），短环稠密图和纯网格图上输出接近或等于 MCB 精度。

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

**完美版 (Enterprise)**：环长自定义 3-8 环。在 20 张基准图中 13 张精确命中 MCB，MCB=7 的图 5/5 零漏网。适合需要精确最小环基但装不了 igraph 的场景。

> 📖 完整对比与定价详见 [技术说明文档]() ｜ 基础版 vs 商业版实跑对比见 [算法分析 README]()

---

## 🛠 Algorithmic Architecture / 算法架构

### 边向扩展 vs 生成树

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

### 消元引擎：CSR 消出满秩，Adaptive 消出密秩

基础版使用 **CSRBlackholeDevourer**（压缩稀疏行消元器 + 黑洞边界检测 + 交替湮灭）。擅长短环和稠密图，在纯 4 环网格上反超 igraph C 实现。

商业版使用 **AdaptiveBlackholeDevourer**（自适应动态消元器）。核心优势不在单次消元更快，而在消元结果的拓扑密度——更密的基结构使黑洞视界提前闭合，候选池大幅压缩，产生二阶加速效应。

### 语言税

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

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

| 数据集 | BH·基础版 (Py) | igraph (C) |
|--------|:-----:|:--------:|
| edge007 (5k边) | **5.52s** | 8.65s |
| edge017 (10k边) | **22.95s** | 51.26s |

规模越大差距越显著，从 1.6 倍扩大到 2.2 倍。

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

---

## 📊 Quick Benchmark / 快速基准

以下为基础版纯 CSR 消元 vs igraph C 实现的端到端对比。所有数据集均通过满秩审计（Rank 100% 对齐，0 弦环）。

### 5000 边级别

| Dataset | V / E / R | MCB | iGraph (C) | BH·Base (Py) | Ratio |
|---------|-----------|:---:|:--------:|:----------:|:----:|
| edge001 | 141/5072/4932 | 3 | 0.38s | 3.34s | 8.8× |
| edge002 | 223/4997/4775 | 4 | 0.71s | 8.22s | 11.5× |
| edge003 | 1666/4989/3324 | 7 | 2.85s | 43.03s | 15.1× |
| edge004 | 1000/4975/3976 | 5 | 2.02s | 22.15s | 11.0× |
| edge005 | 1666/4998/3333 | 12 | 3.20s | 25.03s | 7.8× |
| edge006 | 1000/5000/4001 | 7 | 2.23s | 27.50s | 12.3× |
| **edge007** | 2500/4900/2401 | 4 | 8.65s | **5.52s** | **0.64× 🔥** |
| edge008 | 2500/5400/2901 | 12 | 5.39s | 41.39s | 7.7× |
| edge009 | 2500/5000/2501 | 11 | 6.09s | 65.97s | 10.8× |
| edge010 | 1250/5000/3751 | 6 | 5.00s | 45.21s | 9.0× |

### 10000 边级别

| Dataset | V / E / R | MCB | iGraph (C) | BH·Base (Py) | Ratio |
|---------|-----------|:---:|:--------:|:----------:|:----:|
| edge011 | 200/10053/9854 | 3 | 1.33s | 8.47s | 6.4× |
| edge012 | 316/10167/9852 | 4 | 3.53s | 25.61s | 7.3× |
| edge013 | 3333/9990/6658 | 7 | 14.70s | 200.7s | 13.7× |
| edge014 | 2000/9975/7976 | 6 | 10.73s | 176.4s | 16.4× |
| **edge017** | 4900/9660/4761 | 4 | 51.26s | **22.95s** | **0.45× 🔥** |
| edge019 | 5000/10000/5001 | 11 | 54.73s | 223.0s | 4.1× |

> **注**：
> - 除纯 4-环网格（edge007/017）外，igraph 在计时上更快——这在 Python 实现中是预期内的。
> - MCB ≤ 4 的图（edge001/002/004/007/011/012/017）基础版表现优异，基总边数与 igraph 精确对齐。MCB ≥ 7 的长环图候选池膨胀导致耗时显著上升，这些正是商业版 Adaptive 消元的覆盖范围。
> - 完整 20 数据集及三版对比见独立基准测试报告。

---

## 📐 Mathematical Guarantees / 数学保证

- **满秩无弦环基**：每个环是简单的、无弦的、代数独立的。秩 = E − V + C（连通分量数）。20 基准全部验证通过。
- **安全上界定理**：已有一个满秩无弦环基 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 + Adaptive 动态消元）
- 环长跨度大、需要 MCB 精度 → **Enterprise**（环长 3-8 + MCB ≤1%）

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

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

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

### Q: 为什么商业版消元更强？

基础版 CSR 消元保证满秩，但消元结果拓扑稀疏，长环图上候选池膨胀。商业版 Adaptive 消元在同等满秩条件下产生更密集的基结构，触发黑洞视界闭合的速度快一个数量级。一句话：**CSR 消出满秩，Adaptive 消出密秩。**

---

## 📜 License

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

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

---

## 🔗 Links

- 📖 [完整技术说明文档]()
- 📊 [20 数据集独立基准测试报告]()
- 🔬 [基础版 vs 商业版实跑对比（算法分析 README）]()
- 💼 [商业授权咨询]()
