SAS递归处理实体关联数据集 实现连通客户分组ID生成

问题场景 #

桥接表in01存储实体间双向关联关系：若客户A与客户B存在关联，表中会同时存储A/B、B/A两条对称重复记录，测试数据构造代码如下：

/* 测试数据构造 */
data in01(keep=primary: secondary:);
    infile datalines;
    length primary_party_no secondary_party_no $ 15;
    input primary_party_no secondary_party_no ;
    datalines;
A B
B A
A C
C A
B D
D B
W Z
Z W
Y Z
Z Y
X Y
Y X
;
run;

需求说明 #

为所有存在连通关联的客户分配统一分组ID，只要两个客户可通过任意层数的关联链路连通，即归属为同一分组。

测试数据预期分组结果：

• Group 1：A、B、C、D
• Group 2：W、X、Y、Z

这个需求本质是无向图的连通分量求解问题，不需要设计递归自调用的数据步或宏程序，以下两种方案都可以直接落地： #

方案1：PROC OPTNET过程步实现（生产环境首选） #

SAS的OR模块自带的网络优化过程原生支持连通分量计算，不需要手动处理遍历逻辑，仅需对原始数据做简单去重即可调用，代码简洁且性能极强，适合百万级以上的关联数据处理：

/* 第一步：去重，仅保留单向边，减少冗余计算 */
proc sort data=in01(keep=primary_party_no secondary_party_no) nodupkey out=edges;
    where primary_party_no < secondary_party_no;
run;

/* 第二步：调用OPTNET计算连通分量 */
proc optnet data_links=edges out_nodes=group_res;
    data_links_var
        from=primary_party_no
        to=secondary_party_no;
    concomp; /* 自动为每个连通块生成唯一分组ID */
run;

输出表group_res中的concomp字段即为所需分组ID，和预期结果完全匹配。 #

方案2：哈希表实现并查集逻辑（无SAS/OR模块时使用） #

如果没有SAS/OR模块权限，可以手动实现经典的并查集算法：用哈希表存储每个节点的所属分组，迭代遍历所有关联边，将连通节点的分组合并，直到没有新的合并发生时迭代终止，即可得到最终分组结果：

data group_res;
    length party_no $15 group_id 8;
    if _n_=1 then do;
        /* 初始化节点-分组映射哈希表 */
        declare hash node_grp();
        node_grp.definekey('party_no');
        node_grp.definedata('party_no','group_id');
        node_grp.definedone();
        call missing(party_no, group_id);

        /* 提取所有唯一节点，初始每个节点单独为一个组 */
        declare hash node_list(dataset:'in01(keep=primary_party_no rename=(primary_party_no=party_no))');
        node_list.definekey('party_no');
        node_list.definedone();
        declare hiter list_iter('node_list');
        rc = list_iter.first();
        gid = 1;
        do while(rc=0);
            node_grp.add(key:party_no, data:party_no, data:gid);
            gid + 1;
            rc = list_iter.next();
        end;

        /* 迭代合并连通分组，直到无新合并发生 */
        changed = 1;
        do while(changed=1);
            changed = 0;
            /* 遍历所有关联边 */
            declare hash edge_list(dataset:'in01');
            edge_list.definekey('_n_');
            edge_list.definedata('primary_party_no','secondary_party_no');
            edge_list.definedone();
            declare hiter edge_iter('edge_list');
            rc_e = edge_iter.first();
            do while(rc_e=0);
                /* 获取两个关联节点当前所属分组 */
                node_grp.find(key:primary_party_no);
                g1 = group_id;
                node_grp.find(key:secondary_party_no);
                g2 = group_id;
                /* 分组不一致时，将大分组ID合并到小分组ID */
                if g1 ^= g2 then do;
                    changed = 1;
                    new_g = min(g1, g2);
                    old_g = max(g1, g2);
                    /* 更新所有属于旧分组的节点为新分组ID */
                    rc_u = list_iter.first();
                    do while(rc_u=0);
                        node_grp.find(key:party_no);
                        if group_id = old_g then do;
                            group_id = new_g;
                            node_grp.replace(key:party_no, data:party_no, data:group_id);
                        end;
                        rc_u = list_iter.next();
                    end;
                end;
                rc_e = edge_iter.next();
            end;
            edge_list.delete();
        end;
    end;

    /* 输出最终分组结果 */
    rc = list_iter.first();
    do while(rc=0);
        node_grp.find(key:party_no);
        output;
        rc = list_iter.next();
    end;
    stop;
    keep party_no group_id;
run;

内容的提问来源于stack exchange，提问作者Martin Dreher