Splitting a 2-Dimensional Array-CodePudding

I have this 2 dimensional array of tasks

const graph = [
    ['tie your shoes', 'put on your shoes'],
    ['put on your jacket', 'put on your shirt'],
    ['put on your shoes', 'put on your shorts'],
    ['put on your jacket', 'put on your shorts'],
    ['buy eggs from store', 'cook eggs'],
    ['heat up skillet', 'cook eggs']
]

I need to split up this graph into two separate arrays if the they have no association to each other. (i.e., putting shoes on and cooking eggs have no association/relation within the graph)

Each array within the graph is an association of tasks. An association can be traced between two tasks if they can be traced back to a single common task - putting on your jacket can be traced back to putting on your socks

The result should look like this

const graph_1 = [
    ['tie your shoes', 'put on your shoes'],
    ['put on your jacket', 'put on your shirt'],
    ['put on your shoes', 'put on your shorts'],
    ['put on your jacket', 'put on your shorts']
]

const graph_2 = [
    ['buy eggs from store', 'cook eggs'],
    ['cook eggs', 'heat up skillet']
]

I'm not worried about sorting them at the moment - only concerned with splitting them up

CodePudding user response：

You could use a combo of loops to check against an array that contains keywords.

const graph = [
    ['tie your shoes', 'put on your shoes'],
    ['put on your jacket', 'put on your shirt'],
    ['put on your shoes', 'put on your shorts'],
    ['put on your jacket', 'put on your shorts'],
    ['buy eggs from store', 'cook eggs'],
    ['heat up skillet', 'cook eggs']
]

// Keywords
const clothes = ['shoes', 'jacket', 'shorts']
const foods = ['eggs', 'heat', 'skillet']

// Creating graph 1
const graph_1 = graph.filter(array => {
  return array.reduce((arr, str) => {
    clothes.forEach(item => {
      if (str.includes(item)) {
        arr.push(str)
      }
    })
    return arr
  }, []).length
})

// Creating graph 2
const graph_2 = graph.filter(array => {
  return array.reduce((arr, str) => {
    foods.forEach(item => {
      if (str.includes(item)) {
        arr.push(str)
      }
    })
    return arr
  }, []).length
})

console.log(graph_1)
console.log(graph_2)

CodePudding user response：

This is finding the connected components of the graph problem. In Python you could use Networkx for this purpose. The answer in this post might be helpful to you: https://stackoverflow.com/a/61537932/18534805

Here is also another post and solution in javascript: https://stackoverflow.com/a/21901612/18534805