标签: graph-theory

我正在考虑以下问题(非常粗略的描述):

假设我们有一个图表,其中边缘被分配了一些非负成本,一个起始节点s和一些成本常数C.找出:

• 一组节点N,从到达s那里的最短路径的从开始节点的成本s在任何节点N不大于C.
• 对于上面的每个e集合 - 最短路径的成本.

基本上Dijkstra有成本约束.

我的主要问题是:图论中这个问题的正确术语是什么？

我一直在关注"可访问性"或"可达性",但这些似乎是错误的关键字.

最后,我正在寻找一种算法,它可以在一个(不可修改的)但相当大的(可能约1亿个边缘)图形上并行地有效地回答许多这样的查询.我想查看文献,但需要提供正确的关键词提示.

更新:我的实际问题如下.

假设我们获得了一个大陆规模的道路网络(模拟为有向图,在边缘和节点上具有一些属性,如果它是行人路或高速公路).边缘成本是旅行时间.

我想回答用户查询,例如:从某个给定位置(图形节点)开始,哪些节点可在1小时内到达？

我也想非常快地(对于许多用户来说,如果可能的话,<200-300ms)(并且如果可能的话,> 200,如果可能)并行地回答这些查询.

我认为应该至少有两种可能的优化:

• 一些合理大小的预计算,例如预先计算的所选"中心"节点的距离矩阵.
• 如果搜索是并行进行的,则可以从彼此的"临时结果"中获益.

我自己有一些想法,但我首先要检查文献,以避免重新发明轮子.

上图所示此连结的的" 的曲线图具有6个顶点和7层的边缘,其中所述顶点在最左的无6是叶顶点或侧链顶点. "具有直径为4？对还是错？

定义是

图的直径是图中任何顶点的最大偏心率.也就是说,它是任何一对顶点之间的最大距离.要查找图形的直径,首先要找到每对顶点之间的最短路径.任何这些路径的最大长度是图的直径.

具有N个节点的网络的直径D被定义为网络中任意两个节点之间的最大最短路径

具有N个节点的网络的直径D被定义为任意两个节点D¼max(minp [pij length(p))之间的最短路径的最长路径p.在该等式中,pij是节点i和j之间的路径的长度,并且长度(p)是返回路径长度p的过程.例如,4 4网格D = 6的直径.

生成大型(~300k顶点)随机平面图的最有效方法是什么("随机"在这里意味着均匀分布)？

我有一个未加权的连接图.我想找到一个连接的子图,它肯定包含一组特定的节点,并且尽可能少的附加内容.怎么可以实现呢？

为了以防万一,我将使用更精确的语言重述问题.设G(V,E)为未加权,无向连通图.设N是V的某个子集.找到G(V,E)的最小连通子G'(V',E')的最佳方法是什么,N是V'的子集？

近似没问题.

首先看看这个问题.

这些库都不支持Multigraphs(或Pseudographs).我的意思是我无法生成这样的图形:

为此目的,有没有任何jQuery插件(或javascript库)？

我以为我可以使用WolframAlpha的API并使用它的图像,如下所示:

但它有很多问题:

1-我无法移动节点或以交互方式添加删除边缘.

2-每月只有2000个API调用.不够.

3-我无法生成大图或中间图.

4-真的很难看!

如果你知道一些javascript库以便绘制Multigraphs,或者无论如何产生这样的图形,请帮助我.(像Dracula Graph Library,但能够绘制Multigraphs).

顺便说一句,我不想​​再使用Adobe Flash而不是javascript.(任何其他解决方案对我来说都是可以接受的)

提前致谢.

我正在使用networkx(python中的图形库),我发现文档说PageRank算法在评分时会考虑边缘权重,但我想知道更大边缘权重是更好还是更低权重更好？

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

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

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

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

愿有人向我解释一下吗？

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

我不需要代码,只需要解释.我的教科书说

级别顺序:级别i的每个节点在级别i + 1的任何节点之前被处理

我对广度优先搜索的理解是你从左边开始首先探索离根最近的节点？这有什么不同？这是一个方形和矩形的情况吗？

从这里提取我们得到了一个最小的迭代dfs例程,我把它称为最小,因为你很难进一步简化代码:

def iterative_dfs(graph, start, path=[]):
    q = [start]
    while q:
        v = q.pop(0)
        if v not in path:
            path = path + [v]
            q = graph[v] + q

    return path

graph = {
    'a': ['b', 'c'],
    'b': ['d'],
    'c': ['d'],
    'd': ['e'],
    'e': []
}
print(iterative_dfs(graph, 'a'))

这是我的问题,您如何将此例程转换为拓扑排序方法,其中例程也变为"最小"？我看过这个视频,这个想法非常聪明,所以我想知道是否可以在上面的代码中应用相同的技巧,所以topological_sort的最终结果也变得"最小".

不要求拓扑排序的版本,这不是对上述例程的微小修改,我已经看过很少.问题不是"如何在python中实现拓扑排序",而是找到上述代码的最小可能调整集成为topological_sort.

附加评论

在原文中,作者说:

不久之前,我读了Guido van Rossen的图表实现,看似简单.现在,我坚持使用复杂性最低的纯python最小系统.我们的想法是能够探索算法.稍后,您可以优化和优化代码,但您可能希望以编译语言执行此操作.

这个问题的目标不是优化iterative_dfs,而是提出一个从它派生的topology_sort的最小版本(只是为了更多地了解图论算法).其实,我想一个更一般的问题可以像给一组最小的算法,{ iterative_dfs,recursive_dfs,iterative_bfs,recursive_dfs},这将是他们的topological_sort推导？虽然这会使问题变得更长/更复杂,但是从iterative_dfs中找出topology_sort就足够了.

我正在尝试找到一个简单的Java API来创建图形关系.它应该有一些功能,例如addEdge(),addNode(),isConnected(node1, node2),findPaths(node1, node2),等我不需要UI,只是逻辑.

我发现了一堆学术项目,但似乎都没有" The Definitive Graph API ".

有谁知道这样的API？