Created
September 21, 2020 12:45
-
-
Save mavnn/1357721f6800b15231a64a4b62ce037f to your computer and use it in GitHub Desktop.
Mini-mini-graph library for JS
This file contains 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
const create = () => { | |
return { nodes: new Set(), edges: new Set() } | |
} | |
const addNode = (graph, node) => { | |
graph.nodes.add(node) | |
} | |
const addEdge = (graph, [node1, node2]) => { | |
if (graph.nodes.has(node1) && graph.nodes.has(node2)) { | |
graph.edges.add([node1, node2]) | |
} else { | |
throw new Error("You can't add an edge between nodes that aren't in the graph") | |
} | |
} | |
const getConnected = (graph, node) => { | |
const connected = new Set([node]) | |
graph.edges.forEach(([node1, node2]) => { | |
if (node1 === node || node2 === node) { | |
connected.add(node1 === node ? node2 : node1) | |
} | |
}) | |
return connected | |
} | |
const equalSets = (set, otherSet) => { | |
if (set.size !== otherSet.size) return false | |
for (let item of set) if (!otherSet.has(item)) return false | |
return true | |
} | |
const recursiveGetConnected = (graph, node, connected = new Set(), visited = new Set()) => { | |
connected.add(node) | |
visited.add(node) | |
getConnected(graph, node).forEach(nextNode => { | |
if (!visited.has(nextNode)) { | |
recursiveGetConnected(graph, nextNode, connected, visited) | |
} | |
}) | |
return connected | |
} | |
const cluster = graph => { | |
const clusters = new Set() | |
graph.nodes.forEach(n => clusters.add(recursiveGetConnected(graph, n))) | |
const uniqClusters = [] | |
clusters.forEach(cluster1 => { | |
if (uniqClusters.every(cluster2 => !equalSets(cluster1, cluster2))) { | |
uniqClusters.push(cluster1) | |
} | |
}) | |
return new Set(uniqClusters) | |
} | |
const test = create() | |
addNode(test, "one") | |
addNode(test, "two") | |
addNode(test, "three") | |
addNode(test, "four") | |
addEdge(test, ["one", "two"]) | |
addEdge(test, ["three", "one"]) | |
console.log(cluster(test)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment