Created
September 8, 2015 18:33
-
-
Save hoorayimhelping/01ef64b15e2e2905262a to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| diff --git a/js/src/edge.js b/js/src/edge.js | |
| new file mode 100644 | |
| index 0000000..e829916 | |
| --- /dev/null | |
| +++ b/js/src/edge.js | |
| @@ -0,0 +1,24 @@ | |
| +var Edge = function(value) { | |
| + this.id = value || new Date().getTime(); | |
| + | |
| + this.nodes = {}; | |
| + this.value = value || 0; | |
| +}; | |
| + | |
| +Edge.prototype = { | |
| + add: function(node1, node2) { | |
| + this.nodes = {}; | |
| + | |
| + this.nodes = { | |
| + head: node1, | |
| + tail: node2 | |
| + }; | |
| + }, | |
| + | |
| + areAdjacent: function(node1, node2) { | |
| + return this.nodes.head.id === node1.id | |
| + && this.nodes.tail.id === node2.id; | |
| + } | |
| +}; | |
| + | |
| +module.exports = Edge; | |
| \ No newline at end of file | |
| diff --git a/js/src/graph.js b/js/src/graph.js | |
| index 3c73c0f..351df56 100644 | |
| --- a/js/src/graph.js | |
| +++ b/js/src/graph.js | |
| @@ -1,22 +1,32 @@ | |
| var Node = require('./node'); | |
| +var Edge = require('./edge'); | |
| var Graph = function() { | |
| - this.graph = []; | |
| + this.nodes = []; | |
| + this.edges = []; | |
| }; | |
| // https://en.wikipedia.org/wiki/Graph_(abstract_data_type) | |
| Graph.prototype = { | |
| - add: function(node1, node2) { | |
| - node1.add(node2); | |
| - node2.add(node1); | |
| + addNode: function(node) { | |
| + this.nodes.push(node); | |
| }, | |
| - isAdjacent: function(node1, node2) { | |
| - return node1.isAdjacentWith(node2) || node2.isAdjacentWith(node1); | |
| + addEdge: function(edge, node1, node2) { | |
| + edge.add(node1, node2); | |
| + this.edges.push(edge); | |
| + }, | |
| + | |
| + areAdjacent: function(node1, node2) { | |
| + return this.edges.some(function(edge) { | |
| + return edge.areAdjacent(node1, node2); | |
| + }); | |
| + }, | |
| + | |
| + neighbors: function(node) { | |
| + return node.neighbors; | |
| }, | |
| - neighbors: function(node) {} | |
| - // : adds to G the edge from x to y, if it is not there. | |
| // delete(G, x, y): removes the edge from x to y, if it is there. | |
| // get_node_value(G, x): returns the value associated with the node x. | |
| // set_node_value(G, x, a): sets the value associated with the node x to a. | |
| diff --git a/js/src/node.js b/js/src/node.js | |
| index b5595a7..dbdddf4 100644 | |
| --- a/js/src/node.js | |
| +++ b/js/src/node.js | |
| @@ -1,17 +1,10 @@ | |
| var Node = function() { | |
| this.id = new Date().getTime(); | |
| - this.neighbors = []; | |
| }; | |
| Node.prototype = { | |
| - add: function(node) { | |
| - this.neighbors.push(node); | |
| - }, | |
| - | |
| - isAdjacentWith: function(node) { | |
| - return this.neighbors.some(function(current_node) { | |
| - return current_node.id === node.id; | |
| - }); | |
| + toString: function() { | |
| + return this.id; | |
| } | |
| }; | |
| diff --git a/js/test/graph.js b/js/test/graph.js | |
| index 53d293a..fa170f7 100644 | |
| --- a/js/test/graph.js | |
| +++ b/js/test/graph.js | |
| @@ -1,6 +1,7 @@ | |
| var test = require('tape'); | |
| var Graph = require('../src/graph'); | |
| var Node = require('../src/node'); | |
| +var Edge = require('../src/edge'); | |
| var newNode = function(id) { | |
| var node = new Node(); | |
| @@ -9,25 +10,40 @@ var newNode = function(id) { | |
| return node; | |
| }; | |
| -test("adding a node to another node's adjacency graph", function(t) { | |
| +var newEdge = function(value) { | |
| + return new Edge(value); | |
| +}; | |
| + | |
| +test("creating a simple delta-v graph of the kerbin system", function(t) { | |
| + // http://i.imgur.com/duY2S.png | |
| var graph = new Graph(); | |
| - var node1 = newNode(1); | |
| - var node2 = newNode(2); | |
| - var node3 = newNode(3); | |
| - var node4 = newNode(4); | |
| + var kerbin = newNode('Kerbin'); | |
| + var low_kerbin_orbit = newNode('Low Kerbin Orbit'); | |
| + var geostationary_transfer_orbit = newNode('GTO'); | |
| + var mun_transfer = newNode('Mun Transfer'); | |
| + | |
| + var kerbin_lko = newEdge(3800); | |
| + var lko_gto = newEdge(670); | |
| + var lko_mun_transfer = newEdge(190); | |
| + | |
| + t.plan(5); | |
| - t.plan(4); | |
| + graph.addNode(kerbin); | |
| + graph.addNode(low_kerbin_orbit); | |
| + graph.addNode(geostationary_transfer_orbit); | |
| + graph.addNode(mun_transfer); | |
| - graph.add(node1, node2); | |
| - graph.add(node1, node3); | |
| - graph.add(node3, node4); | |
| + graph.addEdge(kerbin_lko, kerbin, low_kerbin_orbit); | |
| + graph.addEdge(lko_gto, low_kerbin_orbit, geostationary_transfer_orbit); | |
| + graph.addEdge(lko_mun_transfer, low_kerbin_orbit, mun_transfer); | |
| - t.true(graph.isAdjacent(node1, node2), "nodes that have been connected are adjacent"); | |
| - t.true(graph.isAdjacent(node3, node4), "nodes that have been connected are adjacent"); | |
| + t.true(graph.areAdjacent(kerbin, low_kerbin_orbit)); | |
| + t.true(graph.areAdjacent(low_kerbin_orbit, geostationary_transfer_orbit)); | |
| + t.true(graph.areAdjacent(low_kerbin_orbit, mun_transfer)); | |
| - t.false(graph.isAdjacent(node2, node3), "nodes that haven't been connected aren't adjacent"); | |
| - t.false(graph.isAdjacent(node1, node4), "adjacency isn't transitive"); | |
| + t.false(graph.areAdjacent(kerbin, geostationary_transfer_orbit)); | |
| + t.false(graph.areAdjacent(kerbin, mun_transfer)); | |
| t.end(); | |
| }); | |
| \ No newline at end of file | |
| diff --git a/js/test/node.js b/js/test/node.js | |
| deleted file mode 100644 | |
| index 1333e90..0000000 | |
| --- a/js/test/node.js | |
| +++ /dev/null | |
| @@ -1,30 +0,0 @@ | |
| -var test = require('tape'); | |
| -var Node = require('../src/node'); | |
| - | |
| -test("adding an adjacent node", function(t) { | |
| - var node = new Node(); | |
| - | |
| - t.plan(1); | |
| - | |
| - node.add({}); | |
| - t.equal(node.neighbors.length, 1); | |
| - | |
| - t.end(); | |
| -}); | |
| - | |
| -test("node adjacency", function(t) { | |
| - var node = new Node(); | |
| - t.plan(2); | |
| - | |
| - var other_node = new Node(); | |
| - other_node.id = 1; | |
| - | |
| - node.add(other_node); | |
| - t.true(node.isAdjacentWith(other_node), "returns true when the node is adjacent with this node"); | |
| - | |
| - var yet_another_node = new Node(); | |
| - | |
| - t.false(node.isAdjacentWith(yet_another_node), "returns false when the node is not adjacent with this node"); | |
| - | |
| - t.end(); | |
| -}); | |
| \ No newline at end of file |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment