标签: graph-traversal

我引用人工智能:现代方法:

深度优先搜索的属性很大程度上取决于是使用图搜索还是树搜索版本.避免重复状态和冗余路径的图搜索版本在有限状态空间中完成,因为它最终会扩展每个节点.另一方面,树搜索版本并不完整[...].可以在没有额外内存成本的情况下修改深度优先树搜索,以便它检查新状态与从根到当前节点的路径上的状态; 这避免了有限状态空间中的无限循环,但不能避免冗余路径的扩散.

我不明白图搜索是如何完成的,树搜索不是,树是一个特定的图.

此外,我没有明确区分"无限循环"和"冗余路径"......

愿有人向我解释一下吗？

PS.对于有这本书的人来说,这是第86页(第3版).

Apache Giraph vs Neo4j:在这两个图形处理系统中,跨节点的遍历算法是否完全不同？如果我们要遍历说使用Giraph和Neo4j的社交图表存储在单机(非分布式)中的数据,这会表现得更好,为什么？

抽象问题:我有一个大约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" % …

我正在尝试以编程方式计算非常大的电路上的电压变化.

*这个问题似乎可能面向电子产品,但更多的是将算法应用于一组数据.

为了简单起见,
这是一个完整的电路,电压已经计算过:

我原本只给出了电池电压和电阻:

我的问题是并联和串联电路之间的电压计算方式不同.
在SO上提出了一个类似的问题.

一些公式:

When resistors are in parallel:
Rtotal = 1/(1/R1 + 1/R2 + 1/R3 ... + 1/Rn)

When resistors are in series:
Rtotal = R1 + R2 + R3 ... + Rn

欧姆定律:

V = IR
I = V/R
R = V/I

V is voltage (volts)
I is current (amps)
R is resistance(ohms)

我在互联网上找到的每个教程都包括人们在概念上将并联电路分组以获得总电阻,然后使用该电阻来计算串联电阻.

这对于小例子来说很好,但是对于大规模电路来说很难从中推导出算法.

我的问题:
给定一个包含所有完整路径的矩阵,
我有办法计算所有电压降吗？

我目前将系统作为图形数据结构.
所有节点都表示(并且可以通过查找)id号.

所以对于上面的例子,如果我运行遍历,我会得到一个像这样的路径列表:

[[0,1,2,4,0]
,[0,1,3,4,0]]

每个数字都可用于导出实际节点及其相应的数据.我需要对这组数据执行什么样的转换/算法？

电路的某些部分很可能是复合的,而这些复合部分可能会发现它们与其他复合部分并联或串联.

我认为我的问题类似于:http:
//en.wikipedia.org/wiki/Series-parallel_partial_order

我目前有一个存储在列表中的连接列表,其中每个连接是一个连接两个点的有向链接,没有任何点链接到多个点或链接到多个点.例如:

connections = [ (3, 7), (6, 5), (4, 6), (5, 3), (7, 8), (1, 2), (2, 1) ]

应该产生:

ordered = [ [ 4, 6, 5, 3, 7, 8 ], [ 1, 2, 1 ] ]

我尝试使用一种算法来做到这一点,该算法采用输入点和连接列表,并递归调用自身以找到下一个点并将其添加到增长的有序列表中.但是,当我没有从正确的点开始时,我的算法会崩溃(尽管这应该只是反向重复相同的算法),但是当有多个未连接的链时

编写有效算法来订购这些连接的最佳方法是什么？

我试图找出一种遍历图形Scala样式的简洁方法,最好是使用val和不可变数据类型.

给出以下图表,

val graph = Map(0 -> Set(1),
                1 -> Set(2),
                2 -> Set(0, 3, 4),
                3 -> Set(),
                4 -> Set(3))

我希望输出是在给定节点中开始的深度优先遍历.例如,从1开始,应该屈服1 2 3 0 4.

如果没有可变的集合或变量,我似乎无法找到一个很好的方法.任何帮助,将不胜感激.

我想建议一个好的javascript库来操作图形/网络.我对可视化不感兴趣,只是寻找最短的路径和跨越树木.

我看过乌鸦,看起来很不错,但是面向对象.

一个功能模型,如underscore.js是我的偏好,但不是一个要求.

BasicBlock在LLVM框架中获取a的前身的最简单方法是什么？

我已经采取了看DepthFirstIterator和idf_iterator<BasicBlock*>,但实际上我需要做的控制流图的广度优先搜索.

我觉得这应该很容易,但是从我在网上探索的文档或示例中并不明显.

鉴于下面的有向图,我们如何实现后序遍历？

DFS

预订遍历中的访问顺序:1 2 5 4 6 3

在订购后遍历中的访问订单:4 6 5 2 1 3

我有一个问题,我需要在循环图上执行CRUD操作.现在我知道那里有一堆图形数据库,但我有一组特定的用例,这些用例在这些数据库中不受支持(或者至少我不知道它们).

以下是我的构造:

• 节点:可以有多个源和目标
• 定向边缘:连接两个节点
• 节点组:形成一个组的多个节点(与边连接)(简单地说,它是一个较小的图形)
• 有向图:包含多个节点,节点组和边.该图可以是循环的.

以下是我可以拥有的功能:

• 我可以通过定义传入和传出边缘定义来创建节点.
• 我可以通过添加节点并将它们与边连接来创建一个简单的图形.
• 我可以执行标准的图形遍历.
• 我现在可以将图的节点分组并将其称为节点组,我可以在另一个更大的图中使用此节点组的多个实例(就像节点一样).这可以创建复杂的层次结构.
• 我可以创建多个图形,这些图形又使用上述任何结构.
• 我可以对节点和节点组定义进行更改,这意味着可以对图形进行结构更改.如果我对节点或节点组定义进行更改,则还应更新所有图中此节点的所有实例.

现在我明白所有这一切都可以通过关系数据库来完成,这将确保关系完好无损并且查询很简单.但是当存在复杂的图形并且要更新这些图形的多个时,性能将受到影响.

所以,我想知道是否存在一种混合/更好的方法来存储,检索和更新这些图表,与关系数据库相比,这种方法会快得多.

任何想法都会非常有用.提前致谢!