blackhole-diffusion 0.1.1

Pure Python full-rank chordless cycle basis — zero dependencies

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）
• 💼 商业授权咨询