From 5d4c8249cc22f7fc6f784def527fb72535f61581 Mon Sep 17 00:00:00 2001
From: Neil Smith <neil.github@njae.me.uk>
Date: Mon, 26 Sep 2011 16:59:08 +0100
Subject: [PATCH] Bug fix in Vertex#neighbours

---
 lib/graph.njae/vertex.rb  |  10 +--
 spec/graph/vertex_spec.rb | 125 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 131 insertions(+), 4 deletions(-)

diff --git a/lib/graph.njae/vertex.rb b/lib/graph.njae/vertex.rb
index bf14ddd..4a75b6d 100644
--- a/lib/graph.njae/vertex.rb
+++ b/lib/graph.njae/vertex.rb
@@ -31,10 +31,12 @@ module GraphNjae
     
     # Return the set of neighbouring vertices
     def neighbours
-      vertices = self.edges.map {|e| e.vertices}.flatten
-      vertices_to_me = vertices.select {|v| v == self}
-      other_vertices = vertices.select {|v| v != self}
-      (vertices_to_me[1..-1] || []) + other_vertices
+      #vertices = self.edges.map {|e| e.vertices}.flatten
+      #vertices_to_me = vertices.select {|v| v == self}
+      #other_vertices = vertices.select {|v| v != self}
+      #(vertices_to_me[1..-1] || []) + other_vertices#
+      self.edges.map {|e| e.vertices.take_while {|v| v != self} + 
+                      e.vertices.drop_while {|v| v != self}[1..-1]}.flatten
     end
     
   end
diff --git a/spec/graph/vertex_spec.rb b/spec/graph/vertex_spec.rb
index bf2e601..49ce58c 100644
--- a/spec/graph/vertex_spec.rb
+++ b/spec/graph/vertex_spec.rb
@@ -97,5 +97,130 @@ module GraphNjae
       end
 
     end # #connect
+    
+    describe "#neighbours" do
+      it "finds neighbours of a self loop" do
+        v << v
+        v.should have(1).neighbours
+        v.neighbours.should include v
+      end
+      
+      it "finds neighbours on an edge" do
+        v1 = Vertex.new
+        v << v1
+        v.should have(1).neighbours
+        v.neighbours.should include v1
+        v1.should have(1).neighbours
+        v1.neighbours.should include v
+      end
+      
+      it "finds neighbours with multiple edges" do
+        v1 = Vertex.new
+        v1.id = :v1
+        v << v1
+        v1 << v
+        v.should have(2).neighbours
+        v.neighbours.should include v1
+        v.neighbours.should_not include v
+        v1.should have(2).neighbours
+        v1.neighbours.should include v
+        v1.neighbours.should_not include v1
+      end
+      
+      it "finds neighbours with multiple self loops" do
+        v << v << v << v
+        v.should have(3).neighbours
+        v.neighbours.should include v
+        v.neighbours.uniq.length.should == 1
+      end
+      
+      it "finds neighbours with all sorts of edges" do
+        v1 = Vertex.new ; v1.id = :v1
+        v2 = Vertex.new ; v2.id = :v2
+        v3 = Vertex.new ; v3.id = :v3
+        v1 << v
+        v << v2
+        v2 << v3
+        v2 << v2
+        
+        v.should have(2).neighbours
+        v.neighbours.should include v1
+        v.neighbours.should include v2
+        
+        v1.should have(1).neighbours
+        v1.neighbours.should include v
+        
+        v2.should have(3).neighbours
+        v2.neighbours.should include v
+        v2.neighbours.should include v2
+        v2.neighbours.should include v3
+        
+        v3.should have(1).neighbours
+        v3.neighbours.should include v2
+      end
+      
+      it "finds neighbours in graphs with several vertices" do
+        v1 = Vertex.new ; v1.id = :v1
+        v2 = Vertex.new ; v2.id = :v2
+        v3 = Vertex.new ; v3.id = :v3
+        v4 = Vertex.new ; v4.id = :v4
+        v << v1
+        v1 << v2
+        v2 << v3
+        v << v3
+        v4 << v3
+        v.should have(2).neighbours
+        v.neighbours.should include v1
+        v.neighbours.should include v3
+        v.neighbours.should_not include v
+        v1.should have(2).neighbours
+        v1.neighbours.should include v
+        v1.neighbours.should include v2
+        v1.neighbours.should_not include v1
+        v2.should have(2).neighbours
+        v2.neighbours.should include v1
+        v2.neighbours.should include v3
+        v2.neighbours.should_not include v2
+        v3.should have(3).neighbours
+        v3.neighbours.should include v
+        v3.neighbours.should include v2
+        v3.neighbours.should include v4
+        v3.neighbours.should_not include v3
+        v4.should have(1).neighbours
+        v4.neighbours.should include v3
+        v4.neighbours.should_not include v4
+      end
+      
+      it "finds neighbours with multiple edges between vertices" do
+        v1 = Vertex.new ; v1.id = :v1
+        v2 = Vertex.new ; v2.id = :v2
+        v3 = Vertex.new ; v3.id = :v3
+        v1 << v1 << v
+        v << v2
+        v << v
+        v3 << v2
+        v2 << v3
+        v2 << v2
+        
+        v.should have(3).neighbours
+        v.neighbours.should include v1
+        v.neighbours.should include v2
+        v.neighbours.should include v
+        
+        v1.should have(2).neighbours
+        v1.neighbours.should include v
+        v1.neighbours.should include v1
+        
+        v2.should have(4).neighbours
+        v2.neighbours.should include v
+        v2.neighbours.should include v2
+        v2.neighbours.should include v3
+        v2.neighbours.uniq.length.should == 3
+        
+        v3.should have(2).neighbours
+        v3.neighbours.should include v2
+        v3.neighbours.uniq.length.should == 1
+      end
+    end # #neighbours
   end
 end
-- 
2.34.1