问题标签 [subgraph]

Given a graph G=(V, E), a subset S that belongs to V, and the subset S' containing every vertex of G not belonging to S, I want to count the total number of edges between the nodes of S and S'.

An algorithm that could solve this problem with better complexity than O(n^2).

我有一个 boost adjacency_list，这是我的主图。在这个图中，我使用 create_subgraph 函数添加了一些子图。

我的问题是，如何在不存储 Graph 对象的情况下获取刚刚创建的子图列表？

例如：

有没有这样的函数可以让我得到图 g 的所有子图？

我是学习图论的大一新生。我现在正在学习（子）图同构。有两个重要的算法：Ullmann 算法和vf2。

我读过 Ullmann`s: An algorithm for Subgraph Isomorphism 的论文。我也google了一下，google给了我很多应用，但是我看不懂算法的过程。

你能给我一个简单的解释吗？

基本上我想做的是可视化迭代之间的依赖关系。为了实现这一点，我需要在行和列中绘制节点，以便它们形成一个大矩形。我通过使用 Agraph_t *agsubg(Agraph_t*, char*, int) 函数，设置等级属性并制作不可见的边缘，设法在 GraphViz 的 C 代码中做到这一点，但我需要在 C# 中做到这一点。所以我的问题是如何使用 QuickGraph 制作子图/集群。或者也许有一种方法可以在没有子图的情况下完成这项工作。

我创建了一个轻量级图形库，它有 3 个对象（顶点、边缘、图形）和 1 个函数（topo_sort），如下所示：

如果我有一个扁平的 DAG，这可以正常工作。但我想要实现的是在我的主图中添加子图（或嵌套图），正如你在我绘制的插图中看到的那样：

这仍然是一个 DAG，所以如果我对此运行我的函数，正常 topo_sort输出将是这样的：

然而，我的首选输出是当子图所依赖的所有顶点在处理子图的顶点之前“处理”时 - 所以它应该是这样的：

但我找不到任何资源：

• 如何将图中的顶点“标记”或“存储”为子图的一部分？
• 如何根据顶点的子图依赖关系对顶点进行排序（如上面的示例）？
• 如何将子图作为独立图获取或处理？

我希望我能足够详细地解释我的问题——尽管如果有什么遗漏，请告诉我，我会用遗漏的部分来扩展我的问题。

提前致谢！

编辑：

我发现了这个（Boost Graph Library，BGL），它看起来解决了我遇到的一个非常相似（或完全相同？）的问题，虽然我不熟悉 C++，所以我不明白它是怎么回事工作以及它到底在做什么——但我把它放在这里，也许有人会发现回答我的问题很有帮助..

编辑2：

我也接受伪代码，而不仅仅是 python！当然，如果现有的 python 库知道这一点，我对此很感兴趣，但是，我不想使用如此庞大的库graph-tools，例如——这就是我创建自己的库的原因，所以我更喜欢实现而不是库。

我通过我的 perl 脚本创建点文件。这是包含相同节点的子图。例如：

我知道那些子图使用相同的命名空间，所以我的结果输出是一团糟。

在每个子图中，我可以让它们独一无二，likebb和bb_1below，

但是很难使所有子图中的所有节点都是唯一的。

是否有一些方法可以使每个子图“严格”或使用不同的命名空间？

我在这里显示了一个图表。仅针对节点 B_0、B_1 属于类型 B、C_0、C_1 的节点的节点。C_2、C_3 属于 C 类节点，以此类推。现在，我想找到多个子图，它们可以满足本示例定义的标准 -

标准 -

1. 子图包含1个A类型节点，1个B类型节点，1个C类型节点，1个D类型节点。
2. 子图有一条从A类型节点到B类型节点的边，一条边连接B类型和C类型，还有一个节点连接C类型和D类型。
3. 子图包含一条从类型 A 出子图到类型 B 节点的边，一条从类型 B 到类型 C 节点外的边，一条从类型 D 到类型 E 外的边。

现在这个描述应该给出结果 -

1. 子图 :: A_0, B_0, C_1, D_1
2. 子图 :: A_0, B_0, C_0, D_0
3. 子图 :: A_0, B_1, C_2, D_2
4. 子图 :: A_0, B_1, C_3, D_3

我想知道，是否有任何算法可以找到这样的子图？我试图通过进行所有可能的组合来找出一种算法。但是，这将是子图中节点数量的指数。因此，我想知道是否存在一种有效的计算方法。或者图论中是否存在类似性质的问题？

我有一个无向图G。由于G是顶点和边的集合，我想把它当作一个“数据库”。

现在我有一个查询图H，它保证是G. 我怎样才能弄清楚H对应于哪个部分G？

这个问题与这里的现有问题不同，因为基本上我知道肯定H是G.

有没有办法从neo4j图形数据库中提取子图，基于我想存在于我的子图中的节点，所以子图将包括声明的节点及其相互关系？

我正在使用 neo4j java 嵌入数据库。

我搜索但没有找到基于节点的子图提取，所以我将非常感谢您的大力帮助。

我对 VF2 算法实现有疑问。在许多情况下，一切似乎都运行良好，但是有一个问题我无法解决。

该算法不适用于下面的示例。在此示例中，我们正在比较两个相同的图表（见下图）。起始顶点为 0。在 s0 内计算的集合 P 存储所有顶点对的幂集。

下面是关于 VF2 的出版物中包含的伪代码，我的实现正是基于该伪代码。

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B51AD0DAEDF60D6C8AB589A39A570257?doi=10.1.1.101.5342&rep=rep1&type=pdf

http://www.icst.pku.edu.cn/intro/leizou/teaching/2012-autumn/papers/part2/VF2%20A%20%28sub%29Graph%20Isomorphism%20Algorithm%20For%20Matching%20Large%20Graphs。 pdf

/*右边的注释描述了我理解代码的方式：

我不确定创建 P() 集是否有效，如下所述。对的幂集按字典顺序依次通过对的第一个值和第二个值进行迭代。

当算法进入 s4 时，从函数返回时，它会丢失有关良好顶点匹配的信息。它导致搜索子图同构 ({(0,0),(1,1),(2,2),(5,3),(6,4)}) - 即使图是同构的。

我在这里做错了什么？