(Set of) List of sets (Cartesian product(s)) from graph corresponding to set of lists

Question

The set of lists (A):

{[a,b,d,f],
 [a,c,d,f],
 [a,b,e,f],
 [a,c,e,f]}

where a, b, c, d, e and f are items (not necessarily characters in a word), can be factored as a directed acyclic graph (DAG, B, all edges point from left -> to right):

  b-->d
 / \ / \
a   X   f
 \ / \ /
  c-->e

or as the Cartesian product of 4 sets of items (C, termed axes):

{a} * {b,c} * {d, e} * {f}

Guava has a nice method for generating a set of lists (A) from a list of sets (C).

I am trying for an algorithm that accepts a graph like B and returns a list of axes like C (actually one or more, see example below), which can be used with the method above to generate a set of lists like A.

However, it is not guaranteed that the set of lists will be a Cartesian product. For example:

{[a,b,d,f],
 -missing-
 [a,b,e,f],
 [a,c,e,f]}

corresponding to the DAG:

  b-->d
 / \   \
a   \   f
 \   \ /
  c-->e

cannot be expressed as 1 Cartesian product but can be expressed as 2:

{a}*{b}*{d,e}*{f}    and    {a}*{c}*{e}*{f}

corresponding to the graphs:

      d
     / \
a-->b   f            and     a-->c-->e-->f 
     \ /
      e

The lists should have some degree of relatedness (think: a random sample of a very large Cartesian product).

Note: lists of different lengths cannot share the same set of axes.

Is there an algorithm that does this and I just haven't Googled the right terms? If not, can we create it?

Complexity of the algorithm may be an issue as the set could have 10^2 lists and each list could have 10^2 of items, i.e. a fairly large graph. I can guarantee that the input graphs would have the minimal number of nodes possible to represent the set of lists..., and that connected non-branching nodes (a->c->e->f) can be rolled up into single objects (acef).

PS. I don't think this is same as the Cartesian product of graphs, but there could be some overlap.

Answer 1

If I understand your question correctly, you're after (A) and only want (C) as an intermediate step. Generate the shortest paths through the graph using e.g. Dijkstra's algorithm - this will generate the set of lists (A). If you still need the Cartesian product at this point (i.e. if you weren't just generating the Cartesian product as an intermediate step to generating (A)) then it's much easier to generate it from (A) than from (B).