NetworkX查找满足入度出度、时长和约束的有向图子图

现有一个有向图，需要从中提取所有满足如下条件的子图，每个符合要求的子图需同时满足：

• 子图内所有节点的入度恰好为1
• 子图内所有节点的出度恰好为1
• 子图内所有节点的给定属性duration（时长）之和小于等于给定阈值K

小型测试示例 #

测试用图的构建代码如下：

import networkx as nx

G = nx.DiGraph()

G.add_nodes_from([
    (1, {"name": "node 1", "duration": 30}),
    (2, {"name": "node 2", "duration": 40}),
    (3, {"name": "node 3", "duration": 20}),
    (4, {"name": "node 4", "duration": 10}),
    (5, {"name": "node 5", "duration": 30}),
    (6, {"name": "node 6", "duration": 20}),
    (7, {"name": "node 7", "duration": 50}),
    (8, {"name": "node 8", "duration": 40}),
])

links = ( (1,2), (2,3), (3,4), (4,5), (1,8), (8,7), (7,6), (6,5))

G.add_edges_from(links)

该问题存在多组合法解，以下为其中一组期望输出示例：

( (2,3,4), (6,7), (8) )

内容的提问来源于stack exchange，提问作者Timothée HENRY