Кодирование ориентированного графа в виде чисел

Для любой DAG вы можете определить x <= y как "есть путь от x до y". Это отношение является частичным порядком. Я полагаю, что вопрос заключается в том, как эффективно представить это отношение.

Для каждой вершины X определите ¡X как множество вершин, достижимых из X (включая само X). Два утверждения

• ¡X является подмножеством ¡Y
• X достижим из Y

эквивалентны.

Закодируйте эти наборы как наборы битов (N-битные двоичные числа), и все готово.

Вы называете отношение <=, но оно обязательно не полное (то есть: может быть, что для данной пары a и b ни a <= b, ни b <= a).

Вот одна из идей, как это определить.

Если ваши узлы пронумерованы 0, 1..., N-1, вы можете определить type следующим образом:

type(i) = (1 << i) + sum(1 << (N + j), for j such that Path(i, j))

И определите <= следующим образом:

type1 <= type2 if (type1 >> N) & type2 != 0

То есть type(i) кодирует значение i в младших N битах, а набор всех достижимых узлов - в старших N битах. Отношение <= ищет целевой узел в закодированном наборе достижимых узлов.

Это определение работает независимо от того, есть ли в графе циклы, и фактически просто кодирует произвольное отношение в вашем наборе узлов.

Вы можете сделать определение немного более эффективным, используя ceil(log2(N)) бит для кодирования номера узла (всего N + ceil(log2(N)) бит на type).

В вопросе говорилось (и продолжает говориться), что входные данные представляют собой дерево, но более позднее редактирование опровергло это с помощью примера ромбовидного графика. В таких случаях, не являющихся деревьями, мой алгоритм ниже не будет применяться.

Существующие ответы работают для общих отношений на общих ориентированных графах, что увеличивает размеры их представления до O (n) бит для n вершин. Поскольку у вас есть дерево, возможно более короткое представление O (log n) бит.

В дереве, направленном от корня, для любых двух вершин u и v множества листьев L(u) и L(v), достижимых из u и v соответственно, должны быть либо непересекающимися, либо одна из них должна быть подмножеством другой. Если они не пересекаются, то u недостижимо из v (и наоборот); если одно является собственным подмножеством другого, то то, что имеет меньший набор, достижимо из другого (и в этом случае то, у которого меньшее множество, обязательно будет иметь строго большую глубину). Если L(u) = L(v), то u достижимо из v тогда и только тогда, когда глубина (v) ‹ глубина (u), где глубина (u) — количество ребер на пути от корня к u. (В частности, если L(u) = L(v) и depth(u) = depth(v), то u = v.)

Мы можем кратко закодировать это отношение, заметив, что все листья, достижимые из данной вершины v, занимают непрерывный сегмент листьев, полученных при неупорядоченном обходе дерева. Таким образом, для любой заданной вершины v этот набор листьев может быть представлен парой целых чисел (first, last), где first идентифицирует первый лист (в порядке обхода), а last - последний. Тогда проверка существования пути от i к j очень проста — на псевдо-C++:

bool doesPathExist(int i, int j) {
    return x[i].first <= x[j].first && x[i].last >= x[j].last && depth[i] <= depth[j];
}

Обратите внимание, что если у каждой нелистовой вершины в дереве есть как минимум 2 дочерних вершины, то вам не нужно заморачиваться с глубинами, так как L(u) = L(v) подразумевает, что в этом случае u = v. (В моей исходной версии поста было сделано это предположение; теперь я исправил его, чтобы он работал, даже если это не так.)