拓扑结构分析算法

發表於 2022-09-01 分類於开发笔记

2022年09月01日于武汉

flowchart TB
%%{init: { "flowchart": { "curve": "basis" } } }%%
R0[智能融合终端<br>SCU]
R0--->N1[断路器<br>9]
R0--->N2[断路器<br>16]
N1--->N1.1[断路器<br>7]
N1--->N1.2[断路器<br>6]
N1--->N1.3[断路器<br>10]
N1--->N1.4[断路器<br>12]
N2--->N2.1[断路器<br>18]
N2--->N2.2[断路器<br>19]
N2--->N2.3[断路器<br>14]
N1.1--->N1.1.1[断路器<br>3]
N1.1--->N1.1.2[断路器<br>4]
N1.1--->N1.1.3[断路器<br>5]
N1.2--->N1.2.1[断路器<br>8]
N1.2--->N1.2.2[断路器<br>11]
N1.3--->N1.3.1[断路器<br>2]
N2.2--->N2.2.1[断路器<br>13]
N2.2--->N2.2.2[断路器<br>17]
N1.1.1--->N1.1.1.1[断路器<br>0]
N1.2.2--->N1.2.2.1[断路器<br>1]
N2.2.2--->N2.2.2.1[断路器<br>15]

拓扑识别

本文所述的拓扑分析算法针对的是有时间戳的拓扑识别

拓扑流程

flowchart TB
%%{init: { "flowchart": { "curve": "basis" } } }%%
R0[智能融合终端<br>SCU]-->A2[" "]
R0-->A1[断路器<br>1]
A1-->B2[" "]
A1-->B1[断路器<br>2]
B1-->C2[" "]
B1-->C1[断路器<br>3]

以上面这个简单的拓扑结构为例：

当 SCU 给一号断路器发送拓扑信号发生指令后一号断路器会存储一条发生记录。

当 SCU 给二号断路器发送拓扑信号发生指令后二号断路器会存储一条发生记录，此时一号断路器会识别到拓扑信号并存储一条识别记录，并且这两条记录中的时间基本一致。

当 SCU 给三号断路器发送拓扑信号发生指令后三号断路器会存储一条发生记录，此时一号断路器和二号断路器均会识别到拓扑信号并存储一条识别记录，并且这三条记录中的时间基本一致。

最终：

一号断路器总计存储 3 条拓扑记录；
二号断路器总计存储 2 条拓扑记录；
三号断路器总计存储 1 条拓扑记录；

拓扑信号发生流程结束后，智能融合终端会读取每台断路器中的拓扑记录，并将数据整理为以下格式：

然后智能融合终端便可通过本算法以及上述数据计算出所有断路器之间的拓扑关系。

记录数量：每台断路器中拓扑记录的数量
记录内容：每条拓扑记录产生时的时间戳

算法概述

核心思想：从末端节点开始，依次寻找每个节点的父节点，最终找到根节点。最后递归打印出拓扑关系。

1. 遍历只有一条记录的节点（末端节点）遍历完之后将末端节点的记录数量置为零。

2. 遍历其他大于一条记录的节点

3. 判断该节点是否存在与末端节点时间相同的记录｜如果存在则表示该节点为末端节点的潜在父节点（并将该节点的记录数量减一）

4. 拓扑记录数量最少的那个节点即为当前末端节点的父节点

5. 更新拓扑网络（记录父节点）

6. 更新修改过的记录数量｜然后开始下一循环｜直至所有记录数量为零为止

7. 最后可以得到每个节点的父节点是谁（父节点为自身的即为根节点，可以存在多个根节点）

8. 将上述数据递归打印即可得到期望结果

算法详解

这里通过一个示例来描述该算法的逻辑。

遍历之前的拓扑结构（示例）

flowchart TB
%%{init: { "flowchart": { "curve": "basis" } } }%%
R0[智能融合终端<br>SCU]
R0--->N1[断路器<br>9]
R0--->N2[断路器<br>16]
N1--->N1.1[断路器<br>7]
N1--->N1.2[断路器<br>6]
N1--->N1.3[断路器<br>10]
N1--->N1.4[断路器<br>12]
N2--->N2.1[断路器<br>18]
N2--->N2.2[断路器<br>19]
N2--->N2.3[断路器<br>14]
N1.1--->N1.1.1[断路器<br>3]
N1.1--->N1.1.2[断路器<br>4]
N1.1--->N1.1.3[断路器<br>5]
N1.2--->N1.2.1[断路器<br>8]
N1.2--->N1.2.2[断路器<br>11]
N1.3--->N1.3.1[断路器<br>2]
N2.2--->N2.2.1[断路器<br>13]
N2.2--->N2.2.2[断路器<br>17]
N1.1.1--->N1.1.1.1[断路器<br>0]
N1.2.2--->N1.2.2.1[断路器<br>1]
N2.2.2--->N2.2.2.1[断路器<br>15]

遍历之前的数据结构（示例）

第一次遍历后的拓扑结构

flowchart TB
%%{init: { "flowchart": { "curve": "basis" } } }%%
R0[智能融合终端<br>SCU]
R0--->N1[断路器<br>9]
R0--->N2[断路器<br>16]
N1--->N1.1[断路器<br>7]
N1--->N1.2[断路器<br>6]
N1--->N1.3[断路器<br>10]
N1--->N1.4[" "]
N2--->N2.1[" "]
N2--->N2.2[断路器<br>19]
N2--->N2.3[" "]
N1.1--->N1.1.1[断路器<br>3]
N1.1--->N1.1.2[" "]
N1.1--->N1.1.3[" "]
N1.2--->N1.2.1[" "]
N1.2--->N1.2.2[断路器<br>11]
N1.3--->N1.3.1[" "]
N2.2--->N2.2.1[" "]
N2.2--->N2.2.2[断路器<br>17]
N1.1.1--->N1.1.1.1[" "]
N1.2.2--->N1.2.2.1[" "]
N2.2.2--->N2.2.2.1[" "]

第一次遍历后的数据结构

第二次遍历后的拓扑结构

flowchart TB
%%{init: { "flowchart": { "curve": "basis" } } }%%
R0[智能融合终端<br>SCU]
R0--->N1[断路器<br>9]
R0--->N2[断路器<br>16]
N1--->N1.1[断路器<br>7]
N1--->N1.2[断路器<br>6]
N1--->N1.3[" "]
N1--->N1.4[" "]
N2--->N2.1[" "]
N2--->N2.2[断路器<br>19]
N2--->N2.3[" "]
N1.1--->N1.1.1[" "]
N1.1--->N1.1.2[" "]
N1.1--->N1.1.3[" "]
N1.2--->N1.2.1[" "]
N1.2--->N1.2.2[" "]
N2.2--->N2.2.1[" "]
N2.2--->N2.2.2[" "]

第二次遍历后的数据结构

第三次遍历后的拓扑结构

flowchart TB
%%{init: { "flowchart": { "curve": "basis" } } }%%
R0[智能融合终端<br>SCU]
R0--->N1[断路器<br>9]
R0--->N2[断路器<br>16]
N1--->N1.1[" "]
N1--->N1.2[" "]
N1--->N1.3[" "]
N1--->N1.4[" "]
N2--->N2.1[" "]
N2--->N2.2[" "]
N2--->N2.3[" "]

第三次遍历后的数据结构

遍历完成之后得到的数据

核心代码

// 计算拓扑关系
while (HaveData && HaveDataOneRecord)
{
    HaveData = false;
    HaveDataOneRecord = false;

    for (int idx = 0; idx < TOPO_NODE_NUM; ++idx)
    {
        unsigned int MinNum = 0xFFFFFFFF;
        unsigned int MinIdx = idx;

        if (TopoNum[idx] > 0)
        {
            HaveData = true;
        }

        if (TopoNum[idx] == 1) // 遍历只有一条记录的节点（末端节点）
        {
            HaveDataOneRecord = true;

            TopoNumMod[idx]--;

            for (int i = 0; i < TOPO_NODE_NUM; ++i)
            {
                if (TopoNum[i] <= 1) // 遍历其他大于一条记录的节点
                {
                    continue;
                }

                for (int n = 1; n <= TopoSrc[i][0]; ++n) // 判断该节点是否存在与末端节点时间相同的记录
                {
                    if (TimeCompare(TopoSrc[idx][1], TopoSrc[i][n], TOPO_TIME_BIAS)) // 4example bias==3 (±3s)
                    {
                        // 如果存在则表示该节点为末端节点的潜在父节点（并将该节点的记录数量减一）
                        TopoNumMod[i]--;
                        if (TopoSrc[i][0] < MinNum)
                        {
                            MinNum = TopoSrc[i][0];
                            MinIdx = i; // 查找拓扑记录数量最少的节点
                            break;
                        }
                    }
                }
            }

            TopoNet[idx] = MinIdx; // 拓扑记录数量最少的那个节点即为当前末端节点的父节点
        }
    }

    // 经过上述步骤，拓扑记录数量为一的节点的记录数量被清零，同时又重新生成了一批新的拓扑记录数量为一的节点。
    // 这里更新中间变量，然后继续上述步骤：遍历新的只有一条记录的节点（新的末端节点），直至遍历完毕。
    memcpy(TopoNum, TopoNumMod, sizeof(TopoNum));
}

递归打印

void TopoPrint(unsigned int root, unsigned int *node, int node_num) // *node : 节点关系（所有节点的父节点信息）
{
    static int depth = 1;

    FILE * fp;

    for (int i = 0; i < node_num; ++i)
    {
        if (node[i] == root)
        {
            fp = fopen(TOPO_FILE_PATH, "a+");

            // 根节点禁止递归
            if (i == root)
            {
                fclose(fp);
                continue;
            }

            printf("|---");

            for (int d = 0; d < depth; ++d)
            {
                #if (ENABLE_PRINT)
                printf("|---");
                #endif
                #if (ENABLE_PRINT_TO_FILE)
                fprintf(fp, "|---");
                #endif
            }

            // 打印序号
            #if (ENABLE_PRINT)
            printf("%-8d", i);
            printf(TOPO_ALIGN_STR);
            #endif
            #if (ENABLE_PRINT_TO_FILE)
            fprintf(fp, "%-8d", i);
            fprintf(fp, TOPO_ALIGN_STR);
            #endif

            // 打印地址
            for (int len = 0; len < 6; ++len)
            {
                #if (ENABLE_PRINT)
                printf("%02X", TopoDev[i][len]);
                #endif
                #if (ENABLE_PRINT_TO_FILE)
                fprintf(fp, "%02X", TopoDev[i][len]);
                #endif
            }

            // 打印换行
            #if (ENABLE_PRINT)
            printf("\r\n");
            #endif
            #if (ENABLE_PRINT_TO_FILE)
            fprintf(fp, "\n");
            #endif

            fclose(fp);

            // 递归调用
            depth++;
            TopoPrint(i, node, node_num);
            depth--;
        }
    }
}