带分组的拓扑排序 [英] Topological Sort with Grouping

问题描述

好的，所以在根据输入数据进行拓扑排序时，通常有多个正确的解决方案可以处理"图形的顺序，以便所有依赖项都出现在依赖"于它们的节点之前.但是，我正在寻找一个略有不同的答案:

Ok, so in topological sorting depending on the input data, there's usually multiple correct solutions for which order the graph can be "processed" so that all dependencies come before nodes that are "dependent" on them. However, I'm looking for a slightly different answer:

假设有以下数据:<代码>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) 中的任何一个被处理之前完成.

Suppose the following data: a -> b and c -> d (a must come before b and c must come before d).
With just these two constraints we have multiple candidate solutions: (a b c d, a c d b, c a b d, etc). However, I'm looking to create a method of "grouping" these nodes so that after the processing of a group, all of the entries in the next group have their dependencies taken care of. For the above supposed data I'd be looking for a grouping like (a, c) (b, d). Within each group it doesn't matter which order the nodes are processed (a before c or b before d, etc and vice versa) just so long as group 1 (a, c) completes before any of group 2 (b, d) are processed.

唯一的附加问题是每个节点都应该尽可能在最早的组中.考虑以下几点:
<代码>a ->b->c
<代码>d ->e ->f
<代码>x ->y

The only additional catch would be that each node should be in the earliest group possible. Consider the following:
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 组中的某个节点.

A grouping scheme of (a, d) (b, e, x) (c, f, y) would technically be correct because x is before y, a more optimal solution would be (a, d, x) (b, e, y) (c, f) because having x in group 2 implies that x was dependent on some node in group 1.

关于如何去做这件事有什么想法吗?

Any ideas on how to go about doing this?

我想我设法拼凑了一些解决方案代码.感谢所有帮助过的人！

I think I managed to slap together some solution code. Thanks to all those who helped!

// 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;
}

推荐答案

用级别值 0 标记所有根节点.用级别值 parent+1 标记所有子节点.如果正在重新访问节点，即它已经分配了级别值，请检查先前分配的值是否低于新值.如果是，则用更高的值更新它并将它们传播给后代.

Label all root nodes with a level value 0. Label all children with level value parent+1. If, a node is being revisited i.e it already has a level value assigned, check if the previously assigned value is lower than the new one. If so, update it with the higher value and propagate them to the descendents.

现在，您拥有与唯一级别标签一样多的组 0 ... K

now, you have as many groups as there are unique level labels 0 ... K

这篇关于带分组的拓扑排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！