1 require File
.expand_path(File
.dirname(__FILE__
) + '/../spec_helper')
12 let (:g) { Graph
.new
}
13 describe
"#initialize" do
14 it
"creates an empty graph" do
16 g
.edges
.should be_empty
17 g
.vertices
.should be_empty
20 it
"creates a graph with some parameters" do
21 g
= Graph
.new
:value1 => 1, :value2 => "value2", :value3 => :v3
23 g
.value2
.should
== "value2"
24 g
.value3
.should
== :v3
25 g
.value4
.should be_nil
30 describe
"adds attribues" do
31 it
"adds then reports arbitrary attributes" do
38 it
"adds a set of vertices" do
39 g
.vertices
.should be_empty
43 g
.should
have(2).vertices
44 g
.vertices
.should
include(v1
)
45 g
.vertices
.should
include(v2
)
48 it
"adds a set of edges" do
49 g
.edges
.should be_empty
53 g
.should
have(2).edges
54 g
.edges
.should
include(e1
)
55 g
.edges
.should
include(e2
)
58 it
"adds a mixed set of vertices and edges" do
59 g
.vertices
.should be_empty
60 g
.edges
.should be_empty
65 g
<< v1
<< e1
<< v2
<< e2
66 g
.should
have(2).vertices
67 g
.vertices
.should
include(v1
)
68 g
.vertices
.should
include(v2
)
69 g
.should
have(2).edges
70 g
.edges
.should
include(e1
)
71 g
.edges
.should
include(e2
)
74 it
"adds a subclass of Vertex" do
75 g
.vertices
.should be_empty
79 g
.should
have(2).vertices
80 g
.vertices
.should
include(v1
)
81 g
.vertices
.should
include(v2
)
86 it
"adds and records an edge between vertices" do
87 g
.vertices
.should be_empty
88 g
.edges
.should be_empty
89 v1
= Vertex
.new(:name => :v1)
90 v2
= Vertex
.new(:name => :v2)
93 g
.should
have(2).vertices
94 g
.vertices
.should
include(v1
)
95 g
.vertices
.should
include(v2
)
96 g
.should
have(1).edges
100 describe
"product" do
101 it
"finds a product graph of a pair of one-vertex graphs" do
108 product
= g1
.product g2
110 product
.should
have(1).vertices
111 product
.vertices
.first
.g1_vertex
.should
== g1v1
112 product
.vertices
.first
.g2_vertex
.should
== g2v1
113 product
.edges
.should be_empty
116 it
"finds a product graph of a pair of simple graphs" do
119 g1v1
= Vertex
.new(:name => :g1v1)
120 g1v2
= Vertex
.new(:name => :g1v2)
121 g1
.connect(g1v1
, g1v2
)
122 g2v1
= Vertex
.new(:name => :g2v1)
123 g2v2
= Vertex
.new(:name => :g2v2)
124 g2
.connect(g2v1
, g2v2
)
127 pg
.should
have(4).vertices
128 pg
.should
have(2).edges
131 it
"finds a product graph of not-quite-simple graph" do
136 describe
"initial_similarity" do
140 g1v1
= Vertex
.new(:name => :g1v1)
141 g1v2
= Vertex
.new(:name => :g1v2)
142 g1
.connect(g1v1
, g1v2
)
143 g2v1
= Vertex
.new(:name => :g2v1)
144 g2v2
= Vertex
.new(:name => :g2v2)
145 g2
.connect(g2v1
, g2v2
)
149 def simple_name_similarity(n1
, n2
)
150 1 - n1
.to_s
.codepoints
.to_a
.delete_if
{|c
| n2
.to_s
.codepoints
.to_a
.include? c
}.length
/ n1
.to_s
.length
.to_f
153 it
"should give all nodes an initial similarity of 1 if no block is given" do
154 @pg.initial_similarity
155 @pg.vertices
.each
do |v
|
156 v
.initial_similarity
.should
be_within(0.001).of(1.0)
157 v
.similarity
.should
be_within(0.001).of(1.0)
161 it
"should give all nodes the similarity as defined by the given block" do
162 @pg.initial_similarity
{|v
| simple_name_similarity v
.g1_vertex
.name
, v
.g2_vertex
.name
}
163 @pg.vertices
.each
do |v
|
164 v
.initial_similarity
.should
be_within(0.001).of( simple_name_similarity v
.g1_vertex
.name
, v
.g2_vertex
.name
)
165 v
.similarity
.should
be_within(0.001).of( simple_name_similarity v
.g1_vertex
.name
, v
.g2_vertex
.name
)
171 describe
"similarity flood" do
172 it
"similarity floods a graph of two nodes" do
175 g1v1
= Vertex
.new(:name => :g1v1)
176 g1v2
= Vertex
.new(:name => :g1v2)
177 g1
.connect(g1v1
, g1v2
)
178 g2v1
= Vertex
.new(:name => :g2v1)
179 g2v2
= Vertex
.new(:name => :g2v2)
180 g2
.connect(g2v1
, g2v2
)
183 pg
.initial_similarity
185 pg
.vertices
.each
do |v
|
186 v
.similarity
.should
be_within(0.001).of(1.0)
190 it
"similarity floods a graph of three nodes, a -- b -- c" do
193 it
"simialrity floods a sample graph" do