CP-20813: CompressedSparseRowGraph bugs

[fubar-coder]

From unknown CodePlex user on Sunday, 22 May 2011 08:41:54

The attached patch fixes two issues with the CompressedSparseRowGraph implementation:  

• When building the range list an incorrect start was specified for the range.
• TryGetOutEdges always returned false even if ranges were returned.   In addition to these fixes, a single Range(0, 0) object is shared across all empty ranges in the graph to save memory.

CompressedSparseRowGraph.cs.patch

Index: CompressedSparseRowGraph.cs
===================================================================
--- CompressedSparseRowGraph.cs (revision 93)
+++ CompressedSparseRowGraph.cs (revision 97)
@@ -77,14 +77,14 @@

             var outEdgeStartRanges = new Dictionary<TVertex, Range>(visitedGraph.VertexCount);
             var outEdges = new TVertex[visitedGraph.EdgeCount];
+            var emptyRange = new Range(0, 0);

-            int start = 0;
             int end = 0;
             int index = 0;
             foreach (var vertex in visitedGraph.Vertices)
             {
-                end = start + visitedGraph.OutDegree(vertex);
-                var range = new Range(start, end);
+                end = index + visitedGraph.OutDegree(vertex);
+                var range = end == index ? emptyRange : new Range(index, end);
                 outEdgeStartRanges.Add(vertex, range);
                 foreach (var edge in visitedGraph.OutEdges(vertex))
                     outEdges[index++] = edge.Target;
@@ -211,11 +211,12 @@

         public bool TryGetOutEdges(TVertex v, out IEnumerable<SEquatableEdge<TVertex>> edges)
         {
-            var range = this.outEdgeStartRanges[v];
-            if (range.Length > 0)
+            Range range;
+            if (this.outEdgeStartRanges.TryGetValue(v, out range) &&
+                range.Length > 0)
             {
                 edges = this.OutEdges(v);
-                return false;
+                return true;
             }

             edges = null;

[fubar-coder]

Form unknown CodePlex user on Monday, 14 November 2011 22:03:56

Resolved with changeset 63814.