Skip to content

Instantly share code, notes, and snippets.

@peterquiel
Last active July 14, 2016 16:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save peterquiel/12e3eb938ee540cc4c5d22e2e4340503 to your computer and use it in GitHub Desktop.
Save peterquiel/12e3eb938ee540cc4c5d22e2e4340503 to your computer and use it in GitHub Desktop.
Map Reduce Alg to calculate the distance between nodes in mongo db
var map = function() {
if (this._id == 1) {
emit(this._id, { distance: 0, name:'black' , childs: this.includes });
this.includes.forEach(function(it) {
emit(it, { distance: 1, name: 'gray', childs: [] })
});
} else {
emit(this._id, { distance: -1, name: 'white', childs: this.includes });
}
};
var reduce = function(key, values) {
for (var idx in values) {
if (values[idx].name === 'black') {
return values[idx];
}
}
var newEntry = {
distance: 100000,
name: 'black',
childs: []
};
values.forEach(function(value) {
if (value.name === 'gray' && value.distance < newEntry.distance) {
newEntry.distance = value.distance;
} else if (value.name === 'white') {
newEntry.childs = value.childs;
}
});
for(var idx in newEntry.childs) {
emit(newEntry.childs[idx], { distance: newEntry.distance + 1, name: 'gray' , childs: [] });
}
return newEntry;
};
var finalize = function(key, value) {
return {
name: value.name,
distance: value.distance
}
};
var mongo = require('mongodb').MongoClient
var executeReduce = function(count) {
mongo.connect('mongodb://localhost:27017/database', function(err, db) {
var col = db.collection('graphtest');
col.remove();
for(var i = 1; i <= count; i++ ) {
col.insert({
_id : i,
includes : [i-1]
//includes : [Math.ceil(Math.random() * count), Math.ceil(Math.random() * count)]
});
}
col.insert({
_id : count,
includes : [1, count, count]
});
setTimeout( function() {
col.mapReduce(map, reduce, {
out: 'graph_test_reduce',
finalize: finalize
}).then(
function(value) {
db.collection('graph_test_reduce').aggregate([{
$match: {
'value.distance': {
$gt: -1
}
}
}], function(err, result) {
console.log(result);
db.close();
});
},
function(err) {}
);
}, 2000);
});
};
executeReduce(10);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment