How to query using an acyclic graph with exclusive subsets

Question

Question in abstract terms:

I have a directed acyclic graph (DAG) that contains subsets of vertices that are exceptional in the query (the query results should contain only one element for each subset). When I request the structure of a graph, I would like to get a set of vertices that flow from a given vertex, just selecting one element from the known subsets of vertices in the graph.

Question in specific terms:

I have a DAG that stores my assemblies (vertices) and their dependencies (edges). Given an assembly or set of assemblies, I need to query to get a set of all involved assemblies and their dependencies. The hard part is that each assembly has several versions, and only one instance of the assembly can be loaded into the process. The dependencies for this assembly vary between different versions of the assembly.

Is there a name for this problem or group of problems? A standard algorithm that I can research to find a solution?

---

Possible areas of solution:

A transitive closure seems close to a good solution, but an element selected from a subset (assembly version) will change depending on the path traversed by the graph, possibly through several branches, so you will almost need to trace the path traversed by the graph to generate the transitive closure .

A graph database may help a little, but we want to avoid this path right now if we absolutely don't need it.

Answer 1

I think that the many vertices that flow from a given selection look confusing because there is actually a major optimization or satisfaction problem: given assembly A, you can satisfy its dependencies via B1 or B2 or B3, and each of these choices then has its own consequences.

If we consider this a problem of logical satisfaction, then we could consider the problem when assemblies come in only two versions, for example. A1 or A2. Then a sentence, such as (a or b or not c), is transferred to a top-level assembly that would require A1 or B1 or C2 - perhaps indirectly through X1, X2 and X3 - and the connection of sentences would be transferred to the upper top which required all top level assemblies. Therefore, I think that if you could effectively solve the general problem, you could effectively solve the 3-SAT, and then P = NP.

Curiously, if you have no restriction that you are only allowed one assembly of each type (A1 or A2 or A3, but more than one at a time), the problem can easily be translated into Horn sentences (Knuth Vol 4 section 7.1.1 P 57) for which the feasibility problem can be effectively solved. To do this, you work with the inversion of natural variables, so X1 means that A1 is not turned on. Then, if you consider the version of the Horn clause as a way to mitigate your problem, ignoring the restriction that no more than one version of each assembly can support, what you get is a mechanism to tell you that some version of assembly A1 is not may be in the solution, because X1 = not A1 is true in the core of the Horn solution and therefore true in every satisfying destination.