spec/graph/vertex_spec.rb

   1 require File.expand_path(File.dirname(__FILE__) + '/../spec_helper')
   2
   3 module GraphNjae
   4   describe Vertex do
   5     let (:v) { Vertex.new }
   6
   7     describe "#initialize" do
   8       it "creates an empty vertex" do
   9         v = Vertex.new
  10         v.edges.should be_empty
  11       end
  12     end # #initialize
  13
  14     describe "adds attribues" do
  15       it "adds then reports arbitrary attributes" do
  16         v.score = 15
  17         v.score.should == 15
  18       end
  19     end # adds attributes
  20
  21     describe "#<<" do
  22       it "adds a single edge between vertices" do
  23         v.neighbours.should be_empty
  24         v.edges.should be_empty
  25
  26         v1 = Vertex.new
  27         v << v1
  28
  29         v1.id = :v1 # Need this to ensure that v != v1
  30
  31         v.should have(1).edges
  32         v1.should have(1).edges
  33         e = v.edges[0]
  34         v1.edges.should include(e)
  35
  36         v.should have(1).neighbours
  37         v.neighbours.should include(v1)
  38         v.neighbours.should_not include(v)
  39         v1.should have(1).neighbours
  40         v1.neighbours.should include(v)
  41         v1.neighbours.should_not include(v1)
  42       end
  43
  44       it "adds a single edge as a self-loop" do
  45         v.neighbours.should be_empty
  46         v.edges.should be_empty
  47
  48         v << v
  49
  50         v.should have(1).edges
  51         v.should have(1).neighbours
  52         v.neighbours.should include(v)
  53       end
  54     end # #<<
  55
  56     describe "connect" do
  57       it "connects two vertices" do
  58         v1 = Vertex.new
  59         v1.id = :v1 # Need this to ensure that v != v1
  60
  61         e = v.connect v1
  62
  63         v.should have(1).neighbours
  64         v.neighbours.should include(v1)
  65         v.neighbours.should_not include(v)
  66
  67         v1.should have(1).neighbours
  68         v1.neighbours.should include(v)
  69         v1.neighbours.should_not include(v1)
  70
  71         v.should have(1).edges
  72         v.edges.should include(e)
  73         v1.should have(1).edges
  74         v1.edges.should include(e)
  75
  76         e.should have(2).vertices
  77         e.vertices.should include(v)
  78         e.vertices.should include(v1)
  79
  80               e.should have(2).connections
  81       end
  82
  83       it "creates a self-connection" do
  84         e = v.connect v
  85
  86         v.should have(1).neighbours
  87         v.neighbours.should include(v)
  88
  89         v.should have(1).edges
  90         v.edges.should include(e)
  91
  92         e.should have(2).vertices
  93         e.vertices.uniq.length.should == 1
  94         e.vertices.should include(v)
  95
  96         e.should have(2).connections
  97       end
  98
  99     end # #connect
 100
 101     describe "#neighbours" do
 102       it "finds neighbours of a self loop" do
 103         v << v
 104         v.should have(1).neighbours
 105         v.neighbours.should include v
 106       end
 107
 108       it "finds neighbours on an edge" do
 109         v1 = Vertex.new
 110         v << v1
 111         v.should have(1).neighbours
 112         v.neighbours.should include v1
 113         v1.should have(1).neighbours
 114         v1.neighbours.should include v
 115       end
 116
 117       it "finds neighbours with multiple edges" do
 118         v1 = Vertex.new
 119         v1.id = :v1
 120         v << v1
 121         v1 << v
 122         v.should have(2).neighbours
 123         v.neighbours.should include v1
 124         v.neighbours.should_not include v
 125         v1.should have(2).neighbours
 126         v1.neighbours.should include v
 127         v1.neighbours.should_not include v1
 128       end
 129
 130       it "finds neighbours with multiple self loops" do
 131         v << v << v << v
 132         v.should have(3).neighbours
 133         v.neighbours.should include v
 134         v.neighbours.uniq.length.should == 1
 135       end
 136
 137       it "finds neighbours with all sorts of edges" do
 138         v1 = Vertex.new ; v1.id = :v1
 139         v2 = Vertex.new ; v2.id = :v2
 140         v3 = Vertex.new ; v3.id = :v3
 141         v1 << v
 142         v << v2
 143         v2 << v3
 144         v2 << v2
 145
 146         v.should have(2).neighbours
 147         v.neighbours.should include v1
 148         v.neighbours.should include v2
 149
 150         v1.should have(1).neighbours
 151         v1.neighbours.should include v
 152
 153         v2.should have(3).neighbours
 154         v2.neighbours.should include v
 155         v2.neighbours.should include v2
 156         v2.neighbours.should include v3
 157
 158         v3.should have(1).neighbours
 159         v3.neighbours.should include v2
 160       end
 161
 162       it "finds neighbours in graphs with several vertices" do
 163         v1 = Vertex.new ; v1.id = :v1
 164         v2 = Vertex.new ; v2.id = :v2
 165         v3 = Vertex.new ; v3.id = :v3
 166         v4 = Vertex.new ; v4.id = :v4
 167         v << v1
 168         v1 << v2
 169         v2 << v3
 170         v << v3
 171         v4 << v3
 172         v.should have(2).neighbours
 173         v.neighbours.should include v1
 174         v.neighbours.should include v3
 175         v.neighbours.should_not include v
 176         v1.should have(2).neighbours
 177         v1.neighbours.should include v
 178         v1.neighbours.should include v2
 179         v1.neighbours.should_not include v1
 180         v2.should have(2).neighbours
 181         v2.neighbours.should include v1
 182         v2.neighbours.should include v3
 183         v2.neighbours.should_not include v2
 184         v3.should have(3).neighbours
 185         v3.neighbours.should include v
 186         v3.neighbours.should include v2
 187         v3.neighbours.should include v4
 188         v3.neighbours.should_not include v3
 189         v4.should have(1).neighbours
 190         v4.neighbours.should include v3
 191         v4.neighbours.should_not include v4
 192       end
 193
 194       it "finds neighbours with multiple edges between vertices" do
 195         v1 = Vertex.new ; v1.id = :v1
 196         v2 = Vertex.new ; v2.id = :v2
 197         v3 = Vertex.new ; v3.id = :v3
 198         v1 << v1 << v
 199         v << v2
 200         v << v
 201         v3 << v2
 202         v2 << v3
 203         v2 << v2
 204
 205         v.should have(3).neighbours
 206         v.neighbours.should include v1
 207         v.neighbours.should include v2
 208         v.neighbours.should include v
 209
 210         v1.should have(2).neighbours
 211         v1.neighbours.should include v
 212         v1.neighbours.should include v1
 213
 214         v2.should have(4).neighbours
 215         v2.neighbours.should include v
 216         v2.neighbours.should include v2
 217         v2.neighbours.should include v3
 218         v2.neighbours.uniq.length.should == 3
 219
 220         v3.should have(2).neighbours
 221         v3.neighbours.should include v2
 222         v3.neighbours.uniq.length.should == 1
 223       end
 224     end # #neighbours
 225   end
 226 end