blackhole-diffusion 0.1.0

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% 满秩解构，所有环代数独立且绝对无弦。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 数据集独立基准测试报告
• 💼 商业授权咨询