lib/graph.njae/graph.rb

   1 require 'ostruct'
   2
   3 # A simple graph library
   4
   5 module GraphNjae
   6
   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 = {})
  11       super(values)
  12       self.edges = Array.new
  13       self.vertices = Array.new
  14       self
  15     end
  16
  17     # Add a Vertex or Edge to the graph.
  18     def <<(other)
  19       if other.class.ancestors.include? Vertex
  20         self.vertices << other
  21       elsif other.class.ancestors.include? Edge
  22         self.edges << other
  23       end
  24       self
  25     end
  26
  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
  32       edge = Edge.new
  33       self.edges << edge
  34       edge << vertex1 << vertex2
  35     end
  36
  37     # Form a product graph of this graph and the other.
  38     # Return the product graph.
  39     def product(other)
  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})
  44         end
  45       end
  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
  56         end
  57       end
  58       product_graph
  59     end
  60
  61   end # class
  62 end