NetworkX中如何实现有向图的Steiner Tree提取计算

NetworkX 内置的steiner_tree接口仅实现了无向图场景的斯坦纳树近似算法，源码层面做了图类型校验，传入有向图（DiGraph/MultiDiGraph）时会直接抛出NetworkXNotImplemented: not implemented for directed type报错。
直接调用to_undirected()把有向图转无向图再计算的方案不可行——转换过程会丢失边的单向指向、单向可达性这些核心结构信息，最终得到的子图很可能存在大量原图标注不存在的反向边，完全不符合有向场景的计算要求。

有向场景下的斯坦纳树正式名称为斯坦纳树形图（Steiner Arborescence），属于NP难问题，NetworkX没有内置对应实现，可以通过以下三种方式实现计算：

• 精确求解（适合小规模图）
  将问题规约为整数线性规划问题，手动定义约束后调用求解器计算：
  1. 首先确定计算的根节点：有向斯坦纳树默认要求所有指定终端节点，都能从根节点出发沿有向边到达
  2. 定义0-1变量标记每条边是否被选入最终子图
  3. 添加强连通约束、终端节点覆盖约束、无环约束
  4. 以选中边的总权重最小为优化目标
     可以配合pulp、ortools等Python求解器库快速实现，节点规模在百级以内时可以拿到全局最优解。
• 近似求解（适合中大规模图，实现成本最低）
  实现有向场景专用的贪心近似算法，全程复用NetworkX的有向图原生接口即可：
  1. 初始化已覆盖节点集合，初始仅包含选定的根节点
  2. 迭代计算：每次找到距离当前已覆盖子图最近的未覆盖终端节点，将两点之间的最短有向路径上所有节点、边加入结果子图，同时把路径上的节点标记为已覆盖
  3. 所有终端都被覆盖后，对结果子图做剪枝，去掉不在任意一条根到终端路径上的冗余边、冗余非终端节点，消除环路
     这个贪心策略的近似比和无向版steiner_tree的近似水平接近，能满足绝大多数工程场景的需求。
• 快速验证方案（仅适合粗略调试）
  如果只是做快速逻辑验证，可以先转无向图计算无向斯坦纳树，再把结果映射回原有向图，逐一校验子图中所有终端节点从根出发的有向可达性，补全缺失的有向路径、剔除不存在的反向边。这个方法得到的结果总边权通常比最优解高30%以上，绝对不能用于正式计算。

注意：不要尝试给有向图的每条单向边补反向边伪装成无向图计算，这种操作和直接转无向图没有区别，得到的结果完全不满足方向约束。

内容的提问来源于stack exchange，提问作者swarajpande4