标签: isomorphism

简短问题:同构函数在编程中的重要性是什么(即在函数式编程中)？

很长的问题:我试图根据我不时听到的一些术语,在类别理论中绘制函数式编程和概念之间的一些类比.从本质上讲,我正在尝试将该术语"解包"成具体的东西然后我可以扩展.然后,我将能够使用该术语,理解我正在谈论的那些 - 我正在谈论什么.这总是很好.

我一直听到的这些术语之一是同构,我收集的是关于函数或函数组合之间等价的推理.我想知道是否有人可以提供一些常见模式的一些见解,其中同构的属性派上用场(在函数式编程中),以及获得的任何副产品,例如从同构函数推理的编译器优化.

两个二叉树是同构的意味着什么？我一直在网上看,我似乎无法找到明确的解释.

据我所知,如果它们具有相同的形状,则两棵树是同构的.所以我猜两个相同的树,它们可以在节点中包含不同的值.

我有一个15M(百万)DAG(有向无环图 - 实际上是指向超立方体)的集合,我想从中删除同构.这个的常见算法是什么？每个图都相当小,一个维数为N的混合立方体,其中N为3到6(现在),得到64个节点的图,每个节点为N = 6的情况.

使用networkx和python,我实现了它,这适用于300k(千)的小集合就好(几天后运行).

def isIsomorphicDuplicate(hcL, hc):
    """checks if hc is an isomorphism of any of the hc's in hcL
    Returns True if hcL contains an isomorphism of hc
    Returns False if it is not found"""
    #for each cube in hcL, check if hc could be isomorphic
    #if it could be isomorphic, then check if it is
    #if it is isomorphic, then return True
    #if all comparisons have been made already, then it is not an isomorphism and …

给出两个简单的图:

library(igraph)

g <- graph.empty()
g <- g + vertices(1,2,3)
g <- g + path(1,2,3)


g1 <- g
V(g1)$color = c(1,2,2)
g2 <- g
V(g2)$color = c(2,1,1)

看起来像:

par(mfrow=c(1,2))
palette(rainbow(3))
plot(g1)
plot(g2)

他们为什么不同构？

graph.isomorphic.vf2(g1,g2)$iso

假

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

我在Java中编写代码,使用无序的根树,其中每个节点可以有任意数量的子节点.给定树T和子树S,我希望能够找到T中与S匹配的所有子树(即T中与S同构的所有子树).

如果S的节点可以映射到T的节点,使得S的边缘映射到T中的边缘,则T的子树与S同构.

一个先前的问题已经被问如何找到如果树包含另一个子树,但是我希望能够找到所有 T中的子树匹配的S.此外,我希望能够从每个节点在T映象在每场比赛S中的对应节点

也就是说,当找到匹配时,它应该不仅仅作为指向T中节点的指针返回,其中树的根与S匹配,但匹配应该返回为类似于节点指针对的列表[ (T1,S1),(T2,S2),...(Tn,Sn)]使得T1是指向T中的节点的指针,该节点映射到子树中的节点S1,依此类推.

或者,可以返回简单的值对列表,因为树T中的每个节点和子树S具有与之关联的唯一整数标识符.

例如:

鉴于树T如下:

    a
   / \
  b   c
 / \  
d   e

和子树S为:

    x
   / \
  y   z

应返回以下匹配列表:

[(a,x),(b,y),(c,z)] [(b,x),(d,y),(e,z)]

唯一匹配由T中的节点集确定,而不是 T和S中节点之间的映射.

所以以下匹配:

[(a,x),(b,z),(c,y)]

被认为是重复的

[(a,x),(b,y),(c,z)]

因为它们具有来自T(a,b,c)的相同节点集,所以只应返回其中一个匹配.

另一个例子,给定树T:

    a
   /|\
  b c d

和子树S:

  x
 / \  
y   z

应返回以下匹配列表:

[(a,x),(b,y),(c,z)] [(a,x),(b,y),(d,z)] [(a,x),(c,y) ,(d,Z)〕

任何人都可以提供任何示例代码如何做到这一点？

编辑(与Chris Kannon的评论有关):

我想你想要有人为你编码答案？你到底有多远？你写了什么代码？ - Chris Kannon 1小时前

我有以下代码,在运行时,构建一个指向树中节点的指针列表(matchesList),其中子树根与给定的子树相匹配.但是,可能存在多个以同一节点为根的子树,并且当前每个节点最多只会添加一次到matchesList,而不管有多少匹配在那里.

另外,我无法弄清楚如何在子树中的节点和原始树中找到的匹配节点之间建立上述映射.

package Example;

import java.util.LinkedList;
import java.util.Vector;

public …

有人能用简单的单词解释VF2算法的图形同构的步骤吗？我正在学习这个算法,但没有一个有效的例子就很苛刻.有人能引导我正确的方向吗？谢谢.

我正在尝试找到工具/算法来搜索与面向图中指定模式相对应的部分,例如:

A-> B-> C或或A- - B-> C.

请建议我搜索的方向.

我的意思是模式匹配.我需要找到匹配指定模式的所有节点和边的组

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

• 有向/无向图
• 图同构测试(即图g1同构wrt g2？)
• 子图同构测试(即图形g1与g2的子图同构？)
• 图搜索,访问等
• 可能,非常快,因为我需要做一些严肃的计算

我知道Boost Graph Library,但据我从文档中理解,它缺少子图测试.

所以,我的问题是:哪个是最好的c ++图形库,好吗？他们不需要为我需要的每个功能提供支持,我知道现有的库当然没有完全满足我的需求.

受到ADT之间多态函数问题的启发,我试图在多个(不仅仅是2个)类型之间创建同构,因此每次我需要一个同构但不是同一类型时,我可以将一些代码洒在我的代码上convert.

假设我有3个ADT:

data AB = A | B deriving (Show)
data CD = C | D deriving (Show)
data EF = E | F deriving (Show)

使用lens我可以实现AB和CD,CD和EF之间的2个同构:

{-# LANGUAGE MultiParamTypeClasses #-}
class Isomorphic a b where
  convert :: Iso' a b

instance Isomorphic AB CD where
  convert = iso ab2cd cd2ab
    where ab2cd A = C
          ab2cd B = D
          cd2ab C = A
          cd2ab D = B

instance Isomorphic AB EF where
  convert …

在Thinking with Types一书中，6.4 Continuation Monad讲到了类型a和forall r. (a -> r) -> r是同构的，可以通过以下函数来见证：

cont :: a -> (forall r. (a -> r) -> r)
cont x = \f -> f x

unCont :: (forall r. (a -> r) -> r) -> a
unCont f = f id

在这本书中，它告诉我们任何具有相同基数的两种类型总是彼此同构的。所以我试图找出类型a和的基数forall r. (a -> r) -> r。

假设类型的基数a是|a|。那么对于类型forall r. (a -> r) -> r，如何计算其基数等于|a| …