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