为什么在查找直径时，networkx 说我的有向图已断开？

Question

我正在爬行slideshare.net图，从我的节点开始，跟踪BFS中的所有用户，直到访问的节点数为1000。我按以下方式执行BFS：

from urllib.request import urlopen
from collections import deque
import sys
import json
import codecs
import csv
import io
import hashlib
import time
import xml.etree.ElementTree as etree
queue = deque(["himanshutyagi11"])
while len_visitedset < 1ooo:
        vertex = queue.pop()
        if vertex in visited:
            continue
        visited.add(vertex)
        length_visited = len(visited)
        print(vertex,length_visited)
        crawl(vertex)

crawl() 是一个函数，我在其中进行幻灯片 api 查询，如此处所述， 使用我的shared_secret 和 api_key（在 api 注册时给出）创建查询有效负载，发送查询并解析存储在变量“response”中的 XML 响应'。解析后，我将当前节点的联系人添加到队列中。

request_timestamp = int(time.time())
request_hash_string = shared_secret+str(request_timestamp)
request_hash_value = hashlib.sha1(request_hash_string.encode('utf-8')).hexdigest()
request_url = 'https://www.slideshare.net/api/2/get_user_contacts?username_for='+username+'&api_key='+api_key+'&hash='+request_hash_value+'&ts='+str(request_timestamp)
response = etree.parse(urlopen(request_url)).getroot()
# Append all the adjacent nodes of this user to the queue.
    for child in response:
        friend_name = child[0].text
        queue.appendleft(friend_name)
edge_file = open('non_anonymized.csv','a')
    for child in response:
        f_name = child[0].text                              # Name of friend is stored in variable 'f_name'
        edge_file.write(username+','+f_name+'\n')          # username is the name of user currently being crawled
    edge_file.close()

在爬行时，我还创建了一个 edgelist.csv 文件，其中包含图中的所有边。这个文件看起来没问题。此外，其他函数，如 Degree()、in_ Degree()、average_clustering() 似乎工作正常。

然后我使用 networkx 创建一个图，其中有 1000 个节点。但是如果我尝试使用以下函数找到该图的直径：

diameter = nx.diameter(graph)

使用上面的代码，我无法找到图形的直径，这不会返回任何内容，并且我的程序卡在这一行。对可能发生的事情有什么见解吗？我的是一个连通图。我正在使用to_undirected()函数将其转换为无向函数。我厌倦了用有向图运行它，并且出现以下错误
networkx.exception.NetworkXError: Graph not connected: infinite path length

我的问题是，既然我使用BFS爬行，怎么才能断开连接呢？

Python 3.4
网络x 1.9.1

Answer 1

直径的源代码在这里。它依赖于eccentricity源代码中位于该函数上方的函数。 eccentricity找到从一个节点到所有其他节点的最短路径。您收到的错误消息来自这部分代码：

if L != order:
    msg = "Graph not connected: infinite path length"
    raise networkx.NetworkXError(msg)

这L是从给定节点可到达的节点数，order也是网络中的节点数。 L != order表示存在从给定节点无法到达的节点。在无向网络的情况下，这意味着网络未连接。但是，就您而言，您有一个定向网络。对于有向网络来说L != order意味着该网络不是“强连接”的。它实际上可能是弱连接的，你的也可能是弱连接的。

所以你遇到了一条不太准确的错误消息。

对于您创建的有向网络，直径是无限的：如果有一个节点u没有到 的路径v，则意味着直径无限。