问题标签 [subgraph]

我想获得一些给定节点集的第一跳邻居节点。获取所有邻居节点后，我想获取这些邻居节点之间存在的所有关系。我无法为此编写密码查询。

我有这张图：

有没有办法根据它们所属的子图返回两个顶点列表？

我想得到这个输出：

谢谢

如何构建一个 Neo4J 查询：

1) 将返回任意深度子图中的所有节点，其中节点由给定的一组关系连接？

例如在类似 Cypher 的语法中：

如何构建一个 Neo4J 查询：

1）将返回任何一对节点通过一定数量的不同关系连接的所有节点？例如，由 2、3 或 5 个不同关系连接的节点？因此，而不是返回具有未知数量关系的连接节点的查询：

在一般情况下，如何查询任何一对节点通过 n > K、n = L 或 n < M 关系连接的子图？

我已将问题简化为以下简单示例：

产生

在将 0、1 和 2 保持在同一等级的同时（原始示例是在更大图的上下文中），我需要 A 和 B 边是可辨别的。即边缘清晰匹配标签和标签可读。

我想象的一种解决方案是在由指定的边缘连接上使用端口

然而这会产生

其他想法？我正在生成具有相同问题的更大图表，因此最佳解决方案不是完全临时手动放置边/标签。

编辑：更大的生成图的一个（仍然简化的）示例如下。

这会产生：

在上面的简单示例中，它表现出相同的边缘/标签重叠问题。

其他注意事项：

• 当同一秩子图中的双向连接的节点对中间有一个节点时，就会出现此问题。这可能是出现错误的条件的子集。
• 无向图也存在这个问题。

我在networkx中有一个有向图G，我想得到它的最小生成树。我愿意：

这是无方向的，我想恢复方向，但我不知道该怎么做。我试过：

最后一行看起来很pythonic，但这不是networkx的工作方式，显然......有谁知道怎么做？

换句话说：在给定（无向）边的情况下，如何获得有向树的子图？

我需要使用 igraph 从图 (g) 中获取种子节点（节点的输入列表；file.txt）及其第一个交互器（邻居）的子图。不幸的是，我最终在子图中只有一个节点，而不是所有其余的节点和连接它们的边（顶点）。

对于获取整个子网（包括节点和顶点）有什么建议吗？或者是否有任何其他功能可用于创建子图？

数据库.ncol：

它是一个简单的文本文件，每行一个边。一条边由两个由制表符分隔的符号顶点名称定义：

文件.txt

我想从 Neo4j 图数据库中提取子图。输入将是两个节点。我们需要从两个节点中找到所有单跳邻居并形成节点的联合（我们称之为闭包）。现在我们必须得到这个闭包中的所有关系（节点的联合，包括输入节点）。如何在 neo4j 中使用 java“有效地”解决这个问题。请建议。

The problem: Given a Q-regular undirected graph, I'm looking for an algorithm to identify an N-regular undirected subgraph through edge deletion. N < Q (obviously), and it's important that some degree of randomness can be implemented in the algorithm, since I need to sample the space of N-regular subgraphs.

What I've tried: So far, my best method has been finding a Hamiltonian cycle, and deleting every other edge on the cycle. This nicely creates a (Q-1)-regular subgraph and can in principle be repeated until the desired degree of regularity has been reached, or I inadvertently create a graph with no Hamiltonian cycle. However, this approach is slow (this is my main issue) and it's a bit problematic that it relies on the otherwise completely unnecessary restriction of a Hamiltonian cycle.

My Question: Can anyone suggest an alternative to the Hamiltonian cycle approach, or perhaps simply tell me that the problem is inherently hard and that a faster solution than Hamiltonian cycle detection is unlikely? I realize that I'm flirting with some graph theory concepts here, but I'm afraid that I don't have the expertise to frame it more formally.

Thank you for your time :)

EDIT: I forgot to mention that the number of vertices (= L) in the original network is even. I have made this restriction to ensure that a regular graph can be created, since this is impossible if both L and Q are odd, and I wish to have as few restrictions on Q as possible. Second, I do indeed wish to retain all vertices (hence I only mentioned edge deletion).

我想显示一个a指向 node 的 node b。b在子图中。以下 dot graphviz 代码应该可以工作。

唉，虽然节点a是在任何子图之外声明的，但它在内部呈现mysubgraph（在 Ubuntu 14.04 上的 graphviz 2.36.0 上观察到）：

我已经尝试过诸如预先声明b之类的变体。没有成功。

一种解决方法是a在另一个集群子图中声明。

这可以防止a出现在里面mysubgraph，但另一个子图并不是一个真正的选择。

a真的应该在任何子图之外。

问题

• 它应该是这样的吗？
• 是否有保留预期外观的解决方法？