How to count distinct trees in a list of trees

Question

I have a tree structure as follows:

public class TAGNode
{
    public string Val;
    public string Type = "";
    private List<TAGNode> childs;
    public IList<TAGNode> Childs
    {
        get { return childs.AsReadOnly(); }
    }

    public TAGNode AddChild(string val)
    {
        TAGNode tree = new TAGNode(val);
        tree.Parent = this;
        childs.Add(tree);
        return tree;
    }
    public override bool Equals(object obj)
    {
        var t = obj as TAGNode;
        bool eq = Val == t.Val && childs.Count == t.Childs.Count;
        if (eq)
        {
            for (int i = 0; i < childs.Count; i++)
            {
                eq &= childs[i].Equals(t.childs[i]);
            }
        }
        return eq;
    }

}

I have a list of such trees which can contain repeated trees, by repeated I mean they have the same structure with the same labels. Now I want to select distinct trees from this list. I tried

        etrees = new List<TAGNode>();
        TAGNode test1 = new TAGNode("S");
        test1.AddChild("A").AddChild("B");
        test1.AddChild("C");

        TAGNode test2 = new TAGNode("S");
        test2.AddChild("A").AddChild("B");
        test2.AddChild("C");

        TAGNode test3 = new TAGNode("S");
        test3.AddChild("A");
        test3.AddChild("B");

        etrees.Add(test1);
        etrees.Add(test2);
        etrees.Add(test3);

        var results = etrees.Distinct();

       label1.Text = results.Count() + " unique trees";

This returns the count of all the trees (3) while I expect 2 distinct trees! I think maybe I should implement a suitable Equals function for it, but as I tested it doesn't care what Equals returns!

Ivan Stoev · Accepted Answer · 2016-07-09T11:07:30.403

I think maybe I should implement a suitable Equals function for it

Correct.

but as I tested it doesn't care what Equals returns!

Because you have to implement a matching GetHashCode! It doesn't need to include all the items used inside the Equals, in your case Val could be sufficient. Remember, all you need is to return one and the same hash code for the potentially equal items. The items with different hash codes are considered non equal and never checked with Equals.

So something like this should work:

public bool Equals(TAGNode other)
{
    if ((object)this == (object)other) return true;
    if ((object)other == null) return false;
    return Val == other.Val && childs.SequenceEqual(other.childs);
}

public override bool Equals(object obj) => Equals(obj as TAGNode);

public override int GetHashCode() => Val?.GetHashCode() ?? 0;

Once you do that, you can also "mark" your TAGNode as IEquatable<TAGNode>, to let the default equality comparer directly call the Equals(TAGNode other) overload.

score 1 · Answer 2 · answered Jul 09 '16 at 08:26

1

see https://msdn.microsoft.com/en-us/library/bb348436(v=vs.100).aspx

If you want to return distinct elements from sequences of objects of some custom data type, you have to implement the IEquatable generic interface in the class. The following code example shows how to implement this interface in a custom data type and provide GetHashCode and Equals methods.

you need to impliment IEquatable for TagNode

answered Jul 09 '16 at 08:26

Nahum

6,959
12
48
69

thank you, what could be the GetHashCode for TagNode!? – Ahmad Jul 09 '16 at 08:55
I modified my question to show my implementation for Equals, don't know how to map it to GetHashCode, isn't really a better way! do I need to provide GetHashCode?!! – Ahmad Jul 09 '16 at 09:08

jdweng · Answer 3 · 2016-07-09T16:51:40.833

try following for GetHashCode. I updated the method below to make more robust. Was afraid original answer may not create unique has values.

        private int GetHashCode(TAGNode node)
        {
            string hash = node.Val;
            foreach(TAGNode child in node.childs)
            {
                hash += GetHashStr(child);
            }
            return hash.GetHashCode();       
        }
        private string GetHashStr(TAGNode node)
        {
            string hash = node.Val;
            foreach (TAGNode child in node.childs)
            {
                hash += ":" + GetHashStr(child);
            }
            return hash;
        }

How to count distinct trees in a list of trees

3 Answers3