这里实际上有两个问题:首先,你需要想出一个算法来解决这个问题;其次,你需要在 Python 中实现它。
算法
我假设您想要一个最大的分支集合;也就是说,您不能再添加任何分支。如果不需要,则可以考虑最大集合的所有子集。
因此,对于子节点,我们希望尽可能多地采用分支,但又不能让两个父节点共享根节点。换句话说,从每个子节点到每个根节点的邻域中,您最多只能有一条边。这似乎表明您希望首先迭代子节点,然后迭代(邻域的)根节点,最后迭代它们之间的边缘。这个概念给出了以下伪代码:
for each child node:
for each root node:
remember each permissible edge
find all combinations of permissible edges
代码
>>> import networkx as nx
>>> import itertools
>>>
>>> G = nx.DiGraph()
>>> G.add_nodes_from(["r0", "r1", "p0", "p1", "p2", "p3", "p4", "c0", "c1", "c2"])
>>> G.add_edges_from([("r0", "p0"), ("r0", "p1"), ("r1", "p2"), ("r1", "p3"),
... ("r1", "p4"), ("p0", "c0"), ("p1", "c1"), ("p2", "c1"),
... ("p3", "c2"), ("p4", "c2")])
>>>
>>> combs = set()
>>> leaves = [node for node in G if not G.out_degree(node)]
>>> roots = [node for node in G if not G.in_degree(node)]
>>> for leaf in leaves:
... for root in roots:
... possibilities = tuple(edge for edge in G.in_edges_iter(leaf)
... if G.has_edge(root, edge[0]))
... if possibilities: combs.add(possibilities)
...
>>> combs
set([(('p1', 'c1'),),
(('p2', 'c1'),),
(('p3', 'c2'), ('p4', 'c2')),
(('p0', 'c0'),)])
>>> print list(itertools.product(*combs))
[(('p1', 'c1'), ('p2', 'c1'), ('p3', 'c2'), ('p0', 'c0')),
(('p1', 'c1'), ('p2', 'c1'), ('p4', 'c2'), ('p0', 'c0'))]
上述代码看起来应该是可行的,尽管我还没有测试过。