git ssb

1
/**
2
 * Implements a parrilizable DFS check for graph connictivity given a set of nodes
3
 * and a root node. Stating for the set of node to check this does a DFS and
4
 * will return a set a nodes if any that is not connected to the root node.
5
 * @param {object} graph - an instance of ipld-graph-builder
6
 * @param {object} state - the state containing all of the containers to search
7
 * @param {string} root - the root id
8
 * @param {Set} nodes - a set of nodes to start searching from
9
 */
10
module.exports = async function DFSchecker (tree, nodes, checkFn) {
11
  const checkedNodesSet = new Set()
12
  let hasRootSet = new Set()
13
  const promises = []
14
15
  for (const id of nodes) {
16
    // create a set for each of the starting nodes to track the nodes the DFS has
17
    // has traversed
18
    const checkedNodes = new Set()
19
    checkedNodesSet.add(checkedNodes)
20
    promises.push(check(id, checkedNodes))
21
  }
22
23
  // wait for all the search to complete
24
  await Promise.all(promises)
25
  // remove the set of nodes that are connected to the root
26
  checkedNodesSet.delete(hasRootSet)
27
  let unLinkedNodesArray = []
28
29
  // combine the unconnected sets into a single array
30
  for (const set of checkedNodesSet) {
31
    unLinkedNodesArray = unLinkedNodesArray.concat([...set])
32
  }
33
  return unLinkedNodesArray
34
35
  // does the DFS starting with a single node ID
36
  async function check (id, checkedNodes) {
37
    if (!checkedNodesSet.has(checkedNodes) || // check if this DFS is still searching
38
        checkedNodes.has(id) ||  // check if this DFS has alread seen the node
39
        hasRootSet === checkedNodes) { // check that this DFS has alread found the root node
40
      return
41
    }
42
43
    // check if any of the the other DFSs have seen this node and if so merge
44
    // the sets and stop searching
45
    for (const set of checkedNodesSet) {
46
      if (set.has(id)) {
47
        checkedNodes.forEach(id => set.add(id))
48
        checkedNodesSet.delete(checkedNodes)
49
        return
50
      }
51
    }
52
53
    // mark the node 'checked'
54
    checkedNodes.add(id)
55
56
    // check to see if we are at the root
57
    if (checkFn(id)) {
58
      hasRootSet = checkedNodes
59
      return
60
    }
61
62
    const node = await tree.get(id)
63
    const promises = []
64
    // iterate through the nodes ports and recursivly check them
65
    for (const name in node.ports) {
66
      const port = node.ports[name]
67
      promises.push(check(port.destId, checkedNodes))
68
    }
69
    return Promise.all(promises)
70
  }
71
}
72