From 624e339a169bd96eb01da7288a8904e0d1830e42 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Thu, 22 Sep 2011 08:41:34 +0100 Subject: [PATCH] Initial commit --- lib/graph.njae.rb | 3 ++ lib/graph/edge.rb | 33 ++++++++++++ lib/graph/edge.rb~ | 32 ++++++++++++ lib/graph/graph.rb | 21 ++++++++ lib/graph/graph.rb~ | 20 ++++++++ lib/graph/vertex.rb | 32 ++++++++++++ lib/graph/vertex.rb~ | 31 ++++++++++++ spec/graph.njae_spec.rb | 7 --- spec/graph/edge_spec.rb | 100 ++++++++++++++++++++++++++++++++++++ spec/graph/edge_spec.rb~ | 90 +++++++++++++++++++++++++++++++++ spec/graph/graph_spec.rb | 65 ++++++++++++++++++++++++ spec/graph/graph_spec.rb~ | 65 ++++++++++++++++++++++++ spec/graph/vertex_spec.rb | 101 +++++++++++++++++++++++++++++++++++++ spec/graph/vertex_spec.rb~ | 101 +++++++++++++++++++++++++++++++++++++ 14 files changed, 694 insertions(+), 7 deletions(-) create mode 100644 lib/graph/edge.rb create mode 100644 lib/graph/edge.rb~ create mode 100644 lib/graph/graph.rb create mode 100644 lib/graph/graph.rb~ create mode 100644 lib/graph/vertex.rb create mode 100644 lib/graph/vertex.rb~ delete mode 100644 spec/graph.njae_spec.rb create mode 100644 spec/graph/edge_spec.rb create mode 100644 spec/graph/edge_spec.rb~ create mode 100644 spec/graph/graph_spec.rb create mode 100644 spec/graph/graph_spec.rb~ create mode 100644 spec/graph/vertex_spec.rb create mode 100644 spec/graph/vertex_spec.rb~ 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 -- 2.34.1