如何获取一棵树的所有子树分支组合

Question

我有以下树，其分支从 br_a 到 br_i 和一个根点。

我想通过在Python中仅排列分支（而不是单个顶点）来生成这棵树的所有可能的子树排列。例如，

分支的所有排列都必须连接到根点，我不希望重复。我该如何做到这一点，我目前将此树作为 BigTree 对象或 NetworkX 图。这些库有任何函数可以做这样的事情吗？

Answer 1

IIUC，这是一种可能的选择：

all_paths = [
    p for desc in nx.descendants(G, "r0")
    for p in nx.all_simple_paths(G, "r0", desc)
]

perms = set()
for path in all_paths:
    sg_nodes = set()
    for node in path:
        sg_nodes.add(node)
        for data in d.values():
            if node in data["nodes"]:
                sg_nodes.update(data["nodes"])
    perms.add(frozenset(G.subgraph(sg_nodes).nodes))

输出：

for idx, sg_nodes in enumerate(perms, 1):
    sg = G.subgraph(sg_nodes)
    print(f"Perm{idx}: {list(nx.topological_sort(sg))}")

Perm1: ['r0', 'a0', 'a1', 'd0', 'd1']
Perm2: ['r0', 'b0', 'b1', 'b2', 'f0']
Perm3: ['r0', 'c0', 'i0', 'i1', 'i2']
Perm4: ['r0', 'c0']
Perm5: ['r0', 'c0', 'h0', 'h1', 'h2']
Perm6: ['r0', 'b0', 'b1', 'b2']
Perm7: ['r0', 'a0', 'a1']
Perm8: ['r0', 'a0', 'a1', 'e0', 'e1']
Perm9: ['r0', 'b0', 'b1', 'b2', 'g0']

所用图表：

import networkx as nx

d = {
    "root point": {"nodes": ["r0"], "color": "lightpink"},
    "br_a": {"nodes": ["a0", "a1"], "color": "mediumpurple"},
    "br_b": {"nodes": ["b0", "b1", "b2"], "color": "magenta"},
    "br_c": {"nodes": ["c0"], "color": "cyan"},
    "br_d": {"nodes": ["d0", "d1"], "color": "lime"},
    "br_e": {"nodes": ["e0", "e1"], "color": "yellow"},
    "br_f": {"nodes": ["f0"], "color": "crimson"},
    "br_g": {"nodes": ["g0"], "color": "darkgreen"},
    "br_h": {"nodes": ["h0", "h1", "h2"], "color": "blue"},
    "br_i": {"nodes": ["i0", "i1", "i2"], "color": "brown"}
}

connections = [
    ("r0", "a0"),
    ("a0", "a1"),
    ("a1", "d0"),
    ("a1", "e0"),
    ("d0", "d1"),
    ("e0", "e1"),
    ("r0", "b0"),
    ("b0", "b1"),
    ("b1", "b2"),
    ("b2", "f0"),
    ("b2", "g0"),
    ("r0", "c0"),
    ("c0", "h0"),
    ("h0", "h1"),
    ("h1", "h2"),
    ("c0", "i0"),
    ("i0", "i1"),
    ("i1", "i2")
]

G = nx.DiGraph()

for br, data in d.items():
    G.add_nodes_from(data["nodes"], branch=br)

G.add_edges_from(connections)

Answer 2

基于 Timeless 的 answer，但添加了所有排列，包括简单路径。

d = {
    "root point": {"nodes": ["r0"], "color": "lightpink"},
    "br_a": {"nodes": ["a0", "a1"], "color": "mediumpurple"},
    "br_b": {"nodes": ["b0", "b1", "b2"], "color": "magenta"},
    "br_c": {"nodes": ["c0"], "color": "cyan"},
    "br_d": {"nodes": ["d0", "d1"], "color": "lime"},
    "br_e": {"nodes": ["e0", "e1"], "color": "yellow"},
    "br_f": {"nodes": ["f0"], "color": "crimson"},
    "br_g": {"nodes": ["g0"], "color": "darkgreen"},
    "br_h": {"nodes": ["h0", "h1", "h2"], "color": "blue"},
    "br_i": {"nodes": ["i0", "i1", "i2"], "color": "brown"}}

connections = [
    ("r0", "a0"),
    ("a0", "a1"),
    ("a1", "d0"),
    ("a1", "e0"),
    ("d0", "d1"),
    ("e0", "e1"),
    ("r0", "b0"),
    ("b0", "b1"),
    ("b1", "b2"),
    ("b2", "f0"),
    ("b2", "g0"),
    ("r0", "c0"),
    ("c0", "h0"),
    ("h0", "h1"),
    ("h1", "h2"),
    ("c0", "i0"),
    ("i0", "i1"),
    ("i1", "i2")]

G = nx.DiGraph()

for br, data in d.items():
    G.add_nodes_from(data["nodes"], branch=br, color=data['color'])

G.add_edges_from(connections)

descendants = nx.descendants(G, "r0")
filtered_descendants = [node for node in descendants
                        if len(list(G.successors(node))) == 0 or len(list(G.successors(node))) > 1]

# get paths
all_paths = [
    p for desc in filtered_descendants
    for p in nx.all_simple_paths(G, "r0", desc)
]

perms = set()
for path in all_paths:
    sg_nodes = set(path)
    perms.add(frozenset(G.subgraph(sg_nodes).nodes))

# Get all combinations of different lengths (1 to len(perms))
all_combinations = []
for r in range(1, len(perms) + 1):
    combinations_r = itertools.combinations(perms, r)
    all_combinations.extend(combinations_r)

# Merge each tuple of frozensets into a single frozenset
merged_combinations = [frozenset().union(*comb) for comb in all_combinations]
merged_combinations = set(merged_combinations)