faaaf46bca692f1f4367a5aec36b8db4fc290aa2
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