4
$\begingroup$

This is similar to Is there such a thing as an "or" case in a dependency graph?

I am trying to represent a dependency graph where the dependencies for an individual node may be a general boolean function of other nodes.

For example, node A may be reachable from node B or node C.

I can't see how to represent this with a DAG. Is there way to represent general boolean dependencies in a DAG? If there isn't, what other sort of structure should I use?

$\endgroup$
  • $\begingroup$ What is the purpose of the DAG representation? $\endgroup$ – reinierpost Dec 13 '18 at 19:27
1
$\begingroup$

Sorry for the crappy mspaint, but you could make an intermediate layer where the nodes in the middle represent each of the combinations of (A,B), like in a truth table:

A or B dependency with intermediate layer

~ABB~

$\endgroup$
  • $\begingroup$ all the arcs in a dependency graph have to be activated to make a node available to process. In your drawing, you have 3 in-arcs to the AorB node, and you are implicitly OR-ing all those arcs together, whereas the dependency graph requires that all 3 arcs are in place. Your AorB node, as draw, requires both A and B to be processed first. $\endgroup$ – JimN Dec 14 '17 at 22:35
  • 2
    $\begingroup$ Ok, pretend I drew all the arrows in the opposite direction. I wasn't going specifically for a dependency graph. The question more generally asked for a DAG. $\endgroup$ – Cody Dec 14 '17 at 23:25
1
$\begingroup$

It's possible to represent a general boolean function as a directed acyclic graph. Wikipedia has examples of this on the binary decision diagram and propositional directed acyclic graph pages.

In the case of the PDAG, the up triangle represents AND, the down triangle OR, and the diamond represents NOT. The PDAG seems to be the closest to an AND/OR dependency graph, with the topmost element only having it's requirements satisfied if the function would yield a 1.

Propositional directed acyclic graph

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.