Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | 1x 20x 148120x 148120x 148120x 148120x 20x 20x 1x 1x 15x 296111x 296111x 296111x 296111x 15x 15x 1x 1x 7x 7x 7x 7x 7x 7x 7x 7x 1x 1x 26x 26x 1x 1x 31x 31x 325796x 325796x 325796x 325796x 31x 31x 1x 1x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 177722x 177722x 177722x 177722x 177722x 177722x 20x 20x 1x 1x 14x 177687x 177687x 177687x 177687x 355374x 355374x 295289x 355374x 60085x 60085x 177687x 177687x 14x 14x 1x 1x 11x 11x 11x 11x 11x 11x 11x 17x 17x 17x 17x 17x 11x 11x 11x | export function makeOutgoingEdges(arr: unknown[][]) {
return arr.reduce((edges, [from, to]) => {
edges.has(from) || edges.set(from, new Set());
edges.has(to) || edges.set(to, new Set());
edges.get(from).add(to);
return edges;
}, new Map());
}
export function makeIncomingEdges(arr: unknown[][]) {
return arr.reduce((edges, [from, to]) => {
edges.has(from) || edges.set(from, new Set());
edges.has(to) || edges.set(to, new Set());
edges.get(to).add(from);
return edges;
}, new Map());
}
export function getStartNodes<T>(edges: T[][]) {
const incomingEdges = makeIncomingEdges(edges);
const startNodes: T[] = [];
incomingEdges.forEach(
(value, key) => value.size === 0 && startNodes.push(key)
);
return startNodes;
}
export function makeNodesHash(arr: unknown[]) {
return new Map(arr.map((item, i) => [item, i]));
}
export function uniqueNodes<T>(arr: T[][]) {
const res = new Set<T>();
for (let i = 0, len = arr.length; i < len; i++) {
const edge = arr[i];
res.add(edge[0]);
res.add(edge[1]);
}
return [...res];
}
export function visitDepthFirst<T>({
node,
adjacencyMap,
}: {
node: T | undefined;
adjacencyMap: Map<T, T[]>;
}): Set<T> {
const visited = new Set<T>();
const stack = [node];
let cur: T | undefined = node;
while (cur) {
visited.add(cur);
const next: T[] = adjacencyMap.get(cur)? adjacencyMap.get(cur) as T[] : []
const neighbors = [...next];
stack.push(...neighbors.filter((item) => !visited.has(item)).reverse());
cur = stack.pop();
}
return visited;
}
export function getAdjacencyMapOfIndirectedGraph(edges: unknown[][]) {
return edges.reduce((acc, [from, to]) => {
[
[from, to],
[to, from],
].forEach(([node, neighbor]) => {
const neighbors = acc.get(node);
if (neighbors) {
neighbors.add(neighbor);
} else {
acc.set(node, new Set([neighbor]));
}
});
return acc;
}, new Map());
}
export function groupByComponents<T>({ edges }: { edges: T[][] }): Array<Set<T>> {
const adjacencyMap: Map<any, any> = getAdjacencyMapOfIndirectedGraph(edges);
const nodes = uniqueNodes(edges);
const components: Array<Set<T>> = [];
const visitedNodes = new Set();
let currentNode: T | undefined = nodes[0];
while (visitedNodes.size < nodes.length) {
const visited = visitDepthFirst<T>({ adjacencyMap, node: currentNode });
components.push(visited);
visited.forEach((node) => visitedNodes.add(node));
currentNode = nodes.find((node) => !visitedNodes.has(node));
}
return components;
}
|