良好的图遍历算法

Question

抽象问题:我有一个大约250,000个节点的图形,平均连接性大约为10.找到一个节点的连接是一个漫长的过程(10秒钟就可以了).将节点保存到数据库也需要大约10秒钟.我可以非常快速地检查数据库中是否已存在节点.允许并发,但一次不超过10个长请求,您将如何遍历图表以获得最快的覆盖率.

具体问题:我正在尝试抓一个网站用户页面.为了发现新用户,我正在从已知用户那里获取好友列表.我已经导入了大约10%的图形但是我一直陷入循环或使用太多内存记住太多节点.

我目前的实施:

def run() :
    import_pool = ThreadPool(10)
    user_pool = ThreadPool(1)
    do_user("arcaneCoder", import_pool, user_pool)

def do_user(user, import_pool, user_pool) :
    id = user
    alias = models.Alias.get(id)

    # if its been updates in the last 7 days
    if alias and alias.modified + datetime.timedelta(days=7) > datetime.datetime.now() :
        sys.stderr.write("Skipping: %s\n" % user)
    else :
        sys.stderr.write("Importing: %s\n" % user)
        while import_pool.num_jobs() > 20 :
            print "Too many queued jobs, sleeping"
            time.sleep(15)

        import_pool.add_job(alias_view.import_id, [id], lambda rv : sys.stderr.write("Done Importing %s\n" % user))

    sys.stderr.write("Crawling: %s\n" % user)
    users = crawl(id, 5)
    if len(users) >= 2 :
        for user in random.sample(users, 2) :
            if (user_pool.num_jobs() < 100) :
                user_pool.add_job(do_user, [user, import_pool, user_pool])

def crawl(id, limit=50) :
    '''returns the first 'limit' friends of a user'''
    *not relevant*

当前实施的问题:

• 陷入我已经导入的派系中,从而浪费时间并且导入线程处于空闲状态.
• 当他们被指出时会添加更多.

因此,欢迎边际改进,以及完全重写.谢谢!

Answer 1

要记住您已访问过的用户的ID,您需要一张长度为250,000的整数的地图.这远远不是"太多".只需保持这样的地图,只遍历导致已经未被发现的用户的边缘,在找到这样的边缘时将它们添加到该地图.

据我所知,您已接近实施广度优先搜索(BFS).检查谷歌有关此算法的详细信息.当然,不要忘记互斥体 - 你需要它们.