All files helpers.js

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
1x
 
 
 
 
 
 
 
1x
 
 
 
 
 
 
 
1x
 
 
 
 
 
1x
 
 
1x
 
 
 
 
 
 
 
 
1x
 
 
 
 
 
 
 
 
 
 
 
1x
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1x
 
 
 
 
 
 
 
 
 
 
 
 
 
 
export function makeOutgoingEdges(arr) {
    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) {
    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(edges) {
    const incomingEdges = makeIncomingEdges(edges);
    const startNodes = [];
    incomingEdges.forEach((value, key) => value.size === 0 && startNodes.push(key));
    return startNodes;
}
export function makeNodesHash(arr) {
    return new Map(arr.map((item, i) => [item, i]));
}
export function uniqueNodes(arr) {
    const res = new Set();
    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({ node, adjacencyMap, }) {
    const visited = new Set();
    const stack = [node];
    let cur = node;
    while (cur) {
        visited.add(cur);
        const neighbors = [...adjacencyMap.get(cur)];
        stack.push(...neighbors.filter((item) => !visited.has(item)).reverse());
        cur = stack.pop();
    }
    return visited;
}
export function getAdjacencyMapOfIndirectedGraph(edges) {
    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({ edges }) {
    const adjacencyMap = getAdjacencyMapOfIndirectedGraph(edges);
    const nodes = uniqueNodes(edges);
    const components = [];
    const visitedNodes = new Set();
    let currentNode = nodes[0];
    while (visitedNodes.size < nodes.length) {
        const visited = visitDepthFirst({ adjacencyMap, node: currentNode });
        components.push(visited);
        visited.forEach((node) => visitedNodes.add(node));
        currentNode = nodes.find((node) => !visitedNodes.has(node));
    }
    return components;
}