如何在图表中显示直径？

Question

我有一个包含 5 个节点的完整图 G，我必须找到 G（随机选择的节点）的直径，并将该直径绘制为红色。我如何使用 Networkx 和 Python 来做到这一点？这些是我的尝试。另外我需要说的是它们更多，但唯一的区别是我尝试使用其他函数（子图、算法等）而不是最短路径。另外，我需要解释一下随机节点意味着你选择一个开始直径随机

尝试1

import networkx as nx

G = nx.complete_graph(5)

dg = nx.shortest_path(G)

edge_colors = ['red' if e in dg.edges else 'black' for e in G.edges]

nx.draw(G, edge_color=edge_colors)

尝试2

def get_diameters(graph):
    diams = []
    for g in nx.connected_component_subgraphs(graph):
        diams.append(nx.diameter(g))
    diams = list(filter(lambda a: a != 0, diams))
    return np.array(diams) Graph.number_of_nodes()

Answer 1

据我了解您的问题，您不是在寻找图本身的直径，而是在给定随机起始节点的情况下寻找图中的最长最短路径。这可以通过使用

nx.shortest_path

和

source

关键字参数来实现，并为其提供一个随机起始节点。我们可以查看生成的字典，找到最长的最短路径，并将形成该路径的边缘绘制为红色。

代码

import networkx as nx
import random

# Create graph
G = nx.fast_gnp_random_graph(10, 0.3)

# Pick a random node
source = random.choice(list(G.nodes))

# Find the longest shortest path from the node
shortest_paths = nx.shortest_path(G, source=source)
target = max(shortest_paths, key=lambda i: len(shortest_paths[i]))
l_s_path = shortest_paths[target]
l_s_path_edges = list(zip(l_s_path, l_s_path[1:]))

# Draw the graph, then draw over the required edges in red.
pos = nx.spring_layout(G)
nx.draw(G, pos=pos, with_labels=True)
nx.draw_networkx_edges(G, edge_color='r', edgelist=l_s_path_edges, pos=pos)

输出

注意，在本例中，图形的直径为4；最长的最短路径是从节点 6 到节点 4。随机选择的源节点是 7 - 从节点 7 开始的最长最短路径的长度为 3。