时间戳

首页 > 解决方案 > networkx: 直径给 13 想找到那些节点或距离是什么

networkx - networkx: 直径给 13 想找到那些节点或距离是什么

问题描述

我想找到最远的节点。我使用了直径，它给了我一个整数值，我应该怎么做才能在直径的起点和终点获得这些点？即通过使用一些函数在图中找到最远的点。

标签： networkxgraph-theory

解决方案

nx.diameter似乎只是找到节点之间最长最短路径的距离，并且 (docs) 模块中的任何内置函数似乎networkx.algorithms.distance_measures 都无法计算您真正要查找的内容。要获得最远的节点，一种选择是使用一系列调用来调用nx.single_source_shortest_path_length(G,n)哪里G是图和n源节点。n这将返回从节点到所有节点的最短路径的长度，G作为由节点键入的字典，值是从节点到源节点的距离n。然后，您可以查看这些 dicts 以找出哪些节点对具有最长的长度。像这样的东西应该工作。

def get_furthest_nodes(G):
    sp_length = {} # dict containing shortest path distances for each pair of nodes
    diameter = None # will contain the graphs diameter (length of longest shortest path)
    furthest_node_list = [] # will contain list of tuple of nodes with shortest path equal to diameter
    
    for node in G.nodes:
        # Get the shortest path from node to all other nodes
        sp_length[node] = nx.single_source_shortest_path_length(G,node)
        longest_path = max(sp_length[node].values()) # get length of furthest node from node
        
        # Update diameter when necessary (on first iteration and when we find a longer one)
        if diameter == None:
            diameter = longest_path # set the first diameter
            
        # update the list of tuples of furthest nodes if we have a best diameter
        if longest_path >= diameter:
            diameter = longest_path
            
            # a list of tuples containing
            # the current node and the nodes furthest from it
            node_longest_paths = [(node,other_node)
                                      for other_node in sp_length[node].keys()
                                      if sp_length[node][other_node] == longest_path]
            if longest_path > diameter:
                # This is better than the previous diameter
                # so replace the list of tuples of diameter nodes with this nodes
                # tuple of furthest nodes
                furthest_node_list = node_longest_paths
            else: # this is equal to the current diameter
                # add this nodes tuple of furthest nodes to the current list    
                furthest_node_list = furthest_node_list + node_longest_paths
                
    # return the diameter,
        # all pairs of nodes with shortest path length equal to the diameter
        # the dict of all-node shortest paths
    return({'diameter':diameter,
            'furthest_node_list':furthest_node_list,
            'node_shortest_path_dicts':sp_length})

请注意，此解决方案假定图形是连接的（有向图是强连接的），您应该是这样，因为您使用nx.diameter. 这应该具有与对直径的调用类似的运行时间，因为该函数执行类似的步骤，它只是不保留导致直径的所有路径链接和节点。请注意，furthest_node_list返回字典中的项目将使每对节点在相反方向上两次（如果节点a和b最短路径等于直径，则两者都(a,b)将(b,a)在列表中）。

推荐阅读