问题标签 [isomorphism]

I'm doing the subgraph isomorphism using igraph library in R.

I have two graphs p1 and p2:

I got the result when applying graph.subisomorphic:

I can understand this result which contains two mappings.

However, I want to get all the subisomorphisms, so I applied another function called graph.get.subisomorphism. According to R documentation, the result is a list of named numeric vectors:

"graph.get.subisomorphisms.vf2 returns a list of numeric vectors, each numeric vector is an isomorphic mapping from graph2 to a subgraph of graph1."

Could anyone help me explain the result? Why there is a < NA > as the name of the numeric vector?

我希望具有大量内容的网页具有最佳性能。特别有趣的是，在移动设备上，我希望用户尽快看到首屏内容，然后让应用程序尽快启动。

我有一个在浏览器环境中但在服务器环境中isBrowser的变量。考虑以下渲染函数：truefalse

请注意，通过render()这种方式构建，服务器要渲染的标记更少，通过网络传输的数据更少，浏览器在第一次通过时要渲染的标记也更少。

这工作正常，但在控制台反应警告

React 尝试在容器中使用重用标记，但校验和无效。这通常意味着您正在使用服务器渲染，并且在服务器上生成的标记不是客户端所期望的。React 注入了新的标记来补偿哪些工作，但是您已经失去了服务器渲染的许多好处。相反，要弄清楚为什么生成的标记在客户端或服务器上是不同的。

在服务器上，React 使用作为属性嵌入到顶级元素（例如 ex data-react-checksum="941190765"）中的校验和来呈现标记。然后在客户端，react 在第一次渲染后计算校验和，如果它与服务器的校验和不同，它会完全丢弃服务器生成的标记并用客户端生成的标记替换它。

作为一种解决方法，我发现在我的顶级组件的componentDidMount生命周期方法中，我可以在下一个动画帧上安排以下操作：

然后我可以像这样编写我的渲染方法并且反应没有产生任何关于校验和的警告：

这样做有什么明显的性能优势吗？无论哪种情况，首屏内容都会以同样快的速度出现，对吧？额外的复杂性是否合理？

对于用某种编程语言编写的任何程序，是否总是可以编译成任何其他语言的具有等效功能的程序？

我正在尝试制作一个从 .txt （类似于http://pastebin.com/g4cgaHJB）文件中读取图形的程序，然后创建并将它们放入向量中。（这部分工作完美）

想法：我试图迭代图，从第一条边开始（并从中创建一个图，我们称之为 testg ），并测试这个图是否频繁（我将测试 testg 和每个图之间的子图同构dataG 向量，然后我将计算有多少时间是真实的，如果有很多时间那么 2 所以 testg 是频繁的），如果 testg 是频繁的，那么我将添加另一个相邻边（并再次进行子图同构测试），如果 testg 不再频繁，我将删除最后添加的边缘（回溯）并将其更改为另一个（并再次进行子图同构测试）。如果没有更多的优势可以添加，我会说 testg 已关闭。并将其放入向量中，我们称其为 closedG。

我通过这样做开始了这个想法：

但是，它不起作用！这是错误：

给定两棵已知根的树，我们如何有效地确定这些树是否是同构的？我们只关心树的形状，而不关心节点的值。如果一棵树可以通过重命名它的节点变成另一棵树，那么这些树是同构的。该算法不需要 100% 正确，因此只要哈希冲突很少见，我们就可以使用哈希。

编辑：找到解决方案，从这篇文章中删除了不必要的混乱

我目前正处于一个新项目的规划阶段，该项目由一个店面、一个高度反应性的用户仪表板和通过店面提供的单个产品是高度交互的迷你应用程序组成。我们试图让整个平台成为一个 SPA，并在 Flux 架构上设计整个东西，并使用 React 作为前端视图。

与大多数 SPA 一样，一个问题是 SEO。我已经基于 este.js 开发堆栈构建了一个同构解决方案的原型。一个问题是我们的应用程序从一个 RESTful 服务器中消耗了几乎所有的数据，该服务器与提供 SPA 的 Web 服务器是分开的。这意味着 Web 服务器需要从 RESTful 服务器获取大量数据，以同构生成 HTML 快照。

我考虑过让我自己的一个单独的爬虫进程定期爬取整个店面，并且同构地生成页面的 HTML 快照，当 Web 服务器遇到搜索引擎爬虫时可以提供这些快照。我不确定这是否是一个好方法，因为它可能会引入额外的维护，坦率地说，它似乎有点脆弱。我可以让 Web 服务器在运行中以同构方式生成 HTML，但我担心普通用户会使服务器陷入困境，因为服务器会从 REST API 中提取大量数据......

有没有更好的方法来处理这种情况？

给定两个简单的图表：

看起来像：

为什么它们不是同构的？

错误的

最重要的是，如果这不是同构，我怎样才能检测到这种等价性igraph？

我正在尝试实现一种启发式解决方案，以从给定的一组图中识别同构图的类。目前，我正在使用其邻居的多组度数（WL 算法）标记每个节点。

对于度数规则图等情况，这显然会产生误报。我希望找到另一种廉价可实现（时间和空间受限）的启发式方法，它可以跨越 WL 算法的极端情况。本质上，我正在寻找一对易于实施的启发式方法，它们之间会产生边际误报。

除了 WL 算法，我还应该研究哪种启发式算法？

谢谢！

我证明了一些关于列表的定理，并从中提取了算法。现在我想改用堆，因为查找和连接更快。我目前为实现这一目标所做的只是对提取的列表类型使用自定义定义。我想以更正式的方式来做这件事，但理想情况下不必重做所有的证明。可以说我有一个类型

和同构

此外，我有函数 H_app 和 H_nth，这样

和

一方面，我必须用一个模拟列表递归的专用函数来替换每个列表递归。另一方面，事先我想用 and 替换and ，++因此提取的算法会更快。问题是我在某些地方使用了类似and的策略，如果我只是替换证明代码中的所有内容，这可能会失败。以后有可能“重载”这些功能会很好。nthH_appH_nthsimplcompute

这样的事情可能吗？

编辑：澄清一下，数字也出现了类似的问题：我有一些使用的旧证明nat，但是数字变得太大了。使用BinNat会更好，但是是否可以在没有太多修改的情况下使用BinNat而不是在旧的证明中使用？（特别是，用更有效的定义nat替换 ? 的低效用法）+BinNat

我正在使用 boost 库编写图挖掘代码，我想知道如何测试：

• 如果两个图使用同构相等（仅当图具有相同的结构和相同的标签时才返回真）

• 如果一个图是另一个图的子图？

这是图形文件：3test.txt

这是我制作的源代码的一些部分：

不幸的是，当我运行它时，我得到了这些错误：