Traversing a recursive relations matrix in javascript

Question

There are lot of elements (expressed as checkboxes) with some different relations. For example:

• A needs B
• A needs C
• A can't be combined with D
• B can't be combined with E
• D needs E
• C needs F
• F can't be combined with G
• S can't be combined with B
• T can't be combined with D
• U needs S

Edit: 3 questions came up in the answers, that I want to define here:

• Q: What is the default, prohibited or needed? A: None of them. If there is no relation between 2 elements, they can act independently (as long there are no relations to a common element which would say otherwise).

• Q: If A prohibits B, does B then automatically prohibit A? A: Yes. The cat (A) says, you can't have it with a dog (B). Even if the dog doesn't care about the cat, you can't combine them, because the cat won't like it.

• Q: If A needs B, does B then automatically need A? A: No. If you want to read stackoverflow (A), you need the browser (B). But if you want to use the browser (B), you don't need stackoverflow (A).

Edit: I want to give a more simple example. Let's say, you can configure a car with checkboxes. There are some rules. For example, if you choose black paint, you can't choose white interior color (prohibited). If you choose leather seats, you can do this only in combination with seat heating (needed) and leather steering wheel (needed), but can't combine it with electric seat regulation (prohibited). Seat heating is not possible with white interior (prohibited), while a white roof needs white interior. Hence, even if not defined, you can't have white roof with seat heating (prohibited due to relations with a common element).

So if someone activates checkbox A, the checkboxes B and C need to be activated, too, while checkbox D needs to be disabled. Since A needs B and B can't be combined with E, checkbox E needs to be disabled, too. Since C needs F, F needs to be activated. And since F can't be combined with G, G needs to be deactivated as well.

And the other way round: If someone activates E, then B needs to be deactivated, since B can't be combined with E. But D doesn't need to be activated, because D needs E while E doesn't need D necessarily.

The big questions are now:

1. How to ideally express the relations in javascript
2. How to check all the relations with javascript if someone activates a checkbox.

The problem is the recursion. Every action leads to more actions which lead (possibly) to even more actions.

Following logic should apply for the example, that "A" is activated:

1. B will be activated
2. C will be activated
3. D will be disabled
4. E will be disabled
5. S will be disabled
6. T will be disabled
7. U will be disabled

Current definitions of the relations (can be changed):

var relations = {
  'A': {
    'B': 'needed',
    'C': 'needed',
    'D': 'prohibited'
  },
  'B': {
    'E': 'prohibited'
  },
  'D': {
    'E': 'needed'
  },
  'C': {
    'F': 'needed'
  },
  'F': {
    'G': 'prohibited'
  },
  'S': {
    'B': 'prohibited'
  },
  'T': {
    'D': 'prohibited'
  },
  'U': {
    'S': 'needed'
  }
}

Current theoretical approach:

Assumed a click on "A":

foreach (relations['A'] as related, relation) {
  if (relation === 'needed') {
    // take action
    activateRelated(related);
  } else if (relation === 'prohibited') {
    // take action
    disableRelated(related);
  }
}

But that's only the first iteration. Theoretically this could be a function which calls itself recursively after each action is taken. But on, let's say 300 Elements with a lot of relations, it loops infinite. Well, it works fine if one action is taken, one checkbox is activated. In a more realistic scenario, there are 30 to 50 % of the checkboxes active and the checking of the relations needs to go the whole way up and down.

Second problem is: if the user disables the checkbox A again, all relations need to be checked again - for all still active checkboxes, too.

Answer 1

Maybe this helps. If works with hints below the form.

Edit: Now with simple check for circular reference. Selected items which affect each other became deselected first.

Edit 2: Now with disabling/enabling of checkboxes.

var relation = [
        { name: 'A', needed: ['B', 'C'], prohibited: ['D'] },
        { name: 'B', needed: [], prohibited: ['E'] },
        { name: 'C', needed: ['F'], prohibited: [] },
        { name: 'D', needed: ['E'], prohibited: [] },
        { name: 'E', needed: [], prohibited: [] },
        { name: 'F', needed: [], prohibited: ['G'] },
        { name: 'G', needed: [], prohibited: [] },
        { name: 'S', needed: [], prohibited: ['B'] },
        { name: 'T', needed: [], prohibited: ['D'] },
        { name: 'U', needed: ['S'], prohibited: [] }
    ];

void function () {
    var div = document.createElement('div'),
        form = document.createElement('form'),
        loop;
    div.id = 'out';
    form.name = 'boxes';
    relation.forEach(function (a) {            
        var br = document.createElement('br'),
            input = document.createElement('input'),
            label = document.createElement('label');                
        input.type = 'checkbox';
        input.name = a.name;
        input.addEventListener('change', check);
        label.textContent = a.name;
        label.for = a.name;
        label.appendChild(input);
        label.appendChild(document.createTextNode((a.needed.length ? ' needed: ' + a.needed.join(', ') : '') + (a.prohibited.length ? ' prohibited: ' + a.prohibited.join(', ') : '')));
        form.appendChild(label);
        form.appendChild(br);
    });
    form.appendChild(div);
    document.body.appendChild(form);

    do {
        loop = false;
        relation.forEach(function (a) {
            a.needed.forEach(function (aa) {
                relation.forEach(function (b) {
                    b.prohibited.forEach(function (bb) {
                        if (aa === bb) {
                            if (!~a.prohibited.indexOf(b.name)) {
                                a.prohibited.push(b.name);
                                loop = true;
                            }
                            if (!~b.prohibited.indexOf(a.name)) {
                                b.prohibited.push(a.name);
                                loop = true;
                            }
                        }
                    });
                });
            });
        });
    } while (loop);
}();

function check() {
    function getBox(l) { return document.boxes[l].checked; }
    function setBox(l, v) { return document.boxes[l].checked = v; }
    function setBoxDisabled(l, v) { return document.boxes[l].disabled = v; }

    var disabled, msg, loop;

    do {
        disabled = [];
        msg = [];
        loop = false;
        relation.forEach(function (a) {
            if (getBox(a.name)) {
                a.needed.forEach(function (b) {
                    if (!getBox(b)) {
                        msg.push('With ' + a.name + ', ' + b + ' is required');
                        setBox(b, true);
                        loop = true;
                    }
                });
                a.prohibited.forEach(function (b) {
                    if (getBox(b)) {
                        msg.push('With ' + a.name + ', ' + b + ' is prohibited');
                        setBox(b, false);
                        loop = true;
                    }
                    setBoxDisabled(b, true);
                    !~disabled.indexOf(b) && disabled.push(b);
                });
            }
        });
        relation.forEach(function (a) {
            if (!getBox(a.name)) {
                a.prohibited.forEach(function (b) {
                    !~disabled.indexOf(b) && setBoxDisabled(b, false);
                });
            }
        });
        msg.length && out(msg.join('<br>') + '<hr>');
    } while (loop);
}

function out(s) {
    var node = document.createElement('div');
    node.innerHTML = s + '<br>';
    document.getElementById('out').appendChild(node);
}

Bonus: A slightly difference approach, featuring recursive style with proper change messages.

var relation = [
        { name: 'A', needed: ['B', 'C'], prohibited: ['D'] },
        { name: 'B', needed: [], prohibited: ['E'] },
        { name: 'C', needed: ['F'], prohibited: [] },
        { name: 'D', needed: ['E'], prohibited: [] },
        { name: 'E', needed: [], prohibited: [] },
        { name: 'F', needed: [], prohibited: ['G'] },
        { name: 'G', needed: [], prohibited: [] },
        { name: 'S', needed: [], prohibited: ['B'] },
        { name: 'T', needed: [], prohibited: ['D'] },
        { name: 'U', needed: ['S'], prohibited: [] }
    ], object = {};

void function () {
    var div = document.createElement('div'),
        form = document.createElement('form');
    div.id = 'out';
    form.name = 'boxes';

    relation.forEach(function (a) {
        var br = document.createElement('br'),
            input = document.createElement('input'),
            label = document.createElement('label');

        input.type = 'checkbox';
        input.name = a.name;
        input.addEventListener('change', function (l) { return function () { checkBox(l); } }(a.name));
        //input.addEventListener('change', function () { checkBox(a.name); });
        label.textContent = a.name;
        label.for = a.name;
        label.appendChild(input);
        label.appendChild(document.createTextNode((a.needed.length ? ' needed: ' + a.needed.join(', ') : '') + (a.prohibited.length ? ' prohibited: ' + a.prohibited.join(', ') : '')));
        form.appendChild(label);
        form.appendChild(br);
        object[a.name] = a;
    });
    form.appendChild(div);
    document.body.appendChild(form);
}();

function checkBox(l) {
    function getBox(l) { return document.boxes[l].checked; }
    function setBox(l, v, x) {
        if (document.boxes[l].checked !== v) {
            v ? out('With ' + x + ' option ' + l + ' is necessary.') : out('Without ' + x + ' option ' + l + ' is not valid.');
            document.boxes[l].checked = v;
        }
    }
    function setBoxDisabled(l, v, x) {
        if (document.boxes[l].disabled !== v) {
            v ? out('With ' + x + ' option ' + l + ' is not available.') : out('Without ' + x + ' option ' + l + ' is now available.');
            document.boxes[l].disabled = v;
        }
    }

    if (getBox(l)) {
        object[l].prohibited.forEach(function (p) {
            setBox(p, false, l);
            setBoxDisabled(p, true, l);
            relation.forEach(function (a) {
                if (~a.needed.indexOf(p)) {
                    setBox(a.name, false, p);
                    setBoxDisabled(a.name, true, p);
                    checkBox(a.name);
                }
            });
            checkBox(p);
        });
        object[l].needed.forEach(function (p) {
            setBox(p, true, l);
            checkBox(p);
        });
    } else {
        var allProhibited = [];
        relation.forEach(function (a) {
            if (getBox(a.name)) {
                a.prohibited.forEach(function (b) {
                    !~allProhibited.indexOf(b) && allProhibited.push(b);
                });
            }
        });
        object[l].prohibited.forEach(function (p) {
            if (!~allProhibited.indexOf(p)) {
                setBox(p, false, l);
                setBoxDisabled(p, false, l);
            }
            relation.forEach(function (a) {
                if (~a.needed.indexOf(p)) {
                    setBox(a.name, false, p);
                    setBoxDisabled(a.name, false, p);
                    checkBox(a.name);
                }
            });
            checkBox(p);
        });
        relation.forEach(function (a) {
            if (~a.needed.indexOf(l)) {
                setBox(a.name, false, l);
                checkBox(a.name);
            }
        });
    }
}

function out(s) {
    var node = document.createElement('div');
    node.innerHTML = s + '<br>';
    document.getElementById('out').appendChild(node);
}

Answer 2

Edited: requirements were refined

A simple recursion won't do

var relations = {
  'A': {
    'B': 'needed',
    'C': 'needed',
    'D': 'prohibited'
  },
  'B': {
    'E': 'prohibited'
  },
  'D': {
    'E': 'needed'
  },
  'E':{/* added for simplicity */},
  'C': {
    'F': 'needed'
  },
  'F': {
    'G': 'prohibited'
  }
};
var tmp = {};
function checkRelations(start) {
  for (var relation in relations[start]) {
    if (!tmp.hasOwnProperty(relation)) {
       tmp[relation] = {};
    }
    if (relations[start][relation] === 'needed') {
      tmp[relation][start] = 'needed';
    } else if (relations[start][relation] === 'prohibited') {
      tmp[relation][start] = 'prohibited';
    }
    checkRelations(relation);
  }
}
function run(obj) {
  for (var e in obj) {
    checkRelations(e);
  }
}

run(relations);
JSON.stringify(tmp);

will get you this result:

{
  'B': {
    'A': 'needed',
    'S': 'prohibited'
  },
  'E': {
    'B': 'prohibited',
    'D': 'needed'
  },
  'C': {
    'A': 'needed'
  },
  'F': {
    'C': 'needed'
  },
  'G': {
    'F': 'prohibited'
  },
  'D': {
    'A': 'prohibited',
    'T': 'prohibited'
  },
  'S': {
    'U': 'needed'
  }
}

As you can see from the very first entry B: your database is under-defined. What happens to every element that is not defined? What is the default if something is not defined, is it prohibited or 'needed'? If 'A' needs 'B' does that imply that 'B' needs 'A'?

Once you have defined that you can fill the first layer of the database (automatically) and build a tree (dito automatically) based on that if you want and safe a lot of processing (O(n^2)) by spending a lot of memory (O(n^2)).

All under the assumption that the whole thing is consistent and has no infinity loop anywhere!

With the default value set to 'meh' the first round is

function checkRelations(start) {
  for (var relation in relations[start]) {
    if (!relations.hasOwnProperty(relation)) {
      relations[relation] = {
      };
    }
    if (relations[start][relation] === 'needed') {
      relations[relation][start] = 'meh';
    } else if (relations[start][relation] === 'prohibited') {
      relations[relation][start] = 'prohibited';
    }
    for (var r in relations) {
      if (!relations[relation].hasOwnProperty(r) && relation != r) {
        relations[relation][r] = 'meh';
      }
    }
  }
}
function run(obj) {
  for (var e in obj) {
    // fill database up
    checkRelations(e);
  }
}
run(relations);
JSON.stringify(relations)
{
  'A': {
    'B': 'needed',
    'C': 'needed',
    'D': 'prohibited',
    'E': 'meh',
    'F': 'meh',
    'S': 'meh',
    'T': 'meh',
    'U': 'meh',
    'G': 'meh'
  },
  'B': {
    'E': 'prohibited',
    'A': 'meh',
    'D': 'meh',
    'C': 'meh',
    'F': 'meh',
    'S': 'prohibited',
    'T': 'meh',
    'U': 'meh',
    'G': 'meh'
  },
  'E': {
    'B': 'prohibited',
    'A': 'meh',
    'D': 'meh',
    'C': 'meh',
    'F': 'meh',
    'S': 'meh',
    'T': 'meh',
    'U': 'meh',
    'G': 'meh'
  },
  'D': {
    'E': 'needed',
    'A': 'prohibited',
    'B': 'meh',
    'C': 'meh',
    'F': 'meh',
    'S': 'meh',
    'T': 'prohibited',
    'U': 'meh',
    'G': 'meh'
  },
  'C': {
    'F': 'needed',
    'A': 'meh',
    'B': 'meh',
    'E': 'meh',
    'D': 'meh',
    'S': 'meh',
    'T': 'meh',
    'U': 'meh',
    'G': 'meh'
  },
  'F': {
    'G': 'prohibited',
    'A': 'meh',
    'B': 'meh',
    'E': 'meh',
    'D': 'meh',
    'C': 'meh',
    'S': 'meh',
    'T': 'meh',
    'U': 'meh'
  },
  'S': {
    'B': 'prohibited',
    'A': 'meh',
    'E': 'meh',
    'D': 'meh',
    'C': 'meh',
    'F': 'meh',
    'T': 'meh',
    'U': 'meh',
    'G': 'meh'
  },
  'T': {
    'D': 'prohibited',
    'A': 'meh',
    'B': 'meh',
    'E': 'meh',
    'C': 'meh',
    'F': 'meh',
    'S': 'meh',
    'U': 'meh',
    'G': 'meh'
  },
  'U': {
    'S': 'needed',
    'A': 'meh',
    'B': 'meh',
    'E': 'meh',
    'D': 'meh',
    'C': 'meh',
    'F': 'meh',
    'T': 'meh',
    'G': 'meh'
  },
  'G': {
    'F': 'prohibited',
    'A': 'meh',
    'B': 'meh',
    'E': 'meh',
    'D': 'meh',
    'C': 'meh',
    'S': 'meh',
    'T': 'meh',
    'U': 'meh'
  }
}

That was already expensive. You can expand the tree but I would stop here and build the tree on-the-fly by following the path 'needed'. You should be able to use the first recursive method to do it and recurse if you found a 'needed' if the default is 'prohibited'.

Example:

A - B(n) - C(n) - D(p)        
    |       |
    E(p)   F(n)
    ||      |
    S(p)   G(p)

(one bar is a branch, two bars are in a leaf)

Handle the 'meh'parts depending on the defaults, of course. You can even skip the construction of the 'meh' entries completely if the default is 'prohibited' which leaves you with the 'needed' entries only.

The rest would be

{
  'A': {
    'B': 'needed',
    'C': 'needed'
  },
  'B': {
    'nothing':0
  },
  'E': {
    'nothing':0
  },
  'D': {
    'E': 'needed'
  },
  'C': {
    'F': 'needed'
  },
  'F': {
    'nothing':0
  },
  'S': {
    'nothing':0
  },
  'T': {
    'nothing':0
  },
  'U': {
    'S': 'needed'
  },
  'G': {
    'nothing':0
  }
}

And reduced to the bare minimum:

{
  'A': {
    'B': 'needed',
    'C': 'needed'
  }
  'D': {
    'E': 'needed'
  },
  'C': {
    'F': 'needed'
  }
  'U': {
    'S': 'needed'
  }
}

The full algorithm: set all entries to 'prohibited' if needed and travese the little DB listed above which has been made by the following little script

function checkRelations(start) {
  for (var relation in relations[start]) {
    if (relations[start][relation] === 'prohibited') {
      delete relations[start][relation];
    }
  }
}
function isEmpty(obj) {
  for(var p in obj) {
    if(obj.hasOwnProperty(p)){
      return false;
    }
  }
  return true;
}
function run(obj) {
  for (var e in obj) {
    // fill database up
    checkRelations(e);
    // delete empty entries
    if(isEmpty(relations[e])){
      delete relations[e];
    }
  }
}

The function to traverse the last one:

function followPath(start){
  for (var relation in reduced[start]) {
    console.log(relation + " is needed")
    if (reduced.hasOwnProperty(relation)) {
      console.log( relation + " is needed, follow path")
      followPath(relation);
    }
  }

}

Ah, to late. Again ;-)

But at least it is a bit simpler (and faster, if I count the loops correctly) than I thought in the first place.