recursive two-color / bipartite graph solution

bipartite-2-color-recursive.js

/* TWO-COLOR PROBLEM,
i.e., whether or not a given undirected, connected graph is bipartite:
https://en.wikipedia.org/wiki/Bipartite_graph */

/* complexity [of non-recursive Fullstack Academy solution] ? O(n*n) i believe, O(n*n+n) technically */

/* can we do better ? definitely */

/* given a graph */
let zero = {num: 0}, 
	one = {num: 1}, 
	two = {num: 2}, 
	three = {num: 3}, 
	four = {num: 4}, 
	five = {num: 5}, 
	six = {num: 6}, 
	seven = {num: 7}
	// ...etc, etc
	
	// just an example
	edges = [
		[zero, five],
		[zero, six],
		[zero, seven],
		[one, five],
		[one, six],
		[one, seven],
		[two, five],
		[two, six],
		[two, seven],
		[three, five],
		[three, six],
		[three, seven],
		[four, five],
		[four, six],
		[four, seven]
		[zero, one]
	]

/* turn this data into a Map;
this allows us to store nodes as keys and arrays of linked nodes as values */
let graphMap = edges.reduce((graphMap, edge) => {
	for (let i = 0; i < 2; i++) {
		if (graphMap.has(edge[i])) {
			if (graphMap.get(edge[i]).indexOf(edge[i]) < 0) graphMap.get(edge[i]).push(edge[Math.abs(i-1)])
		} else {
			graphMap.set(edge[i], [edge[Math.abs(i-1)]])
		}
	}
	return graphMap
}, new Map())

// in this example, graphMap will be:

// [
//  zero: [five, six, seven],
//  one: [five, six, seven],
//  two: [five, six, seven],
//  three: [five, six, seven],
//  four: [five, six, seven],
//  five: [five, six, seven],
//  six: [five, six, seven],
//  seven: [five, six, seven]
// ]

// now we want to recursively traverse the graph with our bipartite coloring scheme

/* as soon as we reach a point where we can't color in a bipartite manner,
we can set our result to 'false',which breaks us out of our iteration */

// otherwise, we will return true when our recursion ends

const bipartiteChecker = (graph, start) => {
	let currentEdges = graph.get(start), result = true
		start.color = start.color || 'blue'
	
	for (let i = 0; i < currentEdges.length; i++) {
		if (!result) break // we've got two connected vertices with the same color; break out of iteration
		if (start.color === currentEdges[i].color) result = false
		if (!currentEdges[i].color) {
			currentEdges[i].color = start.color === 'red' ? 'blue' : 'red'
			bipartiteChecker(graph, currentEdges[i])
		}
	}
	
	return result
}

// complexity ? well, still pretty bad, i guess, but this solution is more interesting to me

// i think it's O(m*m*n), where m is the number of edges and n is the number of vertices

/* but probably the step to turn the graph data into a map (O(m) on its own) is not strictly necessary.
but i like working with maps. */