Skip to content

Instantly share code, notes, and snippets.

@hoorayimhelping
Created September 8, 2015 18:37
Show Gist options
  • Save hoorayimhelping/ae0e4c4a85f229f337bc to your computer and use it in GitHub Desktop.
Save hoorayimhelping/ae0e4c4a85f229f337bc to your computer and use it in GitHub Desktop.
diff --git a/js/src/edge.js b/js/src/edge.js
new file mode 100644
index 0000000..e151541
--- /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..00ab25c 100644
--- a/js/src/graph.js
+++ b/js/src/graph.js
@@ -1,22 +1,28 @@
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);
},
- neighbors: function(node) {}
- // : adds to G the edge from x to y, if it is not there.
+ areAdjacent: function(node1, node2) {
+ return this.edges.some(function(edge) {
+ return edge.areAdjacent(node1, node2);
+ });
+ }
+
// 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..7c7d11e 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 delta-v graph around kerbin", 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