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

问题描述

好的，因此在根据输入数据的拓扑排序中，通常有多个正确的解决方案，图表的顺序可以被处理，以便所有依赖关系都在依赖它们的节点之前。但是，我正在寻找一个稍微不同的答案：

假设以下数据：
a - > b 和 c - >必须在 b 和 c 之前加上（ a code>必须在 d 之前。

只有这两个约束，我们有多个候选解：（ abcd ， acdb ， cabd 等等）。然而，我想创建一个分组这些节点的方法，以便在处理一个组后，下一个组中的所有条目都有它们的依赖关系。对于上述假设的数据，我会寻找一个分组如（a，c）（b，d）。在每个组内，节点处理的顺序无关紧要（ 之前 c 或 之前，，反之亦然），只要组1 （a，c）



只有附加的catch才能在第2组（b，d）将是每个节点应该在最早的组中。请考虑以下内容：

a - > b - > c

d - > e - > f

x - > （a，d）（b，e，x）（c，f，b）的分组方案， y）在技术上是正确的，因为 x 在 y 之前，因为 x 在（a，d，x）（b，e，y）（c，f）组2暗示 x 依赖于组1中的某个节点。

关于如何去做的任何想法这个？

---

编辑：我想我设法把一些解决方案代码。感谢所有帮助过的人！

  //拓扑排序
 //接受：无边缘non-0 = edge] 
 //返回：1d数组，其中每个索引是节点的group_id 
向量< int> top_sort（vector< vector< int>> graph）
 {
 int size = graph.size 
 vector< int> group_ids = vector< int>（size，0）; 
 vector< int> node_queue; 
 
 //找到根节点，将它们添加到队列中。 
 for（int i = 0; i  {
 bool is_root = true; 
 
 for（int j = 0; j  {
 if（graph [j] [i]！= 0）{is_root = false;打破; } 
} 
 
 if（is_root）{node_queue.push_back（i）; } 
} 
 
 //检测错误情况并根据需要处理。 
 if（node_queue.size（）== 0）
 {
 cerr<< 错误：图中找不到根节点。 << endl; 
 return vector< int>（size，-1）; 
} 
 
 
 //深度优先搜索，用新的深度更新每个节点。 
 while（node_queue.size（）> 0）
 {
 int cur_node = node_queue.back（）; 
 node_queue.pop_back（）; 
 
 //对于连接到当前节点的每个节点... 
 for（int i = 0; i  {
 if graph [cur_node] [i] == 0）{continue; } 
 
 //查看依赖节点是否需要用更后的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 。将所有子级标记为父级+1。如果一个节点已经被标记，则用更高的值更新它，并将它们推广给孩子们。

现在，你有与唯一标签0一样多的组。 .. n

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:

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.

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 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?

---

EDIT: 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;
}

解决方案

Label all root nodes as 0. Label all children as parent+1. if, a node is already labeled, update it with the higher value and propage them to the children.

now, you have as many groups as there are unique lables 0 ... n

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