(Набор) Список множеств (декартово произведение (ы)) из графика, соответствующего набору списков

Набор списков (A):

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

где a, b, c, d, e и f - элементы (не обязательно символы в слове), (DAG, B, все точки ребер слева → вправо):

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

или как декартово произведение четырех наборов элементов (C, обозначенных осей):

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

В Guava есть хороший метод для создания набора списков (A) из списка наборов (C).

Я пытаюсь использовать алгоритм, который принимает граф типа B и возвращает список осей типа C (фактически один или несколько, см. пример ниже), который можно использовать с вышеописанным методом для создания набора списков типа A.

Однако не гарантируется, что набор списков будет декартовым произведением. Например:

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

соответствующий DAG:

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

не может быть выражено как 1 декартово произведение, но может быть выражено как 2:

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

соответствующего графикам:

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

Списки должны иметь некоторую степень родства (подумайте: случайная выборка очень большого декартова произведения).

Примечание: списки разной длины не могут использовать один и тот же набор осей.

Есть ли алгоритм, который делает это, и я просто не имею в виду правильные термины? Если нет, можем ли мы его создать?

Сложность алгоритма может быть проблемой, поскольку набор может иметь 10 ^ 2 списков, и каждый список может иметь 10 ^ 2 элементов, т.е. достаточно большой график. Я могу гарантировать, что входные графики будут иметь минимальное количество узлов, которые могут представлять набор списков... и что связанные не ветвящиеся узлы (a- > c- > e- > f) могут быть свернуты в одиночные объектов (acef).

PS. Я не думаю, что это так же, как декартово произведение графов, но может быть некоторое перекрытие.

Ответ 1