Prims algo in JS

prims.js

// David's prims (JavaScript)
// rough hacked together version !
// 
// (c) 2019 daXXog <>< + + + ><>
// ------------------------------------------

//  [[][][]].flatten prototype
//- https://stackoverflow.com/a/19191529
Array.prototype.flatten = function() {
	var arr  = this,
    	arr2 = [];

	arr2 = (arr2.concat.apply(arr2, arr)).filter(Boolean);

	return arr2;
};

// data structure main
[
	{
		points: ['A', 'D'],
		weight: 1,
		marked: false
	},
	{
		points: ['A', 'B'],
		weight: 10,
		marked: false
	}
];

// data structure links
/*{
	'A': ['D', 'B']
};*/

var Graph = function() {
	this._a = []; // the main data structure
	this._l = {}; // the "links"
	this._m = []; // the marks (in order)
};

Graph.prototype.addEdge = function(from, to, weight) {
	this._a.push({
		points: [from, to],
		weight: weight,
		marked: false
	});

	if(Array.isArray(this._l[from]) === false) {
		this._l[from] = [];
	}

	if(Array.isArray(this._l[to]) === false) {
		this._l[to] = [];
	}

	this._l[from].push(to);
	this._l[to].push(from);
};

Graph.prototype.findEdge = function(from, to) {
	var found = false,
		what;

	this._a.forEach(function(v) {
		if(!found) {
			found = ((v.points[0] === from) && (v.points[1] === to) ||
		      		 (v.points[1] === from) && (v.points[0] === to));

			if(found) {
				what = v;
			}
		}
	});

	return what;
};

Graph.prototype.markEdge = function(from, to, mark) {
	var found = false,
		what;

	this._a = this._a.map(function(v) {
		if(!found) {
			found = ((v.points[0] === from) && (v.points[1] === to) ||
		      		 (v.points[1] === from) && (v.points[0] === to));

			if(found) {
				v.marked = mark;
				what = v;
			}
		}

		return v;
	});

	if(mark === true) {
		this._m.push({
			from: from,
			to: to
		});
	}

	return what;
};

Graph.prototype.findConnected = function(point) {
	var that = this;

	return this._l[point].map(function(v) {
		return that.findEdge(point, v);
	});
};

Graph.prototype.findConnectedMarks = function(points, mark) {
	var that = this,
		_r = [];

	points.forEach(function(point) {
		that._l[point].map(function(v) {
			var edge = that.findEdge(point, v);

			if(edge.marked === mark) {
				return edge;
			}
		}).filter(function (el) {
			return el != null;
		}).forEach(function(v) {
			_r.push(v);
		});
	});

	return _r;
};

Graph.prototype.findConnectedMark = function(point, mark) {
	return this.findConnectedMarks([point], mark);
};

Graph.prototype.findMark = function(mark) {
	return this._a.map(function(v) {
		if(v.marked === mark) {
			return v.points;
		}
	}).filter(function (el) {
			return el != null;
	}).flatten();
};

Graph.prototype.findMarkOther = function() {
	var that = this;

	return this.findMark(false).map(function(v) {
		return (that.findMark(true).indexOf(v) === -1) ? v : false;
	}).filter(function (el) {
			return el != false;
	});
};

Graph.prototype.badMark = function(smallest) {
	var mo = this.findMarkOther();

	return (mo.indexOf(smallest.points[0]) === -1) && (mo.indexOf(smallest.points[1]) === -1);
};

Graph.smallestFromPointList = function(points) { //points is a data structure
	var smallest = Infinity,
		smallObj;

	points.forEach(function(point) {
		if(point.weight < smallest) {
			smallest = point.weight;
			smallObj = point;
		}
	});

	return smallObj;
};

var Prims = function(graph, start) {
	this.graph = graph;
	this.start = start;

	this._run();
};

Prims.prototype._run = function() {
	var that = this;

	//console.log(this.graph);
	//console.log(this.start);
	var connected = this.graph.findConnectedMark(this.start, false),	
		smallest = Graph.smallestFromPointList(connected);

	this.graph.markEdge(smallest.points[0], smallest.points[1], true);

	var i = 0;
	while(true) {
		connected = this.graph.findConnectedMarks(this.graph.findMark(true), false);
		smallest = Graph.smallestFromPointList(connected);

		//console.log(i, 'DBG', this.graph.findMark(true));
		//console.log(i, 'DBG3', this.graph.findMarkOther());
		//console.log(i, 'DBG4', this.graph.badMark(smallest));

		if(this.graph.badMark(smallest)) {
			connected = this.graph.findConnectedMarks(this.graph.findMarkOther(), false);
			smallest = Graph.smallestFromPointList(connected);
		}

		if(typeof smallest === 'object') {
			this.graph.markEdge(smallest.points[0], smallest.points[1], true);
		} else {
			break;
		}

		//console.log(i, smallest);

		i++;
	}

	//console.log(this.graph._m);
};


// here be the main() code -->
var graphA = new Graph();

/*graphA.addEdge('A', 'D', 1);
graphA.addEdge('A', 'B', 10);
graphA.addEdge('A', 'C', 9);
graphA.addEdge('B', 'C', 8);
graphA.addEdge('D', 'C', 14);
graphA.addEdge('C', 'E', 4);
graphA.addEdge('C', 'F', 3);
graphA.addEdge('B', 'E', 3);
graphA.addEdge('E', 'F', 12);
graphA.addEdge('D', 'F', 4);
graphA.addEdge('F', 'Z', 17);
graphA.addEdge('E', 'Z', 8);*/

graphA.addEdge('A', 'B', 7);
graphA.addEdge('A', 'C', 2);
graphA.addEdge('A', 'D', 8);
graphA.addEdge('B', 'D', 4);
graphA.addEdge('C', 'E', 9);
graphA.addEdge('C', 'D', 4);
graphA.addEdge('D', 'E', 3);
graphA.addEdge('D', 'F', 11);
graphA.addEdge('E', 'F', 4);
graphA.addEdge('D', 'G', 13);
graphA.addEdge('F', 'G', 12);
graphA.addEdge('G', 'H', 8);
graphA.addEdge('G', 'J', 3);
graphA.addEdge('G', 'Z', 7);
graphA.addEdge('Z', 'J', 5);
graphA.addEdge('J', 'H', 5);

new Prims(graphA, 'A');
console.log(graphA);
console.log(JSON.stringify(graphA));