From: Neil Smith <neil.github@njae.me.uk>
Date: Thu, 22 Sep 2011 07:41:34 +0000 (+0100)
Subject: Initial commit
X-Git-Tag: v~5
X-Git-Url: https://git.njae.me.uk/?p=graph.njae.git;a=commitdiff_plain;h=624e339a169bd96eb01da7288a8904e0d1830e42

Initial commit
---

diff --git a/lib/graph.njae.rb b/lib/graph.njae.rb
index e69de29..f6d4873 100644
--- a/lib/graph.njae.rb
+++ b/lib/graph.njae.rb
@@ -0,0 +1,3 @@
+require 'graph/graph'
+require 'graph/edge'
+require 'graph/vertex'
diff --git a/lib/graph/edge.rb b/lib/graph/edge.rb
new file mode 100644
index 0000000..c579a2f
--- /dev/null
+++ b/lib/graph/edge.rb
@@ -0,0 +1,33 @@
+require 'ostruct'
+
+module Graph
+  class Edge < OpenStruct
+    def initialize
+      super
+      self.connections = []
+      self
+    end
+    
+    def <<(other)
+      c = Connection.new
+      c.end = other
+      self.connections << c
+      self
+    end
+    
+    def vertices
+      self.connections.map {|c| c.end}
+    end
+    
+    def connection_at(vertex)
+      self.connections.select {|c| c.end.equal?  vertex}.first
+    end
+  end
+  
+  class Connection < OpenStruct
+    def initialize
+      super
+      self
+    end
+  end
+end
diff --git a/lib/graph/edge.rb~ b/lib/graph/edge.rb~
new file mode 100644
index 0000000..10f133e
--- /dev/null
+++ b/lib/graph/edge.rb~
@@ -0,0 +1,32 @@
+require 'ostruct'
+
+module Graph
+  class Edge < OpenStruct
+    def initialize
+      super
+      self.connections = []
+      self
+    end
+    
+    def <<(other)
+      c = Connection.new
+      c.end = other
+      self.connections << c
+      self
+    end
+    
+    def vertices
+      self.connections.map {|c| c.end}
+    end
+    
+    def connection_at(vertex)
+      self.connections.select {|c| c.end.equal?  vertex}.first
+    end
+  end
+  
+  class Connection < OpenStruct
+    def initialize
+      super
+    end
+  end
+end
diff --git a/lib/graph/graph.rb b/lib/graph/graph.rb
new file mode 100644
index 0000000..c9d83b1
--- /dev/null
+++ b/lib/graph/graph.rb
@@ -0,0 +1,21 @@
+require 'ostruct'
+
+module Graph
+  class Graph < OpenStruct
+    def initialize
+      super
+      self.edges = Array.new
+      self.vertices = Array.new
+      self
+    end
+    
+    def <<(other)
+      if other.class == Vertex
+        self.vertices << other
+      elsif
+        self.edges << other
+      end
+      self
+    end
+  end
+end
diff --git a/lib/graph/graph.rb~ b/lib/graph/graph.rb~
new file mode 100644
index 0000000..0201c84
--- /dev/null
+++ b/lib/graph/graph.rb~
@@ -0,0 +1,20 @@
+require 'ostruct'
+
+module Graph
+  class Graph < OpenStruct
+    def initialize
+      super
+      self.edges = Array.new
+      self.vertices = Array.new
+    end
+    
+    def <<(other)
+      if other.class == Vertex
+        self.vertices << other
+      elsif
+        self.edges << other
+      end
+      self
+    end
+  end
+end
diff --git a/lib/graph/vertex.rb b/lib/graph/vertex.rb
new file mode 100644
index 0000000..0bccb57
--- /dev/null
+++ b/lib/graph/vertex.rb
@@ -0,0 +1,32 @@
+require 'ostruct'
+
+module Graph
+  class Vertex < OpenStruct
+    def initialize
+      super
+      self.edges = []
+      self
+    end
+    
+    def connect(other)
+      e = Edge.new
+      e << self << other
+      self.edges << e
+      other.edges << e unless self === other
+      e
+    end
+    
+    def <<(other)
+      connect(other)
+      self
+    end
+    
+    def neighbours
+      vertices = self.edges.map {|e| e.vertices}.flatten
+      vertices_to_me = vertices.select {|v| v == self}
+      other_vertices = vertices.select {|v| v != self}
+      (vertices_to_me[1..-1] || []) + other_vertices
+    end
+    
+  end
+end
diff --git a/lib/graph/vertex.rb~ b/lib/graph/vertex.rb~
new file mode 100644
index 0000000..6a85373
--- /dev/null
+++ b/lib/graph/vertex.rb~
@@ -0,0 +1,31 @@
+require 'ostruct'
+
+module Graph
+  class Vertex < OpenStruct
+    def initialize
+      super
+      self.edges = []
+    end
+    
+    def connect(other)
+      e = Edge.new
+      e << self << other
+      self.edges << e
+      other.edges << e unless self === other
+      e
+    end
+    
+    def <<(other)
+      connect(other)
+      self
+    end
+    
+    def neighbours
+      vertices = self.edges.map {|e| e.vertices}.flatten
+      vertices_to_me = vertices.select {|v| v == self}
+      other_vertices = vertices.select {|v| v != self}
+      (vertices_to_me[1..-1] || []) + other_vertices
+    end
+    
+  end
+end
diff --git a/spec/graph.njae_spec.rb b/spec/graph.njae_spec.rb
deleted file mode 100644
index d752562..0000000
--- a/spec/graph.njae_spec.rb
+++ /dev/null
@@ -1,7 +0,0 @@
-require File.expand_path(File.dirname(__FILE__) + '/spec_helper')
-
-describe "Graph.njae" do
-  it "fails" do
-    fail "hey buddy, you should probably rename this file and start specing for real"
-  end
-end
diff --git a/spec/graph/edge_spec.rb b/spec/graph/edge_spec.rb
new file mode 100644
index 0000000..8bd1f9a
--- /dev/null
+++ b/spec/graph/edge_spec.rb
@@ -0,0 +1,100 @@
+require File.expand_path(File.dirname(__FILE__) + '/../spec_helper')
+
+module Graph
+  describe Edge do
+    let (:e) { Edge.new }
+    describe "#initialize" do
+      it "creates an empty edge" do
+        e = Edge.new
+        e.connections.should be_empty
+      end
+    end # #initialize
+    
+    describe "adds attribues" do
+      it "adds then reports arbitrary attributes" do
+        e.score = 15
+        e.score.should == 15
+      end
+    end # adds attributes
+    
+    describe "#<<" do
+      it "adds a new vertex to an edge (with a connection)" do
+        e.connections.should be_empty
+        v1 = Vertex.new
+        v2 = Vertex.new
+        e << v1
+        e.should have(1).connections
+        e.should have(1).vertices
+        e.vertices.should include(v1)
+        e << v2
+        e.should have(2).connections
+        e.should have(2).vertices
+        e.vertices.should include(v1)
+        e.vertices.should include(v2)
+      end
+      
+      it "adds several vertices to an edge" do
+        e.connections.should be_empty
+        v1 = Vertex.new
+        v2 = Vertex.new
+        e << v1 << v2
+        e.vertices.should include(v1)
+        e.vertices.should include(v2)
+        e.should have(2).vertices
+      end
+
+      it "adds a self-loop" do
+        e.connections.should be_empty
+        v1 = Vertex.new
+        e << v1 << v1
+        e.vertices.should include(v1)
+        e.should have(2).vertices
+        e.vertices.uniq.length.should == 1
+      end
+    end # #<<
+    
+    describe "connection_at" do
+      it "returns the connection that links to a vertex" do
+        e.connections.should be_empty
+        v1 = Vertex.new
+        v2 = Vertex.new
+        e << v1 << v2
+        
+        e.connection_at(v1).end.should be v1
+        e.connection_at(v2).end.should be v2
+      end
+      
+      it "returns nil if there is no connection to that vertex" do
+        e.connections.should be_empty
+        v1 = Vertex.new
+        v2 = Vertex.new
+        v3 = Vertex.new
+        e << v1 << v2
+        
+        e.connection_at(v3).should be nil
+      end
+      
+      it "returns the vertex for a self-loop" do
+        e.connections.should be_empty
+        v1 = Vertex.new
+        e << v1 << v1
+        
+        e.connection_at(v1).end.should be v1
+      end
+
+    
+    end # #connection_at
+  end # Edge
+  
+  describe Connection do
+    let (:c) {Connection.new }
+    
+    describe "adds attribues" do
+      it "adds then reports arbitrary attributes" do
+        c.score = 15
+        c.score.should == 15
+      end
+    end # adds attributes
+  end # Connection
+  
+end
diff --git a/spec/graph/edge_spec.rb~ b/spec/graph/edge_spec.rb~
new file mode 100644
index 0000000..e4848e5
--- /dev/null
+++ b/spec/graph/edge_spec.rb~
@@ -0,0 +1,90 @@
+require 'spec_helper'
+
+module Graph
+  describe Edge do
+    let (:e) { Edge.new }
+    describe "#initialize" do
+      it "creates an empty edge" do
+        e = Edge.new
+        e.connections.should be_empty
+      end
+    end # #initialize
+    
+    describe "adds attribues" do
+      it "adds then reports arbitrary attributes" do
+        e.score = 15
+        e.score.should == 15
+      end
+    end # adds attributes
+    
+    describe "#<<" do
+      it "adds a new vertex to an edge (with a connection)" do
+        e.connections.should be_empty
+        v1 = Vertex.new
+        v2 = Vertex.new
+        e << v1
+        e.should have(1).connections
+        e.should have(1).vertices
+        e.vertices.should include(v1)
+        e << v2
+        e.should have(2).connections
+        e.should have(2).vertices
+        e.vertices.should include(v1)
+        e.vertices.should include(v2)
+      end
+      
+      it "adds several vertices to an edge" do
+        e.connections.should be_empty
+        v1 = Vertex.new
+        v2 = Vertex.new
+        e << v1 << v2
+        e.vertices.should include(v1)
+        e.vertices.should include(v2)
+        e.should have(2).vertices
+      end
+
+      it "adds a self-loop" do
+        e.connections.should be_empty
+        v1 = Vertex.new
+        e << v1 << v1
+        e.vertices.should include(v1)
+        e.should have(2).vertices
+        e.vertices.uniq.length.should == 1
+      end
+    end # #<<
+    
+    describe "connection_at" do
+      it "returns the connection that links to a vertex" do
+        e.connections.should be_empty
+        v1 = Vertex.new
+        v2 = Vertex.new
+        e << v1 << v2
+        
+        e.connection_at(v1).end.should be v1
+        e.connection_at(v2).end.should be v2
+      end
+      
+      it "returns nil if there is no connection to that vertex" do
+        e.connections.should be_empty
+        v1 = Vertex.new
+        v2 = Vertex.new
+        v3 = Vertex.new
+        e << v1 << v2
+        
+        e.connection_at(v3).should be nil
+      end
+    end # #connection_at
+  end # Edge
+  
+  describe Connection do
+    let (:c) {Connection.new }
+    
+    describe "adds attribues" do
+      it "adds then reports arbitrary attributes" do
+        c.score = 15
+        c.score.should == 15
+      end
+    end # adds attributes
+  end # Connection
+  
+end
\ No newline at end of file
diff --git a/spec/graph/graph_spec.rb b/spec/graph/graph_spec.rb
new file mode 100644
index 0000000..7227a6f
--- /dev/null
+++ b/spec/graph/graph_spec.rb
@@ -0,0 +1,65 @@
+require File.expand_path(File.dirname(__FILE__) + '/../spec_helper')
+
+module Graph
+  describe Graph do
+    let (:g) { Graph.new }
+    describe "#initialize" do
+      it "creates an empty graph" do
+        g = Graph.new
+        g.edges.should be_empty
+        g.vertices.should be_empty
+      end
+    end # #initialize
+      
+    describe "adds attribues" do
+      it "adds then reports arbitrary attributes" do
+        g.score = 15
+        g.score == 15
+      end
+    end # adds attributes
+    
+    describe "#<<" do
+      it "adds a set of vertices" do
+        g.vertices.should be_empty
+        v1 = Vertex.new
+        v2 = Vertex.new
+        g << v1 << v2
+        g.should have(2).vertices
+        g.vertices.should include(v1)
+        g.vertices.should include(v2)
+      end
+      
+      it "adds a set of edges" do
+        g.edges.should be_empty
+        e1 = Edge.new
+        e2 = Edge.new
+        g << e1 << e2
+        g.should have(2).edges
+        g.edges.should include(e1)
+        g.edges.should include(e2)
+      end
+      
+      it "adds a mixed set of vertices and edges" do
+        g.vertices.should be_empty
+        g.edges.should be_empty
+        v1 = Vertex.new
+        v2 = Vertex.new
+        e1 = Edge.new
+        e2 = Edge.new
+        g << v1 << e1 << v2 << e2
+        g.should have(2).vertices
+        g.vertices.should include(v1)
+        g.vertices.should include(v2)
+        g.should have(2).edges
+        g.edges.should include(e1)
+        g.edges.should include(e2)
+      end
+    end # #<<
+
+    describe "connect" do
+      it "adds and records an edge between vertices" do
+      end
+    end # #connect
+    
+  end
+end
diff --git a/spec/graph/graph_spec.rb~ b/spec/graph/graph_spec.rb~
new file mode 100644
index 0000000..e4ec746
--- /dev/null
+++ b/spec/graph/graph_spec.rb~
@@ -0,0 +1,65 @@
+require 'spec_helper'
+
+module Graph
+  describe Graph do
+    let (:g) { Graph.new }
+    describe "#initialize" do
+      it "creates an empty graph" do
+        g = Graph.new
+        g.edges.should be_empty
+        g.vertices.should be_empty
+      end
+    end # #initialize
+      
+    describe "adds attribues" do
+      it "adds then reports arbitrary attributes" do
+        g.score = 15
+        g.score == 15
+      end
+    end # adds attributes
+    
+    describe "#<<" do
+      it "adds a set of vertices" do
+        g.vertices.should be_empty
+        v1 = Vertex.new
+        v2 = Vertex.new
+        g << v1 << v2
+        g.should have(2).vertices
+        g.vertices.should include(v1)
+        g.vertices.should include(v2)
+      end
+      
+      it "adds a set of edges" do
+        g.edges.should be_empty
+        e1 = Edge.new
+        e2 = Edge.new
+        g << e1 << e2
+        g.should have(2).edges
+        g.edges.should include(e1)
+        g.edges.should include(e2)
+      end
+      
+      it "adds a mixed set of vertices and edges" do
+        g.vertices.should be_empty
+        g.edges.should be_empty
+        v1 = Vertex.new
+        v2 = Vertex.new
+        e1 = Edge.new
+        e2 = Edge.new
+        g << v1 << e1 << v2 << e2
+        g.should have(2).vertices
+        g.vertices.should include(v1)
+        g.vertices.should include(v2)
+        g.should have(2).edges
+        g.edges.should include(e1)
+        g.edges.should include(e2)
+      end
+    end # #<<
+
+    describe "connect" do
+      it "adds and records an edge between vertices" do
+      end
+    end # #connect
+    
+  end
+end
\ No newline at end of file
diff --git a/spec/graph/vertex_spec.rb b/spec/graph/vertex_spec.rb
new file mode 100644
index 0000000..637499b
--- /dev/null
+++ b/spec/graph/vertex_spec.rb
@@ -0,0 +1,101 @@
+require File.expand_path(File.dirname(__FILE__) + '/../spec_helper')
+
+module Graph
+  describe Vertex do
+    let (:v) { Vertex.new }
+    
+    describe "#initialize" do
+      it "creates an empty vertex" do
+        v = Vertex.new
+        v.edges.should be_empty
+      end
+    end # #initialize
+    
+    describe "adds attribues" do
+      it "adds then reports arbitrary attributes" do
+        v.score = 15
+        v.score.should == 15
+      end
+    end # adds attributes
+    
+    describe "#<<" do
+      it "adds a single edge between vertices" do
+        v.neighbours.should be_empty
+        v.edges.should be_empty
+        
+        v1 = Vertex.new
+        v << v1
+        
+        v1.id = :v1 # Need this to ensure that v != v1
+        
+        v.should have(1).edges
+        v1.should have(1).edges
+        e = v.edges[0]
+        v1.edges.should include(e)
+        
+        v.should have(1).neighbours
+        v.neighbours.should include(v1)
+        v.neighbours.should_not include(v)
+        v1.should have(1).neighbours
+        v1.neighbours.should include(v)
+        v1.neighbours.should_not include(v1)
+      end
+
+      it "adds a single edge as a self-loop" do
+        v.neighbours.should be_empty
+        v.edges.should be_empty
+        
+        v << v
+        
+        v.should have(1).edges
+        v.should have(1).neighbours
+        v.neighbours.should include(v)
+      end
+    end # #<<
+    
+    describe "connect" do
+      it "connects two vertices" do
+        v1 = Vertex.new
+        v1.id = :v1 # Need this to ensure that v != v1
+
+        e = v.connect v1
+        
+        v.should have(1).neighbours
+        v.neighbours.should include(v1)
+        v.neighbours.should_not include(v)
+
+        v1.should have(1).neighbours
+        v1.neighbours.should include(v)
+        v1.neighbours.should_not include(v1)
+
+        v.should have(1).edges
+        v.edges.should include(e)
+        v1.should have(1).edges
+        v1.edges.should include(e)
+        
+        e.should have(2).vertices
+        e.vertices.should include(v)
+        e.vertices.should include(v1)
+
+              e.should have(2).connections
+      end
+
+      it "creates a self-connection" do
+        e = v.connect v
+        
+        v.should have(1).neighbours
+        v.neighbours.should include(v)
+
+        v.should have(1).edges
+        v.edges.should include(e)
+        
+        e.should have(2).vertices
+        e.vertices.uniq.length.should == 1
+        e.vertices.should include(v)
+
+        e.should have(2).connections
+      end
+
+    end # #connect
+  end
+end
diff --git a/spec/graph/vertex_spec.rb~ b/spec/graph/vertex_spec.rb~
new file mode 100644
index 0000000..3410365
--- /dev/null
+++ b/spec/graph/vertex_spec.rb~
@@ -0,0 +1,101 @@
+require 'spec_helper'
+
+module Graph
+  describe Vertex do
+    let (:v) { Vertex.new }
+    
+    describe "#initialize" do
+      it "creates an empty vertex" do
+	v = Vertex.new
+	v.edges.should be_empty
+      end
+    end # #initialize
+    
+    describe "adds attribues" do
+      it "adds then reports arbitrary attributes" do
+	v.score = 15
+	v.score.should == 15
+      end
+    end # adds attributes
+    
+    describe "#<<" do
+      it "adds a single edge between vertices" do
+	v.neighbours.should be_empty
+	v.edges.should be_empty
+	
+        v1 = Vertex.new
+	v << v1
+	
+	v1.id = :v1 # Need this to ensure that v != v1
+        
+	v.should have(1).edges
+	v1.should have(1).edges
+	e = v.edges[0]
+	v1.edges.should include(e)
+	
+        v.should have(1).neighbours
+	v.neighbours.should include(v1)
+	v.neighbours.should_not include(v)
+	v1.should have(1).neighbours
+	v1.neighbours.should include(v)
+	v1.neighbours.should_not include(v1)
+      end
+
+      it "adds a single edge as a self-loop" do
+	v.neighbours.should be_empty
+	v.edges.should be_empty
+	
+        v << v
+        
+	v.should have(1).edges
+        v.should have(1).neighbours
+	v.neighbours.should include(v)
+      end
+    end # #<<
+    
+    describe "connect" do
+      it "connects two vertices" do
+	v1 = Vertex.new
+	v1.id = :v1 # Need this to ensure that v != v1
+
+	e = v.connect v1
+	
+	v.should have(1).neighbours
+	v.neighbours.should include(v1)
+	v.neighbours.should_not include(v)
+
+	v1.should have(1).neighbours
+	v1.neighbours.should include(v)
+	v1.neighbours.should_not include(v1)
+
+	v.should have(1).edges
+	v.edges.should include(e)
+	v1.should have(1).edges
+	v1.edges.should include(e)
+	
+	e.should have(2).vertices
+	e.vertices.should include(v)
+	e.vertices.should include(v1)
+
+      	e.should have(2).connections
+      end
+
+      it "creates a self-connection" do
+	e = v.connect v
+	
+	v.should have(1).neighbours
+	v.neighbours.should include(v)
+
+	v.should have(1).edges
+	v.edges.should include(e)
+	
+	e.should have(2).vertices
+	e.vertices.uniq.length.should == 1
+	e.vertices.should include(v)
+
+	e.should have(2).connections
+      end
+
+    end # #connect
+  end
+end
\ No newline at end of file