Блог

Я хочу найти самые дальние узлы. Я использовал диаметр, и он дал мне целочисленное значение, что мне делать, чтобы получить эти точки в начале и конце диаметра? т.е. найдите самые дальние точки на графике, используя некоторую функцию.

nx.diameter Похоже, что нужно только найти расстояние от самого длинного кратчайшего пути между узлами, и ни одна из встроенных функций в модуле networkx.algorithms.distance_measures (docs), похоже, не вычисляет то, что вы действительно ищете. Чтобы получить самые дальние узлы, одним из вариантов является использование последовательности вызовов 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 . Это должно иметь такое же время выполнения, что и вызов diamater, потому что эта функция выполняет аналогичные шаги, она просто не сохраняет все ссылки на пути и узлы, которые приводят к диаметру. Обратите furthest_node_list внимание, что элемент в возвращаемом dict будет иметь каждую пару узлов дважды только в противоположном направлении (если узлы a и b имеют кратчайший путь, равный диаметру, оба (a,b) и (b,a) будут в списке).

Узлы на периферии — это те узлы, которые разделены расстоянием диаметра. Их легко вычислить в networkx. Для некоторого связного графа g:

 n1, n2 = nx.periphery(g)
diameter_nodes = nx.shortest_path(g, source = n1, target = n2)
  

обратите внимание, что это предполагает, что у вас будет ровно два узла на периферии. В общем, это не так, и вам придется реализовать некоторую логику, чтобы определить, какой кратчайший путь вы хотите вычислить. Кроме того, не все пары узлов на периферии обязательно имеют расстояние, равное диаметру. так что это еще кое-что, с чем следует быть осторожным.