Spark环境下关联数据集的递归图着色算法实现问题咨询

背景说明 #

我有一个待着色的图，每个节点都关联一个由行/元组组成的Dataset集合。算法逻辑可通过下述示例说明：
（图1：图着色问题执行流程示例）

上传的图展示了节点集合为{v1, v3, v2}的图G的着色执行流程：图(a)初始所有节点未着色，先处理v1选择簇Sσ1 = {{t9, t10}}（图b），再递归调用着色方法处理v2和v3。
单节点着色会限制邻接节点的颜色选择：比如v1选了含t10的簇后，v3就不能选含t10的{{t6, t7, t10}}簇，v3可选{{t6, t7}}、{{t7, t8}}等簇。
图(c)中着色算法为v3选择{{t6, t7}}，会导致v2仅有的可选簇{{t5, t6}}因重叠t6不可用，触发失败（图d）。算法回溯v3的选择，改为选择{{t7, t8}}（图e），此时v2的{{t5, t6}}簇与v3的簇无重叠，满足所有约束，着色方法返回true，返回的V中存储所有节点及对应的着色簇。

我当前编写的代码运行耗时过长，怀疑节点着色逻辑存在问题，其中nodeIterator参数存储按自定义规则排序的所有图节点：

public Boolean coloring(graph, nodeIterator, vector){
    Node  nodeIt  ;
    if (nodeIterator.hasNext())
        nodeIt = nodeIterator.next();
    else {
        return false;
    }
    // cluster是当前节点关联的数据集
    ArrayList<Dataset<Row>> cluster = allClustersOfGraph.getNextDataset(nodeIt.name);
    if (graph.getNeighbors(nodeIt) == null) {
        if (!nodeIterator.hasNext()){
            colorNode(vector, nodeIt);
            return false;
        }
        else {
            colorNode(vector, nodeIt);
            nodeIterator.next();
        }
    }
    Iterable<Node> adjNodes = graph.getNeighbors(nodeIt);
    Iterator<Node> adjNodesIt = adjNodes.iterator();
    // 我怀疑下面应该用if而不是while，这样当前节点的下一个邻接节点会在下一轮递归调用中处理
    while (adjNodesIt.hasNext()){
        Node adjNode = adjNodesIt.next();
        if (!checkNodeColored(vector, adjNode)) {
            ArrayList<Dataset<Row>> adjCluster = allClustersOfGraph.getNextDataset(adjNode.name);
            for (Dataset<Row> subCluster : cluster) {
                for (Dataset<Row> subAdjCluster : adjCluster) {
                    // 小数据集（行元组）无交集
                    if (noDatasetIntersection(subCluster, subAdjCluster)) {
                         colorNode(vector, nodeIt, subCluster);
                        if (coloring(graph, nodeIterator, vector)) {
                            return true;
                        } else {
                           // vector存储当前着色进度
                            // 回溯
                            vector.remove(vector.size() - 1);
                        }
                    }
                }
            }
        } else if (!adjNodesIt.hasNext()) {
                    // 给最后一个节点着色
                    colorNode(vector, nodeIt);
            return true;
        }
    }
    return false;
}

allClustersOfGraph的类型为ArrayList<ArrayList<Dataset<Row>>>，伪算法参考如下：
（图2：着色伪算法参考）

核心问题 #

我在递归方法中使用while (adjNodesIt.hasNext()){...}循环在单次递归调用中检查当前处理节点的所有邻接节点，该写法在递归方法中是否合理？我的实现是否覆盖了所有边界场景？

问题解答 #

1. while循环的写法完全不合理
   你的怀疑是正确的，这正是代码耗时过长的核心原因：

• 你已经通过nodeIterator按自定义顺序逐个取节点处理，单次递归只需要处理当前取出的nodeIt的合法性校验即可，不需要遍历所有邻接节点触发递归。当前的while循环会为每个未着色的邻接节点都触发一轮递归，相当于同一个nodeIt的着色会被重复尝试N次（N为未着色邻接节点数量），直接导致递归调用次数指数级上升。
• 未着色邻接节点的约束校验会在轮到它们被nodeIterator取出的时候自行完成，不需要在当前节点的处理逻辑里提前处理，属于完全冗余的逻辑。

2. 现有实现存在大量边界场景遗漏

• 孤立节点处理分支错误：当节点无邻接节点且还有后续节点待处理时，你额外调用了一次nodeIterator.next()，会直接跳过下一个节点的处理，导致节点漏着色。
• 约束校验逻辑不全：没有校验当前节点选的簇和所有已经着色的邻接节点的簇是否冲突，仅校验了遇到的第一个未着色邻接节点的可选簇，可能出现冲突的着色结果。
• 递归终止条件错误：当nodeIterator没有下一个节点的时候直接返回false，正确逻辑应该是所有节点都处理完成，已经找到合法着色方案，返回true。
• 邻接节点遍历完的返回逻辑错误：只要所有邻接节点都已经着色就直接返回true，不会继续处理nodeIterator里剩余的未处理节点，导致大量节点漏着色。

3. 修正方向
   把while循环整体替换为如下逻辑即可：

• 先遍历所有已经着色的邻接节点，筛选出当前节点所有和已着色邻接节点簇无交集的合法可选簇
• 对每个合法簇，着色当前节点后递归调用coloring处理下一个节点
• 递归返回true就直接向上返回true，否则回溯尝试下一个簇
• 所有簇都尝试失败就返回false

内容的提问来源于stack exchange，提问作者Patrick Schulz