节点作为网络x中的网格点

问题描述 投票:0回答:1

我有一个树状图,看起来像长长的树干,有树枝,每个树枝上可以有 "叶子"。它的样子基本是这样的(边没有图)。

    o
   oo
    oo     o
    o      o     o
oooooooooooooooooooooooooo
    o
    o

树干的长度可以是任意的 每一个垂直的分支都是10个节点的顺序 树叶最多只有一个节点。树干的每个节点最多只有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)}

我试图通过检查树干上的一个节点是否有两个以上的邻居来计算垂直分支,然后从一个节点到另一个节点进行迭代,但当遇到叶子时,我遇到了麻烦。此外,对于大的树干来说,它的伸缩性也不好。

有没有更简单的方法可以用networkx来实现?

EDIT:一个最简单的例子是。

G = nx.path_graph(10)
G.add_edges_from([(3,11),(11,12),(12,13),(13,14),(13,15),(1,16)])
python graph nodes networkx
1个回答
1
投票

我不完全确定你期望通过添加你的图的垂直分支得到什么输出,也许一个最小的例子会有助于澄清。但是,如果我理解的设置是正确的,我建议你得到的是 后备箱 的图形,而不是用下面的方法。

你可以先找到 nx.eccentricity 的图,也就是一个给定节点与其他所有节点之间的最大距离。然后,通过找到它的最大值,或者换句话说,那么图的直径,我们可以限制搜索的。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 应该足够了。

那么对于分支来说,也许可以考虑在主干节点上迭代,然后发现主干节点的 树枝 和后续的叶子通过广度优先搜索,忽略路径Co tianing节点从主干,或已经遍历。

热门问题
推荐问题
最新问题