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