Vertices expand on creating AdjacencyGraph?

Topics: algorithm
Sep 25, 2009 at 6:24 AM
Edited Sep 25, 2009 at 6:25 AM

Hi...  I'm a QuickGraph newbie, so hopefully the question makes sense.


I have a list of custom edges that I’ve defined like this:


    public class PluginEdge : IEdge<PluginVertex>


        public PluginVertex Importer { get; set; }

        public PluginVertex Exporter { get; set; }

        public string Contract { get; set; }


        #region IEdge<PluginVertex> Members


        PluginVertex IEdge<PluginVertex>.Source


            get { return Importer; }



        PluginVertex IEdge<PluginVertex>.Target


            get { return Exporter; }






And I create an adjacency graph from a list of these (called _allEdges) like so:


            var graph = _allEdges.ToAdjacencyGraph<PluginVertex, PluginEdge>();


In my data set, it happens that all of the edges in _allEdges (there are 401) have a source and a target that are picked from a bag of 65 PluginVertex classes.  But the resulting graph has a VertexCount of 121.  So somehow the ToAdjacencyGraph() replicated vertices into it.


What I did next was just make a simple graph with int-valued vertices, and SEdge<int> edges, and populated it with the exact same data set/connectivity.  The resulting adjacency graph there was what I expected:  a VertexCount of 65, not the 121 I saw above.


Any idea what’s going on?  Is this because of use of classes and not structs?  Or do I need to implement an IComparable/IEquatable/I??? somewhere on my PluginVertex or PluginEdge to somehow prevent this replication of vertices? 


I can certainly work around the issue by going with int’s only and maintaining lookaside tables, but it seems much cleaner for me to have the graph store my actual data structures.


Another possible hint: my data really has a cycle in it.  But the AdjacencyGraph I create with PluginVertex/PluginEdge says that graph.IsDirectedAcyclicGraph is true.  With the 'int' version, this returns false, as I'd expect.  Making me believe further that there's an IComparable thing going on here, or some object equality issue.




Sep 25, 2009 at 7:06 AM

Nevermind :-).  Figured it out.  Needed to implement Object.Equals and Object.HashCode on my PluginVertex.  I hadn't expected to do that, as I had created all the instances to PluginVertex myself and they were all unique... but somehow/somewhere they are getting cloned into separate references...  don't understand, but I'm not worrying about it :-).