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 "creates a self-connection" do
  92         e = v.connect v
  93
  94         v.should have(1).neighbours
  95         v.neighbours.should include(v)
  96
  97         v.should have(1).edges
  98         v.edges.should include(e)
  99
 100         e.should have(2).vertices
 101         e.vertices.uniq.length.should == 1
 102         e.vertices.should include(v)
 103
 104         e.should have(2).connections
 105       end
 106
 107     end # #connect
 108
 109     describe "#neighbours" do
 110       it "finds neighbours of a self loop" do
 111         v << v
 112         v.should have(1).neighbours
 113         v.neighbours.should include v
 114       end
 115
 116       it "finds neighbours on an edge" do
 117         v1 = Vertex.new
 118         v << v1
 119         v.should have(1).neighbours
 120         v.neighbours.should include v1
 121         v1.should have(1).neighbours
 122         v1.neighbours.should include v
 123       end
 124
 125       it "finds neighbours with multiple edges" do
 126         v1 = Vertex.new
 127         v1.id = :v1
 128         v << v1
 129         v1 << v
 130         v.should have(2).neighbours
 131         v.neighbours.should include v1
 132         v.neighbours.should_not include v
 133         v1.should have(2).neighbours
 134         v1.neighbours.should include v
 135         v1.neighbours.should_not include v1
 136       end
 137
 138       it "finds neighbours with multiple self loops" do
 139         v << v << v << v
 140         v.should have(3).neighbours
 141         v.neighbours.should include v
 142         v.neighbours.uniq.length.should == 1
 143       end
 144
 145       it "finds neighbours with all sorts of edges" do
 146         v1 = Vertex.new ; v1.id = :v1
 147         v2 = Vertex.new ; v2.id = :v2
 148         v3 = Vertex.new ; v3.id = :v3
 149         v1 << v
 150         v << v2
 151         v2 << v3
 152         v2 << v2
 153
 154         v.should have(2).neighbours
 155         v.neighbours.should include v1
 156         v.neighbours.should include v2
 157
 158         v1.should have(1).neighbours
 159         v1.neighbours.should include v
 160
 161         v2.should have(3).neighbours
 162         v2.neighbours.should include v
 163         v2.neighbours.should include v2
 164         v2.neighbours.should include v3
 165
 166         v3.should have(1).neighbours
 167         v3.neighbours.should include v2
 168       end
 169
 170       it "finds neighbours in graphs with several vertices" do
 171         v1 = Vertex.new ; v1.id = :v1
 172         v2 = Vertex.new ; v2.id = :v2
 173         v3 = Vertex.new ; v3.id = :v3
 174         v4 = Vertex.new ; v4.id = :v4
 175         v << v1
 176         v1 << v2
 177         v2 << v3
 178         v << v3
 179         v4 << v3
 180         v.should have(2).neighbours
 181         v.neighbours.should include v1
 182         v.neighbours.should include v3
 183         v.neighbours.should_not include v
 184         v1.should have(2).neighbours
 185         v1.neighbours.should include v
 186         v1.neighbours.should include v2
 187         v1.neighbours.should_not include v1
 188         v2.should have(2).neighbours
 189         v2.neighbours.should include v1
 190         v2.neighbours.should include v3
 191         v2.neighbours.should_not include v2
 192         v3.should have(3).neighbours
 193         v3.neighbours.should include v
 194         v3.neighbours.should include v2
 195         v3.neighbours.should include v4
 196         v3.neighbours.should_not include v3
 197         v4.should have(1).neighbours
 198         v4.neighbours.should include v3
 199         v4.neighbours.should_not include v4
 200       end
 201
 202       it "finds neighbours with multiple edges between vertices" do
 203         v1 = Vertex.new ; v1.id = :v1
 204         v2 = Vertex.new ; v2.id = :v2
 205         v3 = Vertex.new ; v3.id = :v3
 206         v1 << v1 << v
 207         v << v2
 208         v << v
 209         v3 << v2
 210         v2 << v3
 211         v2 << v2
 212
 213         v.should have(3).neighbours
 214         v.neighbours.should include v1
 215         v.neighbours.should include v2
 216         v.neighbours.should include v
 217
 218         v1.should have(2).neighbours
 219         v1.neighbours.should include v
 220         v1.neighbours.should include v1
 221
 222         v2.should have(4).neighbours
 223         v2.neighbours.should include v
 224         v2.neighbours.should include v2
 225         v2.neighbours.should include v3
 226         v2.neighbours.uniq.length.should == 3
 227
 228         v3.should have(2).neighbours
 229         v3.neighbours.should include v2
 230         v3.neighbours.uniq.length.should == 1
 231       end
 232     end # #neighbours
 233   end
 234 end