networkx中作为晶格站点的节点

Question

我有树状图，看起来像长树干和树枝，每个树枝上都可以有“叶子”。它看起来基本上像（没有图片）：

    o
   oo
    oo     o
    o      o     o
oooooooooooooooooooooooooo
    o
    o

主干的长度可以是任意的，每个垂直分支有十个节点，叶子最多只有一个节点。主干的每个节点最多有4条边。由于垂直的“叶子”保证永远不会重叠，我希望能够转换一个图，使每个节点都位于晶格的一个点上，并获得该形式的字典

dict = {n1: (x1, y2), n2: (x2, y2), ...}

使用ni节点ID和(xi, yi)一对整数指示晶格上的位置。我试图通过使用图G的所有节点之间的最大距离来获取主干，从而实现它：

nodeList = list(G.nodes)
dic = {}
for i, n1 in enumerate(nodeList):
        for n2 in nodeList[i+1:]:
            dic[(n1, n2)] = networkx.shortest_path(G,source=n1,target=n2)

    dicLength = {k: len(dic[k]) for k in dic}
    k = max(dicLength, key=dicLength.get)
    trunk = dic[k]

然后，我可以将躯干设置为晶格的x坐标：

lattice = {k: (i, 0) for i, k in enumerate(trunk)}

然后，我试图通过检查主干中的a节点是否有两个以上的邻居来计算垂直分支，并在节点之间进行迭代，但遇到叶子时，我遇到了麻烦。此外，它不适合大型树干

使用networkx有没有更简单的方法

编辑：最简单的例子是：

G = nx.path_graph(10)
G.add_edges_from([(3,11),(11,12),(12,13),(13,14),(13,15),(1,16)])

Answer 1

我不完全确定通过添加图形的垂直分支，您希望得到什么样的输出，也许一个简单的示例有助于澄清。但是，如果我正确理解了设置，我建议您用以下方式获取图形的主干

您可以从查找图的^{}开始，即给定节点与所有其他节点之间的最大距离。然后，通过找到它的最大值，或者换句话说，然后是图的直径，我们可以将shortest_path的搜索限制在图中只有一对最大距离的节点（如果一个主干的两端都没有分支，那么就没有必要了，找到两个extrema_cand之间的最短路径就足够了）：

ecc = nx.eccentricity(G)
diam = max(ecc.values())
extrema_cand = [node for node, length in ecc.items() if length==diam]

现在，我们只能在上述节点子集上查找最短路径：

from itertools import combinations
trunk=[]
for nodes in combinations(extrema_cand, r=2):
    trunk.append(nx.shortest_path(G,*nodes))
trunk = max(trunk, key=len)

通过过滤最后一行中的max，我们可以确保节点不在图的两侧。尽管如前所述，如果只有一个主干，nx.shortest_path(G,*nodes)中仅有的一对节点上的extrema_cand就足够了

然后对于分支，可能的想法是迭代主干节点，并通过广度优先搜索发现分支和随后的叶子，忽略与主干节点相连的路径，或者已经穿过的路径