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