问题标签 [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.

0 投票
1 回答
596 浏览

scala - GraphX 内部是如何遍历 Graph 的?

我想知道GraphX对Graph的内部遍历。RDDS是基于顶点和边的遍历还是顺序遍历?例如,给定一个图的顶点,我只想获取它的邻居而不是所有顶点的邻居?在这种情况下 GraphX 将如何遍历图形。

感谢期待。

0 投票
1 回答
211 浏览

sql - 一个查询遍历多个表的算法

我正在尝试编写一种算法,该算法将帮助我找到通过多个表来获取查询数据的最佳路径。这些表具有相互关联的重叠变量。例如,我可能有这样的查询:

'选择 T1:F1 使得 T3:F6 > 0'

表是这样设置的:

表 1(T1):F1、F2

表2(T2):F2、F3、F4

表 3(T3):F4、F5、F6

其中为 F1 到 F6 的条目分配了值。因此,表 1 有 F1,而 F2 是它的兄弟。F2也在表2中,F4也是它的兄弟。F4也在表3中,F6是它的兄弟。

遍历表的正确方法是:T1:F1 -> T1:F2 -> T2:F2 -> T2:F4 -> T3:F4 -> T3:F6

有这样做的算法吗?似乎很难简单地搜索每个表的兄弟。似乎这将是某种树搜索算法,但我不知道如何设置树。

0 投票
2 回答
3366 浏览

tree - 树边缘和前向边缘之间的区别

当我遇到这个问题时,我正在读一本书:当在图形上运行 DFS 时,如何从图中特定顶点的发现和完成时间来区分前向边和树边之间的区别?

到目前为止,我尝试的是: Fwd 之间的主要区别。树边是如果 A 和 B 之间存在树边,则 A 是 B 的直接邻居,路径长度为 1,但如果是 Fwd。边缘,那么路径长度应该大于1左右。因此,在分析可以存储在数组中的发现和完成时间时,我们可以检查它们的完成/开始时间是否相差 1。因为如果有,那么它就是树边缘,否则就是前向边缘。

但是,我无法开发一种算法,也怀疑这种方法有问题。请帮帮我。谢谢你。

0 投票
1 回答
2045 浏览

java - Titan图用例中的GremlinPipeLine java API链遍历

我有一个用例,我必须遍历从特定顶点开始的顶点链。它是一个线性链(如火车),只有一个顶点连接到前一个顶点。遍历时,我必须根据某些标准发出某些顶点,直到到达链的末端。

第二个用例是上述用例的扩展,但不是从单个顶点开始的单个链,而是有多个这样的链,同样从单个顶点开始。我必须遍历每个链并检查顶点中的特定属性值。当找到该属性匹配时,我必须发出该顶点并从第二个链开始,依此类推。

我必须使用 Gremlin java API 来实现。这似乎很简单,但我是 gremlin 的新手,并且在 gremlin java API 上也没有太多来自互联网的帮助。

0 投票
1 回答
116 浏览

java - 确定沿点和线段的每条可能的路径

所以我Objects在我的 Java 程序中创建了两个,一个Point对象(在 2d 空间中,包含两个双类变量,一个用于 x,一个用于 y),以及一个LineSegment类,两个端点作为其类变量。

稍后我还创建了一个Path类,将点数组作为其类变量,点的顺序确定路径并假设第一个点是起点,然后依次访问每个后续点,在点之间直线遍历方向。

在给定一组点的情况下,如何确定所有可能的路径、指定的起点和终点,以及这些路径中的任何一条都不能出于任何原因重新访问任何点的规则?

谢谢!

0 投票
1 回答
422 浏览

arangodb - 通过特定节点的 ArangoDB 图形遍历

以美国城市为例,说我想要穿越纽约市、芝加哥和西雅图的所有城市和道路。

这可以通过 TRAVERSAL AQL 函数(使用 filterVertices)来完成。但是,此函数仅采用 ID 而不是 GRAPH_TRAVERSAL 中的顶点示例。

GRAPH_TRAVERSAL 没有过滤器选项,所以我的问题是有没有办法使用图形操作过滤结果?

0 投票
2 回答
603 浏览

arangodb - 从 AQL 遍历返回单个顶点和边的文档

当我在 Arango 中进行遍历时,我得到一个 json 结构数组,如下所示:

有没有一种方法可以使用 AQL 将遍历中找到的所有边/顶点变成一个单一的结构,例如上面的结构?

0 投票
0 回答
13 浏览

graph - 和弦可以确定图中的两个基本电路吗

我正在研究基本电路,基本割集相关定理,然后我想到了一个问题:关于图中给定生成树的和弦是否有可能确定两个基本电路?

0 投票
3 回答
2883 浏览

algorithm - 我使用什么算法来计算组合电路上的电压?

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

*这个问题似乎是针对电子学的,但更多的是关于在一组数据上应用算法。

为简单起见,
这里有一个完整的电路,电压已经计算出来:

在此处输入图像描述

我最初只给出了电池电压和电阻:

在此处输入图像描述

我遇到的问题是并联和串联电路之间的电压计算方式不同。
在 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 号表示(并且可以通过它来查找)。

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

每个数字都可以用来推导实际的节点及其对应的数据。我需要对这组数据执行什么样的转换/算法?


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

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

0 投票
2 回答
1037 浏览

algorithm - 控制流图遍历 - BFS,但确保访问前辈

我有一种情况,必须在访问节点之前访问节点的前任。所以,这里是代码:

上述算法适用于没有循环的线性控制流图(阅读:循环)正常的 BFS 遍历并不能确保在节点本身之前访问节点的前任。

示例 CFG: 控制流图。 根:0

正常的 BFS 遍历将是: 0, 1 , 2 , 3 , 12, 4, 5, 9, 10, 11, 8 , 6, 7

但是,我希望顺序为 0、1、2、3、4、5、6、7、8、9、10、11、12,这可以通过我的代码中显示的小修改来实现开始。

但是,当涉及到循环时,此修改将导致无休止地跳过块。

可能失败的示例 CFG: 带循环的控制流图

在这种情况下,我的代码将无休止地推迟对节点 1、2、3 的访问

因此,我一直在寻找一种遍历方式,以确保在节点本身之前访问节点的前任节点(带或不带循环)的 CFG 节点的遍历。

我正在考虑识别后端,即检查节点 N 是否是其前任 P 的支配者,然后 P-> N 是后端并且不需要将 P 视为节点 N 的前身。但这似乎不是作为节点 N 工作并不总是必须支配节点 P。