标签: isomorphism

在算法设计手册中,它说

你在测试两棵树是否同构吗？ - 对于图同构的某些特殊情况,例如树和平面图,存在更快的算法.也许最重要的情况是检测树之间的同构,这是语言模式匹配和解析应用程序中出现的问题.解析树通常用于描述文本的结构; 如果底层文本具有相同的结构,则两个解析树将是同构的.

我只是希望有人请给我一个例子,说明如何使用Tree Isomorphism来解决语言模式匹配问题.即,如何将语言模式匹配映射到树同构问题？

通常,如何将字符串或文本构造为树并比较它们的身份？

谢谢

比方说,我有一个名为两个函数f :: a -> b,它的逆g :: b -> a这样f . g ? id.

现在不是g . f ? id吗？(因而暗示同构)

我试着写一个类似的例子并想出了这个:

myRead :: String -> Int
myRead = read

myShow :: Int -> String
myShow = show

在ghci:

?> myRead . myShow $ 3
3
?> myShow . myRead $ "33"
"33"

但似乎反函数并不意味着同构.所以有人能指出我在这里做错了吗？

我是学习图论的新生.我现在正在学习(子)图同构.有两个重要的算法:Ullmann算法和vf2.

我读过Ullmann的论文:Subgraph Isomorphism 的算法.我也谷歌搜索它和谷歌给了我很多应用程序,但我无法理解算法的程序.

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

有没有人实现Laszlo Babai的准多项式图同构？

http://people.cs.uchicago.edu/~laci/

我不是这方面的专家.我想知道 为什么不实施他的算法并运行它来验证它的时间复杂度？

我有一个大图，我想使用 NetworkX 中内置的 VF2 算法找到子图同构。“干草堆”图和“针”图都是有向的。举个简单的例子：

from networkx.algorithms.isomorphism import DiGraphMatcher

G1 = nx.complete_graph(20, nx.DiGraph)

G2 = nx.DiGraph()
G2.add_edge(1, 2)

list(DiGraphMatcher(G1, G2).subgraph_isomorphisms_iter())

最后一行返回一个空列表[]。

我的理解是，这应该返回图中的所有边，事实上，如果我替换GraphMatcher，DiGraphMatcher我会得到所有边的列表。

是否有问题DiGraphMatcher，或者我对应该做什么的理解有问题DiGraphMatcher？

版本：

• 蟒蛇：3.7.7
• 网络X：2.4

无向图代码示例（全部替换DiGraph为Graph，其他相同）：

from networkx.algorithms.isomorphism import GraphMatcher

G1 = nx.complete_graph(20, nx.Graph)

G2 = nx.Graph()
G2.add_edge(1, 2)

list(GraphMatcher(G1, G2).subgraph_isomorphisms_iter())

我有一个关于在Haskell中转换两种数据类型的问题.

请考虑以下两种数据类型

data Stream a = Cons a (Stream a)

data Stream2 a = ST {shead :: a, stail :: Stream2 a}

Run Code Online (Sandbox Code Playgroud)

Q2:写

sToS2 :: Stream a -> Stream2 a

s2ToS :: Stream2 a -> Stream a

Run Code Online (Sandbox Code Playgroud)

在两个流表示之间进行转换

我遇到麻烦的第一件事是Stream数据类型,我们可以看到这是一个递归数据类型,但没有基本情况,这让我想知道这是否有点无限以及如何创建流数据类型.此外,Stream2的构造函数以记录语法给出,其中一个字段也是Stream2类型.我知道有一个类似于时间的问题

data Ab = A | B
data Cd = C | D

fromAb :: Ab -> Cd
fromAb A = C
fromAb B = D

toAb :: Cd -> Ab
toAb C = A
toAb D = B

但我不确定如何将这个问题的答案应用到我特别的困惑中.