Created
September 10, 2015 03:25
-
-
Save hoorayimhelping/31e805e457f1e45e0080 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 | |
| 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