问题标签 [graph-traversal]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
graph - 有效地找到有向图中两个节点之间的某个路径上的所有节点
我目前正在尝试找出一种有效的方法来查找有向图中两个节点(例如和)之间的某个路径上的所有节点。X
Y
我的第一个想法是从 X 运行 BFS,从 Y 运行 BFS,并获取访问节点的交集。请注意,我不需要枚举 X 和 Y 之间的所有路径,只需找到位于从 X 到 Y 的路径上的所有节点。
我的问题是,有没有更优化的方法来做到这一点?
algorithm - 无起点的图搜索算法
我有一个场景的边缘图,想提取最能区分天空和地形的边缘。这似乎被很好地描述为一个图遍历问题。但是,流行的搜索算法(例如 A*)依赖于使用起点和终点(分别不同于第一列和最后一列)。是否有不需要这些参数的图形搜索算法?我还想最大化提取边缘的一些全局特征,例如平滑度。注意:速度是一个重要问题,这需要实时完成。
mysql - 高效遍历关系数据库中存储为表的图
我有一个表,它表示在边缘列表表示中没有循环依赖关系的图形数据结构,如下所示:
是否可以进行 SQL 查询,以便对于特定的 vertex v
,直接和间接地检索V
由所有连接顶点组成的顶点集?
例如retrieve_all_connected_vertices(3)
将返回 set (4, 5, 7)
。
我正在研究的方法是那些使用 MySQL 支持的纯 SQL 语句(存储过程等没有选择),或者与某种伪编程语言结合使用的方法。我不是在寻找特定于语言的实现,尽管我将使用 Scala 来实现这个特定目的。
我知道我们基本上可以递归地跟踪链接,直到它到达最后一个顶点,但是,如果可以使用某种优化来减少内存使用或算法复杂性,我会很高兴。
scala - Play's Hot Reloading and Neo4j Embedded takes too long
I am using Neo4j embedded database on a Play/Scala app. I leaned towards the embedded version because I want to use the Neo4j's Traversal Framework so I can easily create JSON trees using a breadth-first traversal. The problem with embedding the database is that when my Play application hot-reloads, it restarts the application, whereby my app shuts down the server (otherwise I get a db file lock error). This is causing 20s browser reloads between edits. This is especially annoying when editing Play's Twirl html files.
Am I screwed? Should I hide the calls to the embedded db behind a service? Is it worth it to do this just for developement? AFAIK, Neo4j's RESTful service doesn't allow breadth-first traversals. I'm open to suggestions. Thanks.
algorithm - 交通灯图
假设您有一个标准图,每个节点和每条边都有附加值。您希望在最短的时间内从图表上的一个节点转到另一个节点。到目前为止,您遍历此图所花费的时间将被称为 T。如果边的值为 V,则遍历该边会将 V 添加到您花费的时间 (T += V)。如果一个节点的值为 N,遍历该节点将迫使您等待,直到您花费的时间可以被 N 整除 (T += (N - T % N) % N)。
你可以把它想象成街道和红绿灯。在街道上行驶需要一定的时间才能到达另一端。开车穿过红绿灯需要等待它变绿的时间。
例如,假设您有这个图表:
乍一看,顶部路径看起来更快,因为它具有更短的边缘和更短的延迟。然而,事实证明底部路线更快。让我们先计算底部:
然后是顶部:
如您所见,底部要短得多。在这样的小规模下,计算起来更容易,但在城市规模下,您需要使用某种遍历算法。有谁知道除了蛮力之外是否有任何解决方案?
c# - 图表 - 找不到到节点的最小路线
我想找到到节点成本最低的路线。它为我找到了几条路线,但没有最低成本的路线。
我的类来存储有关节点的信息:
在元组中,我有 int, int - 第一个 int 是结束节点,第二个 int 是到该节点的路由成本
遍历图的类:
在我的示例中,我想找到到节点 6 的成本最低的路线
neo4j - 使用 Neo4J 求解加权网络流
我有一个二分图(男孩和女孩的笔记),其中节点与加权边相连(女孩-男孩对的兼容性如何),每个节点的容量为 5(每个男孩/女孩可以匹配 5 个相反的人性别)。我需要找到最佳匹配以最大化权重。
这可以表述为加权网络流——每个男人是 5 个单位的源,每个女孩是 5 个单位的汇,每个可能的弧有 1 个单位的容量。该问题可以使用线性规划或图遍历算法(例如 Ford-Fulkerson)来解决。
我目前正在研究使用 Neo4j 的可能解决方案 - 有人知道如何去做吗?(或者我应该只使用线性编程解决方案......)
prolog - 确定图形是否在序言中连接
我需要创建一个谓词isConnected/1
,将图形作为参数并确定对之间是否存在无向路径。
假设我有一个边列表(G
图在哪里):
因此,由于 3 和 4 之间没有边,这应该会失败。
我将如何解决这个问题?我是否必须遍历每个边缘并将边缘记录在列表中?还是有更好的方法来做到这一点?
algorithm - 如何从遍历两个不相交的等数组顶点中找到最后一个连接顶点的egde
给定两个不相交的等数(大小n
)集合(称为0
and 1
),其值从1
to2n
我必须找到由特定遍历形成的最后一条边(顶点对)。
遍历算法:
- 从值开始
1
(这个值在哪个集合中并不重要) - 将它与来自相反集合的第一个自由值连接(首先相对于实际值,所以如果当前值等于
3
,那么我将检查4
,5
,6
,7
, ...,2n - 1
,2n
,1
,2
) - 重复第二步
例子:
我能够以2 * (1 + 2 ... + n) = 0(n^2)
复杂的方式解决这个问题。但我相信有更好的解决方案。
python - 如何在自定义 PyYAML 构造函数中处理递归?
PyYAML 可以处理常规 python 对象中的循环图。例如:
片段#1。
这段代码成功了,所以很明显在加载序列化对象时有一些机制可以防止无限递归。当我编写自己的 YAML 构造函数时,如何利用它?
例如,sayNode
是一个具有瞬态字段foo
和的类,以及非瞬态bar
字段child
。只child
应将其放入 yaml 文档中。我希望这样做:
片段#2。
但它失败了:
我明白为什么了。我的构造函数不是为递归而构建的。它需要在完成构造父对象之前返回子对象,并且当子对象和父对象是同一个对象时会失败。
但显然 PyYAML 具有解决此问题的图遍历,因为 Snippet #1 有效。也许有一个传递来构造所有对象,第二个传递来填充它们的字段。我的问题是,我的自定义构造函数如何与这些机制联系起来?
这个问题的答案将是理想的。但是,如果答案是我不能使用自定义构造函数来做到这一点,并且有一个不太理想的替代方案(例如将YAMLObject
类混合到我的Node
类中),那么这个答案也会受到赞赏。