Graph Comparers

Topics: graph
Jun 22, 2009 at 4:48 AM

Are there any plans to include Graph Comparers, especially equality comparers, in QG?

For example given a Set of Graphs, we may need to check if a candidate exists in it. This can be done using a HasSet and a CustomEqualityComparer. However, having something in-built would be useful for graph mining applications. This would be on the lines on the StringEqualityComparer and StringComparer types in .Net

 

Coordinator
Jun 22, 2009 at 5:02 AM

QuickGraph does not have graph isomorphism algorithms so that feature is not really easy to implement as is. What kind of equality are you thinking about?

 

Jun 23, 2009 at 2:10 AM
Edited Jun 23, 2009 at 2:11 AM

Here is my definition

  • Two nodes are equal when they have same label
  • Two edges are equal when the Source nodes are equal and Target nodes are equal
  • Two graphs are equal, if they have the same nodes and same edges

Suppose G1 has V={1,2}, E={(1,2)} and G2 has V={1,2,3}, E={(1,2)}. Then G1 !=G2. However, G1==G1.

And here's my sample implementation.

    public class UndirectedGraphEqualityComparer : IEqualityComparer<UndirectedGraph<int, Edge<int>>>
    {
        #region IEqualityComparer<UndirectedGraph<int,Edge<int>>> Members
        public bool Equals(UndirectedGraph<int, Edge<int>> x, UndirectedGraph<int, Edge<int>> y)
        {
            if (x.EdgeCount != y.EdgeCount)
                return false;

            if (x.VertexCount != y.VertexCount)
                return false;

            foreach (var item in x.Vertices)
            {
                if (!y.Vertices.Contains(item))
                    return false;
            }

            foreach (var item in x.Edges)
            {
                if (!y.Edges.Contains(item, new EdgeEqualityComparer()))
                    return false;
            }

            return true;
        }

        public int GetHashCode(UndirectedGraph<int, Edge<int>> obj)
        {
            int edgeHashCode = obj.EdgeCount.GetHashCode() ^ obj.VertexCount.GetHashCode();

            foreach (var item in obj.Edges)
            {
                edgeHashCode ^= item.Source.GetHashCode() ^ item.Target.GetHashCode();
            }

            foreach (var item in obj.Vertices)
            {
                edgeHashCode ^= item.GetHashCode();
            }

            return edgeHashCode;
        }

        #endregion
    }

    public class EdgeEqualityComparer : IEqualityComparer<Edge<int>>
    {
        #region IEqualityComparer<Edge<int>> Members

        public bool Equals(Edge<int> x, Edge<int> y)
        {
            return x.Target.Equals(y.Target) && x.Source.Equals(y.Source);
        }

        public int GetHashCode(Edge<int> obj)
        {
            return obj.Target.GetHashCode() ^ obj.Source.GetHashCode();
        }

        #endregion
    }  

Coordinator
Jun 23, 2009 at 7:53 AM

The problem with your comparers is that you assume the edges are sorted in the same order in each graph. The problem relies on your GetHashCode() implementation.

ps: don't write "y.Edges.Contains", this is very inefficient. This is a really Enumerable.Contains(y.Edges), so each time you walk the entire edge list. Use 'y.ContainsEdge' instead which should be more efficent.