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

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.

Любые идеи о том, как это сделать?

---

EDIT: Я думаю, мне удалось удалиться вместе с некоторым кодом решения. Спасибо всем, кто помог!

// 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 + миллионами узлов. Решение, в котором я закончил, основано на the approach detailed here.

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

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

A -> Х

В -> Х

Х -> У

X -> Z

Таким образом, желаемый выход (A, B), (X), (Y, Z)

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

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

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

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

Таким образом, для данного примера в начале:

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

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