问题标签 [isomorphism]

HashMap.containsValue()和因此的代码的时间复杂度是多少？是它O(n2)还是if条件将HashMap.containsValue()'s 的复杂性降低到O(1)?

我正在使用 Networkx 函数进行同构：

我想对一个名为“type”的边缘属性做同样的事情，但我不知道怎么做。我刚试过这个：

但它不起作用。谢谢！

编辑：这是来自文档：

boost::vf2_subgraph_iso应该在给定的大图中找到给定较小图的诱导子图。传递给它的回调将获得一个映射作为输入。

但是文档只提到了顶点映射。我知道可以通过映射每个边缘的源和目标来理解边缘映射。但我需要映射边缘的捆绑属性。

似乎这boost::get不适用于映射和边缘描述符。boost::get(f, e)产生以下错误消息。

我有一个无向的彩色（相邻节点有不同的颜色）图，我需要计算一个散列，以便如果两个图是同构的，它们具有相同的散列（图也是平面的，我不知道它是否可以有所作为）。

我的数据结构是这样的：

该id属性用于程序逻辑，因此在比较图形时不应考虑它。

我的想法是对图的节点进行排序，然后从第一个节点开始探索相邻节点以生成图的树。然后我从树中生成一个唯一的字符串（实际上我是在探索期间生成的字符串）。所以，我想做的是找到一种图的规范化。

描述

我首先按度数对节点进行排序，然后按颜色属性名称升序排列。我采用第一个节点并开始探索相邻节点，深度优先搜索以相同的方式对它们进行排序。我跟踪已经访问过的节点以避免扩展旧节点。

我的字符串是这样生成的：使用深度优先搜索，每次我到达一个新节点时，我都会将以下内容附加到图形字符串中：

• 节点颜色
• 节点度
• 访问节点列表中的索引

也许这是多余的，但我认为这些信息足以保证正确的规范化。

真正的问题是两个节点在排序过程中具有相同的度数和相同的颜色。我所做的应该保证规范化，但效率不高。取一组相似的节点（相同的度数和颜色），我为每个节点生成一个子树，并为子树生成一个关联的字符串，并在节点排序中选择最大的一个（按降序排序）作为下一个。然后我删除最后一个节点并重复操作，直到该组为空。我需要这样做，因为在选择第一个节点后，我可能已经更改了访问节点的列表，然后新的字符串可能会有所不同。

目前这种实现效率很低：

问题

因此我有两个问题：

• 我的算法真的有效吗（我的意思是，它似乎有效，但我没有任何数学证明）？
• 是否有更快的算法（复杂性更低）来计算哈希？

I'm looking for motifs of size 5 in graphs with less than 5000 nodes and less than 10000 edges. (everything uncolored)

To do this I use function provided in igraph library for R subgraph_isomorphisms using method vf2 (see example below). I use adjacency matrix to generate subgraph and edgelist to generate the graph itself.

A lot of isomorphic subgraphs that I find have extra edges. Is there any way to only find subgraphs with exact given structure? Looking for answers using igraph or any other library in R

See reproducible example below (looking at this example is way easier if you just draw graph given by this adjacency matrix on a piece of paper)

Output gives you two pairs of (1,2) and (3,4), when in fact adjacency matrix of (1,2) looks like

(0 1) (1 1)

Which is different from the one we were looking for

我是 Haskell 初学者，我想创建一个函数来确定两个列表之间是否存在同构。我认为如果它们的长度相同 > 0，答案是肯定的。

但是空集呢？空集之间可以存在同构吗？

谢谢。

使用 python 库 networkx 可以使用函数检查同构is_isomorphic(G1, G2)，其中 G1 和 G2 是两个图（https://networkx.github.io/documentation/stable/reference/algorithms/isomorphism.html）。

但是在检查存在一个之后，如何得到同构的一一对应的节点呢？

假设我们专门执行节点匹配。

所以我创建了两种整数表示：

和两个转换函数：

请注意，那PZ Z代表+1，而不是0。

现在我证明这些表示是同构的：

令我惊讶的是，伊德里斯礼貌地点点头表示同意。

所以诚然，这正是我想要的，尽管我对我现在可以证明的事实感到有点不安NN 0 3 = NN 6 9：

这似乎不对。毕竟，NN 0 3 在结构上与NN 6 9. 那么伊德里斯到底是从哪里确信他们是一样的呢？这是一种预期的行为（我可以想象它是），如果是这样，它究竟是如何工作的？

原来的问题在这里。

如何计算具有 6 个顶点和 5 条边的图具有三角形的概率？

我想做一个模拟。我将创建triangle图然后生成带有顶点和边的1,000随机图，并找到三角形的分布。n=6m=5

现在我g用一个三角形创建了一个图形，该subgraph_isomorphisms()函数返回6同构三角形。然后我使用该unique()函数来找到一个三角形。但结果是6。

问题。 如何从一组同构三角形中只返回一个三角形？

.bashrc在它们之间切换的简单技巧：

名为c-，为cd -。尝试在路径中替换，test意味着成功退出。否则尝试匡威。如果没有匹配项，则无效。[如果或出现在路径中的其他地方不正确]。srctsrctest

但是...我真的想要一些可以作为路径的一部分使用的东西——比如符号链接，所以它适用于vi/ emacs、mv、rm等ls，而不仅仅是cd. 就好像：从src树中，t链接到树中的相应目录test（和反向链接s），使用如下：

当然，实际的符号链接可以做到这一点。可以根据需要手动添加（或递归地完成所有操作） - 但看起来很乱。另一种方式是t作为脚本或函数：

但我（懒惰地）想避免``or $()，并以某种方式t动态地充当符号链接......需要解析和修改命令行？

或者，也许整个想法既危险又愚蠢，无论何时使用都会产生狂野的效果t？它在命令行中必须是上下文敏感的（即，当需要路径/文件名/参数时，并且在开头）。或者也许是一种奇怪的自动完成？

我们可以这样做吗？（我们应该这样做吗？）