问题标签 [subgraph]

我目前正在使用Graph，但是它缺少一种方法来创建由给定顶点列表引起的原始图的子图。

我写了一个存根，它使用 Graph 的访问器，但是

这是我的代码：

笔记：

• 该$Graph->new行为未记录在案，但是由于 Graph 的源显示它会复制属性，但不会复制顶点/边。

• CPAN 上已有功能请求：https ://rt.cpan.org/Ticket/Display.html?id=65497

那么，是否有其他模块（可能是 XS），或者我应该 patch Graph，还是每个人自己编写一个图形类，我也应该这样做？

我有一个有向循环图，边缘处有值，但节点处没有值。

该图有一个开始节点和一个结束节点，我想保留通过图的路径集，但我不关心路径上的节点，只关心边缘值。下面的例子。

是否有任何算法可以生成保留该属性的较小图形？

该图可能有数十个数千个节点，但不是数百万个。每个节点的边数比节点数少。

保守的启发式方法是受欢迎的。

举个例子，哪里O是一个节点，一个数字是相邻边的值：

从头到尾有两条边值为 [1,2,3,4] 的路径，所以一条是多余的，我很乐意将上述内容减少到

该图可以是循环的，所以在

一个更简单的图将消除第二个 1 转换，只留下自边缘：

我有一个无向且未加权（或所有边都加权为 1）的非循环图（G=VxE）。该图的一些节点被选为 sV（sV 是 V 的子集）。问题是，我想找到覆盖所有选定节点的子图。自然可以覆盖一些未选中的节点。但是不在所需子图上的节点受到限制。这些受限节点不应出现在解决方案子图中，除非它们仅位于两个选定节点之间的一条路径上。一个例子：

A、B、C、D 是节点，+ 表示包含边。对于此图，B 和 D 是选定的节点。我想要的这个例子的解决方案如下：子图由节点 B、C、D 和边 (B,C)、(C,D) * 组成。请注意，A 未按预期出现在子图中。什么样的方法可以帮助我找到这种类型的子图？感谢您的想法。

*(X,Y) 表示节点 X 和 Y 之间的边。

我有这个 Graphviz 图：

产生这个输出：

我本来希望 A 和 D 之间的边缘长度最小化，以便节点排列为：

而不是

如果我删除子图定义，这将按预期工作。

为什么在引入子图时 Graphviz 将 ABC 放在底部？

我将开始一个关于自动机和图论的科学项目，我正在寻找一个支持以下功能的图形库：

• 有向/无向图
• 图同构测试（即图 g1 与 g2 同构吗？）
• 子图同构测试（即图 g1 是否与 g2 的子图同构？）
• 图表搜索、访问等
• 可能，非常快，因为我需要进行一些认真的计算

我知道Boost Graph Library，但据我从其文档中了解，它缺乏子图测试。

所以，我的问题是：请问哪个是最好的 c++ 图形库？他们不必为我需要的每个功能提供支持，我知道肯定有可能没有现有的库完全适合我的需求。

这是图表的消费税。

给定一个有 n 个顶点和 m 个边的无向图 G，以及一个整数 k，给出一个 O(m + n) 算法，该算法找到 G 的最大诱导子图 H，使得 H 中的每个顶点的度数≥ k，或证明没有存在这样的图表。图 G = (V, E) 的诱导子图 F = (U, R) 是 G 的顶点 V 和 G 的所有边 R 的子集，使得每条边的两个顶点都在 U 中。

我最初的想法是这样的：

首先，这个 excise 实际上要求我们拥有所有度数大于或等于 k ​​的顶点 S，然后我们删除 S 中没有任何边与其他顶点相连的顶点。则精化后的 S 为 H，其中所有顶点的度数 >= k，并且它们之间的边为 R。

另外，它要求 O(m+n)，所以我想我需要一个 BFS 或 DFS。然后我就卡住了。

在 BFS 中，我可以知道一个顶点的度数。但是一旦我得到 v （一个顶点）的度数，我不知道除了它的父顶点之外的其他连接顶点。但是如果父母没有度数> = k，我不能消除v，因为它可能仍然与其他人有联系。

有什么提示吗？

编辑：

根据@Michael J. Barber 的回答，我实现了它并在此处更新代码：

任何人都可以看看代码的关键方法public Graph kCore(Graph g, int k)吗？我做对了吗？是 O(m+n) 吗？

}

我需要一种算法来查找大图的 k 大小子图。你的建议是什么？

注意：我的图表是无向的。

提前致谢。

我想用以下代码对一些节点进行分组

但 dot 不关心子图：

我想知道是否可以使用 python 和可能的 networkx 创建一个图形，覆盖具有不同颜色的子图？这些子图是节点集群。可以在以下位置找到此类图表的示例：

http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200904-10_PLoSCompBio-HumanPhenotypes/200904-10_PLoSCompBio-Fig2sm.png

我有显示两个子图的代码：

此代码显示两个子图，如下所示：

但我想要这样：

我希望有人能帮助我修复“rankdir”以完成它。