011dd8625720dd601cd4868257ae7224273fb133
3 # A simple graph library
7 # A container for all the parts of a graph. The graph can have arbitrary attributes,
8 # treated as method names.
9 class Graph
< OpenStruct
10 def initialize(values
= {})
12 self.edges
= Array
.new
13 self.vertices
= Array
.new
17 # Add a Vertex or Edge to the graph.
19 if other
.class.ancestors
.include? Vertex
20 self.vertices
<< other
21 elsif other
.class.ancestors
.include? Edge
27 # Connects two vertices, creating and storing a new edge
28 # Also adds the vertices, unless they're already in the graph
29 def connect(vertex1
, vertex2
)
30 self.vertices
<< vertex1
unless self.vertices
.include? vertex1
31 self.vertices
<< vertex2
unless self.vertices
.include? vertex2
34 edge
<< vertex1
<< vertex2
37 # Form a product graph of this graph and the other.
38 # Return the product graph.
40 product_graph
= Graph
.new
41 self.vertices
.each
do |v1
|
42 other
.vertices
.each
do |v2
|
43 product_graph
<< Vertex
.new({:g1_vertex => v1
, :g2_vertex => v2
})
46 self.edges
.each
do |e1
|
47 e1_vertices
= e1
.vertices
48 other
.edges
.each
do |e2
|
49 e2_vertices
= e2
.vertices
50 source
= product_graph
.vertices
.find
{|v
| v
.g1_vertex
== e1_vertices
[0] and v
.g2_vertex
== e2_vertices
[0]}
51 destination
= product_graph
.vertices
.find
{|v
| v
.g1_vertex
== e1_vertices
[1] and v
.g2_vertex
== e2_vertices
[1]}
52 product_graph
.connect source
, destination
53 source
= product_graph
.vertices
.find
{|v
| v
.g1_vertex
== e1_vertices
[0] and v
.g2_vertex
== e2_vertices
[1]}
54 destination
= product_graph
.vertices
.find
{|v
| v
.g1_vertex
== e1_vertices
[1] and v
.g2_vertex
== e2_vertices
[0]}
55 product_graph
.connect source
, destination
62 def initial_similarity
63 self.vertices
.each
do |v
|
65 v
.initial_similarity
= yield v
67 v
.initial_similarity
= 1.0
69 v
.similarity
= v
.initial_similarity
73 # Performs similarity flooding on a graph
74 # Assumes that the initial similarity has already been calculated
75 def similarity_flood(opts
= {})
76 max_iterations
= opts
[:iterations] || 100
77 max_residual
= opts
[:max_residual] || 0.001
79 residual
= max_residual
+ 1
80 while residual
> max_residual
and iteration
<= max_iterations
81 self.vertices
.each
do |v
|
82 v
.last_similarity
= v
.similarity
84 self.vertices
.each
do |v
|
85 n
= v
.neighbours
.length
86 v
.neighbours
.each
do |neighbour
|
87 neighbour
.similarity
+= v
.last_similarity
/ n
90 max_similarity
= vertices
.max
{|v
, w
| v
.similarity
<=> w
.similarity
}.similarity
91 self.vertices
.each
do |v
|
92 v
.similarity
= v
.similarity
/ max_similarity
94 residual
= Math
.sqrt(self.vertices
.reduce(0) {|a
, v
| a
+= (v
.similarity
- v
.last_similarity
) ** 2})