值等于和循环引用:如何解决无限递归？

Question

我有一些包含几个字段的类.我需要按值比较它们,即如果它们的字段包含相同的数据,则类的两个实例是相等的.我已经覆盖了GetHashCode它的Equals方法.

可能会发生这些类包含循环引用.

示例:我们想要建立机构(如政府,体育俱乐部等).一个机构有一个名字.A Club是具有名称和成员列表的机构.每个成员Person都有一个名字和最喜欢的机构.如果某个俱乐部的成员将该俱乐部作为他最喜欢的机构,我们有一个循环参考.

但循环引用与值相等一起导致无限递归.这是一个代码示例:

interface IInstitution { string Name { get; } }

class Club : IInstitution
{
    public string Name { get; set; }
    public HashSet<Person> Members { get; set; }

    public override int GetHashCode() { return Name.GetHashCode() + Members.Count; }

    public override bool Equals(object obj)
    {
        Club other = obj as Club;
        if (other == null)
            return false;

        return Name.Equals(other.Name) && Members.SetEquals(other.Members);
    }
}

class Person
{
    public string Name { get; set; }
    public IInstitution FavouriteInstitution { get; set; }

    public override int GetHashCode() { return Name.GetHashCode(); }

    public override bool Equals(object obj)
    {
        Person other = obj as Person;
        if (other == null)
            return false;

        return Name.Equals(other.Name)
            && FavouriteInstitution.Equals(other.FavouriteInstitution);
    }
}

class Program
{
    public static void Main()
    {
        Club c1 = new Club { Name = "myClub", Members = new HashSet<Person>() };
        Person p1 = new Person { Name = "Johnny", FavouriteInstitution = c1 }
        c1.Members.Add(p1);

        Club c2 = new Club { Name = "myClub", Members = new HashSet<Person>() };
        Person p2 = new Person { Name = "Johnny", FavouriteInstitution = c2 }
        c2.Members.Add(p2);

        bool c1_and_c2_equal = c1.Equals(c2); // StackOverflowException!
            // c1.Equals(c2) calls Members.SetEquals(other.Members)
            // Members.SetEquals(other.Members) calls p1.Equals(p2)
            // p1.Equals(p2) calls c1.Equals(c2) 
    }
}

c1_and_c2_equal应该回归true,实际上我们(人类)可以看到它们在一点点思考中是有价值的,而不会遇到无限的递归.但是,我无法真实地说出我们如何解决这个问题.但既然有可能,我希望有一种方法可以在代码中解决这个问题!

所以问题是:如何在不进行无限递归的情况下检查值的相等性？

请注意,我需要解决一般的循环引用,而不仅仅是上面的情况.自c1引用p1和p1引用以来,我将其称为2圈c1.也有其他的正圆形,例如,如果一个俱乐部A有一个成员M,其最喜欢的是俱乐部B,其成员有N她最喜欢的俱乐部A.这将是一个4圈.其他对象模型也可能允许具有奇数n的n个圆.我正在寻找一种方法来解决所有这些问题,因为我不会事先知道n可以有哪些价值.

Answer 1

对于我感兴趣的一般情况

-- 我们有类C1，...，Cn其中每个类都可以有任意数量的值（例如int，，string...）以及对任何其他类的任意数量的引用C1，...，Cn（例如通过每种类型都有Ci一个字段ICollection<Ci>）--

“两个对象相等吗A？B”的问题 ，就我在这里描述的平等而言，

似乎相当于

问题“对于两个有限、有向、连通的彩色图G和H，是否存在从G到 的同构H？” 。

这是等价的：

• 图顶点对应于objects（类实例）
• 图边对应于对objects 的引用
• 颜色对应于值和类型本身的集合（即，如果两个顶点对应的objects 具有相同的类型和相同的值，则两个顶点的颜色是相同的）

这是一个 NP 难题，所以我想我将放弃实现这个问题的计划，转而采用无循环引用的方法。