Skip to content

Instantly share code, notes, and snippets.

@hoorayimhelping
Created September 10, 2015 03:25
Show Gist options
  • Save hoorayimhelping/31e805e457f1e45e0080 to your computer and use it in GitHub Desktop.
Save hoorayimhelping/31e805e457f1e45e0080 to your computer and use it in GitHub Desktop.
diff --git a/js/src/edge.js b/js/src/edge.js
index 7dc926b..67e776d 100644
--- a/js/src/edge.js
+++ b/js/src/edge.js
@@ -1,8 +1,8 @@
var Edge = function(options) {
- this.name = options.name;
+ this.props = options || {};
+ this.id = new Date().getTime();
this.nodes = {};
- this.deltav = options.deltav;
};
Edge.prototype = {
diff --git a/js/src/graph.js b/js/src/graph.js
index 00ab25c..09515b6 100644
--- a/js/src/graph.js
+++ b/js/src/graph.js
@@ -2,25 +2,44 @@ var Node = require('./node');
var Edge = require('./edge');
var Graph = function() {
- this.nodes = [];
this.edges = [];
};
// https://en.wikipedia.org/wiki/Graph_(abstract_data_type)
Graph.prototype = {
- addNode: function(node) {
- this.nodes.push(node);
- },
+ addEdge: function(edge, head_node, tail_node) {
+ edge.add(head_node, tail_node);
+
+ head_node.addEdge(edge);
+ tail_node.addEdge(edge);
- addEdge: function(edge, node1, node2) {
- edge.add(node1, node2);
this.edges.push(edge);
},
- areAdjacent: function(node1, node2) {
+ areAdjacent: function(head_node, tail_node) {
return this.edges.some(function(edge) {
- return edge.areAdjacent(node1, node2);
+ return edge.areAdjacent(head_node, tail_node);
});
+ },
+
+ // depth first search
+ walk: function(head_node, final_node) {
+ var current_node = head_node;
+ var total_value = 0;
+
+ current_node.visited = true;
+
+ current_node.edges.forEach(function(edge) {
+ var node = edge.nodes.tail;
+
+ if (!node.visited) {
+ total_value = edge.props.deltav;
+
+ total_value += this.walk(node, final_node)
+ }
+ }, this);
+
+ return total_value;
}
// delete(G, x, y): removes the edge from x to y, if it is there.
diff --git a/js/src/node.js b/js/src/node.js
index dbdddf4..9964b57 100644
--- a/js/src/node.js
+++ b/js/src/node.js
@@ -1,10 +1,14 @@
-var Node = function() {
+var Node = function(options) {
+ this.props = options || {};
+
this.id = new Date().getTime();
+ this.edges = [];
+ this.visited = false;
};
Node.prototype = {
- toString: function() {
- return this.id;
+ addEdge: function(edge) {
+ this.edges.push(edge);
}
};
diff --git a/js/test/graph.js b/js/test/graph.js
index 9bac524..c838cde 100644
--- a/js/test/graph.js
+++ b/js/test/graph.js
@@ -1,4 +1,4 @@
-var test = require('tape');
+var describe = require('tape');
var Graph = require('../src/graph');
var Node = require('../src/node');
var Edge = require('../src/edge');
@@ -14,36 +14,74 @@ var newEdge = function(options) {
return new Edge(options);
};
-test("creating a simple delta-v graph of the delta-v graph around kerbin", function(t) {
- // http://i.imgur.com/duY2S.png
+describe("walking the graph", function(t) {
var graph = new Graph();
- var kerbin = newNode('Kerbin');
- var low_kerbin_orbit = newNode('Low Kerbin Orbit');
- var geostationary_transfer_orbit = newNode('GTO');
- var mun_transfer = newNode('Mun Transfer');
+ describe("walking a simple linear graph", function(t) {
+ t.plan(5);
- var kerbin_lko = newEdge({ deltav: 3800, name: 'kerbin-lko' });
- var lko_gto = newEdge({ deltav: 670, name: 'lko-gto' });
- var lko_mun_transfer = newEdge({ deltav: 190, name: 'lko-mun_transfer' });
+ // values taken from http://i.imgur.com/duY2S.png
+ var kerbin = newNode('Kerbin');
+ var low_kerbin_orbit = newNode('Low Kerbin Orbit');
+ var geostationary_transfer_orbit = newNode('GTO');
+ var mun_transfer = newNode('Mun Transfer');
- t.plan(5);
+ var kerbin_lko = newEdge({ deltav: 3800, name: 'kerbin-lko' });
+ var lko_gto = newEdge({ deltav: 670, name: 'lko-gto' });
+ var lko_mun_transfer = newEdge({ deltav: 190, name: 'lko-mun_transfer' });
- graph.addNode(kerbin);
- graph.addNode(low_kerbin_orbit);
- graph.addNode(geostationary_transfer_orbit);
- graph.addNode(mun_transfer);
+ 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);
- 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.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.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.areAdjacent(kerbin, geostationary_transfer_orbit));
+ t.false(graph.areAdjacent(kerbin, mun_transfer));
- t.false(graph.areAdjacent(kerbin, geostationary_transfer_orbit));
- t.false(graph.areAdjacent(kerbin, mun_transfer));
+ t.end();
+ });
+
+ describe("walking a graph with three branches", function(t) {
+ t.plan(1);
+
+ // values taken from http://i.imgur.com/SqdzxzF.png
+ var earth = newNode('Earth');
+ var leo = newNode('Low Earth Orbit');
+ var geo_transfer = newNode('Geostationary Transfer');
+ var geostationary = newNode('Geostationary Orbit');
+ var moon_transfer = newNode('Moon Transfer');
+ var low_moon_orbit = newNode('Low Moon Orbit');
+ var earth_escape = newNode('Earth Escape');
+ var mars_transfer = newNode('Mars Transfer');
+
+ var low_earth_orbit = newEdge({ deltav: 9400, name: 'low_earth_orbit' });
+
+ var leo_geo_transfer = newEdge({ deltav: 2440, name: 'leo-geo_transfer' });
+ var geo_transfer_geo_orbit = newEdge({ deltav: 1470, name: 'geostationary_transfer-geostationary_orbit' });
+
+ var leo_moon_transfer = newEdge({ deltav: 3260, name: 'leo-moon_transfer' });
+ var moon_transfer_lmo = newEdge({ deltav: 680, name: 'moon_transfer-low_moon_orbit' });
+
+ var leo_earth_escape = newEdge({ deltav: 3210, name: 'leo-earth_escape' });
+
+ var earth_escape_mars_transfer = newEdge({ deltav: 390, name: 'earth_escape-mars_transfer' });
+
+ graph.addEdge(low_earth_orbit, earth, leo);
+
+ graph.addEdge(leo_geo_transfer, leo, geo_transfer);
+ graph.addEdge(geo_transfer_geo_orbit, geo_transfer, geostationary);
+
+ graph.addEdge(leo_moon_transfer, leo, moon_transfer);
+ graph.addEdge(moon_transfer_lmo, moon_transfer, low_moon_orbit);
+
+ graph.addEdge(leo_earth_escape, leo, earth_escape);
+ graph.addEdge(earth_escape_mars_transfer, earth_escape, mars_transfer);
+
+ var tot = graph.walk(earth, mars_transfer);
+ });
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