Топологическая сортировка с группировкой

Question

Итак, в топологической сортировке в зависимости от входных данных обычно есть несколько правильных решений, для которых порядок "графа" может быть "обработан", так что все зависимости располагаются перед "зависимыми" от них узлами. Тем не менее, я ищу немного другой ответ:

Предположим, следующие данные:a -> b а также c -> d (a должен прийти раньше b а также c должен прийти раньше d).
Только с этими двумя ограничениями у нас есть несколько вариантов решения:a b c d, a c d b, c a b d, так далее). Однако я собираюсь создать метод "группировки" этих узлов, чтобы после обработки группы все записи в следующей группе имели свои зависимости. Для вышеупомянутых предполагаемых данных я бы искал группировку как (a, c) (b, d), Внутри каждой группы не имеет значения, в каком порядке обрабатываются узлы (a до c или же b до dи тд и наоборот) просто пока группа 1 (a, c) завершается до любой из группы 2 (b, d) обрабатываются.

Единственным дополнительным уловом будет то, что каждый узел должен быть в самой ранней возможной группе. Учтите следующее:
a -> b -> c
d -> e -> f
x -> y

Схема группировки (a, d) (b, e, x) (c, f, y) технически было бы правильно, потому что x раньше y, более оптимальное решение будет (a, d, x) (b, e, y) (c, f) потому что имея x в группе 2 подразумевается, что x зависел от какого-то узла в группе 1.

Есть идеи, как это сделать?

---

РЕДАКТИРОВАТЬ: Я думаю, что мне удалось собрать воедино некоторый код решения. Спасибо всем, кто помог!

// Topological sort
// Accepts: 2d graph where a [0 = no edge; non-0 = edge]
// Returns: 1d array where each index is that node's group_id
vector<int> top_sort(vector< vector<int> > graph)
{
    int size = graph.size();
    vector<int> group_ids = vector<int>(size, 0);
    vector<int> node_queue;

    // Find the root nodes, add them to the queue.
    for (int i = 0; i < size; i++)
    {
        bool is_root = true;

        for (int j = 0; j < size; j++)
        {
            if (graph[j][i] != 0) { is_root = false; break; }
        }

        if (is_root) { node_queue.push_back(i); }
    }

    // Detect error case and handle if needed.
    if (node_queue.size() == 0)
    {
        cerr << "ERROR: No root nodes found in graph." << endl;
        return vector<int>(size, -1);
    }


    // Depth first search, updating each node with it's new depth.
    while (node_queue.size() > 0)
    {
        int cur_node = node_queue.back();
        node_queue.pop_back();

        // For each node connected to the current node...
        for (int i = 0; i < size; i++)
        {
            if (graph[cur_node][i] == 0) { continue; }

            // See if dependent node needs to be updated with a later group_id
            if (group_ids[cur_node] + 1 > group_ids[i])
            {
                group_ids[i] = group_ids[cur_node] + 1;
                node_queue.push_back(i);
            }
        }
    }

    return group_ids;
}

Answer 1

Пометить все корневые узлы значением уровня 0. Пометить всех потомков значением уровня parent+1. Если узел повторно посещается, т. Е. Ему уже присвоено значение уровня, проверьте, является ли ранее назначенное значение ниже нового. Если так, обновите это с более высоким значением и распространите их потомкам.

теперь у вас столько групп, сколько уникальных меток уровней 0 ... K

Answer 2

Я недавно реализовал этот алгоритм. Я начал с подхода, который вы показали, но он не масштабировался до графиков более 20 миллионов узлов. Решение, которое я выбрал, основано на подходе, подробно описанном здесь.

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

Рассмотрим график:

A -> X

B -> X

X -> Y

X -> Z

Таким образом, желаемый результат - (A,B), (X), (Y, Z)

Основной подход состоит в том, чтобы найти все без использования этого (A, B в этом примере). Все они на высоте 0.

Теперь удалите A и B из графика, найдите все, что теперь не имеет ничего, используя его (теперь X в этом примере). Итак, Х на высоте 1.

Удалите X из графика, найдите все, что теперь не имеет ничего, используя его (теперь Y, Z в этом примере). так что Y, Z на высоте 2.

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

Итак, для этого примера в начале:

• 0 вещей используют 1
• 0 вещей используют 2
• 2 вещи используют X (1 и 2)
• 1 вещи используют Y,Z (X)

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