一种最优网络最大流算法的选择方法和设备

摘要

本发明实施例提供一种最优网络最大流算法的选择方法和设备。涉及网络最大流领域，能够根据不同的网络流图确定最优的网络最大流算法。该方法包括：算法选择设备获取网络流图，并根据该网络流图得到第一残量网络；获取操作算法集合，其中，该操作算法集合包括至少两个算法，在该第一残量网络中通过该至少两个算法并行进行预流推进，得到第二残量网络，并在该第二残量网络中确定该至少两个算法对应的关键边的数量，确定该关键边的数量的最大值对应的算法为该网络流图的最优网络最大流算法。本发明实施例用于网络最大流算法的选择。

说明书

技术领域

本发明涉及网络最大流领域，尤其涉及一种最优网络最大流算法 的选择方法和设备。

背景技术

获取网络最大流问题是图论和组合优化中的经典问题，它具有广 泛的应用背景。

现有技术中，预流推进方法是一种常用的获取网络最大流的方法， 该方法包括多种算法，这些算法可以归纳为:根据获取的网络流图得到 残量网络，从残量网络中获取活跃结点，并在该残量网络中将活跃结 点对应的盈余流通过相邻结点向汇点进行推进，并在确定该相邻结点 为新的活跃结点后，继续在该残量网络将该新的活跃结点通过相邻结 点向汇点进行推进，直至该残量网络中不存在活跃结点，则确定此时 汇点的流量为网络最大流。

由上可知，在现有的通过预流推进方法获取网络最大流的过程中， 只是通过一种算法对网络流图进行预流推进，也就是说，无论获取的 网络流图是哪种类型（例如可以是非平衡的二分图），都通过一种算 法进行计算，但是，对于不同类型的网络流图，该算法对网络最大流 的计算并不一定是最优的，由于不适应这个网络流图的算法冗余操作 多，因此无法保证该算法对网络流图的算法性能（如运算时间和运算 效率等），从而降低了网络最大流计算的效率。

发明内容

本发明的实施例提供一种最优网络最大流算法的选择方法和设 备，能够根据不同的网络流图确定最优的网络最大流算法。

为达到上述目的，本发明的实施例采用如下技术方案：

第一方面，提供一种最优网络最大流算法的选择方法，包括：

获取网络流图，并根据所述网络流图得到第一残量网络；

获取操作算法集合，其中，所述操作算法集合包括至少两个算法；

在所述第一残量网络中通过所述至少两个算法并行进行预流推 进，得到第二残量网络，并在所述第二残量网络中确定所述至少两个 算法对应的关键边的数量；

确定所述关键边的数量的最大值对应的算法为所述网络流图的最 优网络最大流算法。

在第一方面第一种可能的实现方式中，所述根据所述网络流图得 到第一残量网络后，还包括：

根据所述第一残量网络获取活跃结点；

所述获取操作算法集合包括：

根据算法模板获取所述活跃结点对应的算法和数据结构；其中， 所述算法模板包括用户配置的管理所述活跃结点的数据结构和用户配 置的对应所述活跃结点的算法以及所述网络流图的数据结构；

根据所述算法和数据结构获得所述操作算法集合。

结合第一种可能的实现方式，在第二种可能的实现方式中，所述 方法还包括：

对所述网络流图的数据结构加细粒度锁。

结合第一种可能的实现方式或第二种可能的实现方式，在第三种 可能的实现方式中，所述在所述第一残量网络中通过所述至少两个算 法并行进行预流推进包括：

根据所述至少两个算法从所述管理活跃结点的数据结构中获取对 应的活跃结点；

根据所述至少两个算法并行将所述对应的活跃结点的盈余流通过 距离标识比自己低的相邻结点向汇点进行推进，其中，所述盈余流包 括所述活跃结点的入流量与出流量的正差值。

结合第三种可能的实现方式，在第四种可能的实现方式中，所述 在将所述对应的活跃结点的盈余流通过所述相邻结点向汇点进行推进 后，还包括：

若所述相邻结点存在所述盈余流，则确定所述相邻结点为新的活 跃结点，并将所述新的活跃结点放入所述管理活跃结点的数据结构中。

结合第四种可能的实现方式，在第五种可能的实现方式中，在所 述得到第二残量网络前，还包括：

在通过所述至少两个算法并行进行预流推进时，获取被重标识的 边数；

根据所述算法模板获取更新参数；

在确定所述更新参数和所述被重标识的边数满足预设条件时，更 新所有结点到汇点的距离标识，以得到所述所有结点到汇点的新的距 离标识；

所述得到第二残量网络包括：

根据所述所有结点到汇点的新的距离标识得到所述第二残量网 络。

结合第四种可能的实现方式或第五种可能的实现方式，在第六种 可能的实现方式中，在确定所述管理活跃结点的数据结构不存在活跃 结点时，则确定汇点的流量为所述网络最大流。

结合第一方面至第六种可能的实现方式中的任意一种可能的实现 方式，在第七种可能的实现方式中，所述在所述第一残量网络中通过 所述至少两个算法并行进行预流推进前，所述方法还包括：

获取总线程数；

根据所述总线程数配置对应所述至少两个算法的线程数，其中， 所述线程数包括所述总线程数与所述至少两个算法的算法数量的比 值；

所述在所述第一残量网络中通过所述至少两个算法并行进行预流 推进包括：

在所述第一残量网络中通过所述至少两个算法根据所述对应的线 程数并行进行预流推进。

结合第七种可能的实现方式，在第八种可能的实现方式中，在确 定所述关键边的数量的最大值对应的算法为最优网络最大流算法后， 还包括：

根据所述关键边的数量为所述至少两个算法重新配置线程数。

第二方面，提供一种算法选择设备，包括：

获取单元，用于获取网络流图，并根据所述网络流图得到第一残 量网络，并获取操作算法集合，其中，所述操作算法集合包括至少两 个算法；

处理单元，用于在所述第一残量网络中通过所述至少两个算法并 行进行预流推进，得到第二残量网络，并在预流推进后确定所述至少 两个算法对应的关键边的数量，并在所述第二残量网络中确定所述关 键边的数量的最大值对应的算法为所述网络流图的最优网络最大流算 法。

在第二方面第一种可能的实现方式中，所述获取单元还用于，根 据所述网络流图得到第一残量网络后，根据所述第一残量网络获取活 跃结点；

所述获取单元具体用于，根据算法模板获取所述活跃结点对应的 算法和数据结构，并根据所述算法和数据结构获得所述操作算法集合， 其中，所述算法模板包括用户配置的管理所述活跃结点的数据结构和 用户配置的对应所述活跃结点的算法以及所述网络流图的数据结构。

结合第一种可能的实现方式，在第二种可能的实现方式中，所述 处理单元还用于，对所述网络流图的数据结构加细粒度锁。

结合第一种可能的实现方式或第二种可能的实现方式，在第三种 可能的实现方式中，所述处理单元具体用于，根据所述至少两个算法 从所述管理活跃结点的数据结构中获取对应的活跃结点，并根据所述 至少两个算法并行将所述对应的活跃结点的盈余流通过距离标识比自 己低的相邻结点向汇点进行推进，其中，所述盈余流包括所述活跃结 点的入流量与出流量的正差值。

结合第三种可能的实现方式，在第四种可能的实现方式中，所述 处理单元还用于，在将所述对应的活跃结点的盈余流通过所述相邻结 点向汇点进行推进后，若所述相邻结点存在所述盈余流，则确定所述 相邻结点为新的活跃结点，并将所述新的活跃结点放入所述管理活跃 结点的数据结构中。

结合第四种可能的实现方式，在第五种可能的实现方式中，所述 处理单元还用于，在通过所述至少两个算法并行进行预流推进时，获 取被重标识的边数，根据所述算法模板获取更新参数，并在确定所述 更新参数和所述被重标识的边数满足预设条件时，更新所有结点到汇 点的距离标识，以得到所述所有结点到汇点的新的距离标识，并根据 所述所有结点到汇点的新的距离标识得到所述第二残量网络。

结合第四种可能的实现方式或第五种可能的实现方式，在第六种 可能的实现方式中，所述处理单元还用于，在确定所述管理活跃结点 的数据结构不存在活跃结点时，则确定汇点的流量为所述网络最大流。

结合第二方面至第六种可能的实现方式中的任意一种可能的实现 方式，在第七种可能的实现方式中，所述获取单元还用于，在所述第 一残量网络中通过所述至少两个算法并行进行预流推进前，获取总线 程数；

所述处理单元还用于，配置对应所述至少两个算法的线程数，并 在所述第一残量网络中通过所述至少两个算法根据所述对应的线程数 并行进行预流推进，其中，所述线程数包括所述总线程数与所述至少 两个算法的算法数量的比值。

结合第七种可能的实现方式，在第八种可能的实现方式中，所述 处理单元还用于，在确定所述关键边的数量的最大值对应的算法为最 优网络最大流算法后，根据所述关键边的数量为所述至少两个算法重 新配置线程数。

采用上述方案，通过操作算法集合中的多种算法对网络流图进行 预流推进，并在预流推进后，将各算法对应的关键边的数量最多的算 法确定为最优网络最大流算法，使得在获取网络最大流的计算过程中， 能够动态调整自适应不同的网络流图，得到最优性能的算法，从而提 高网络最大流计算的效率。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对实施例描 述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附 图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不 付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例提供的一种最优网络最大流算法的选择方法 的流程示意图；

图2为本发明实施例提供的另一种最优网络最大流算法的选择方 法的流程示意图；

图3为本发明实施例提供的一种算法选择设备的结构示意图；

图4为本发明实施例提供的另一种算法选择设备的结构示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方 案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部 分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普 通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例， 都属于本发明保护的范围。

发明实施例提供一种最优网络最大流算法的选择方法，如图1所 示，该方法的执行主体为算法选择设备，包括：

S101、算法选择设备获取网络流图，并根据该网络流图得到第一 残量网络。

其中，该残量网络是通过对网络流图的变换得到的。

S102、算法选择设备获取操作算法集合。

其中，该操作算法集合包括至少两个算法。

具体地，该算法选择设备根据第一残量网络获取活跃结点，其中， 活跃结点为入流量大于出流量的结点，该算法选择设备根据算法模板 获取该活跃结点对应的算法和数据结构，并根据该算法和数据结构获 得该操作算法集合。

其中，该算法模板包括用户配置的管理活跃结点的数据结构和用 户配置的对应该活跃结点的算法以及该网络流图的数据结构。

示例地，该算法模板包括主控部分，提供算法的框架；算法部分， 可以由用户配置至少两个算法；结点管理部分，包括获取的活跃结点 以及用户配置的对应管理活跃结点的数据结构（如bucket、FIFO_queue 和stack中的任一种）；更新事件，用于更新第一残量网络中各结点 到汇点的距离标识；更新参数，由用户进行配置；网络流图数据结构， 用于存放残量网络。

其中，算法部分、结点管理部分和更新参数可以由用户进行配置。

例如，上述算法框架可以为：

其中，activeV表示残量网络存在活跃结点的个数，while(activeV) 表示残量网络存在活跃结点的个数不为零时执行算法，i= workset.remove()表示将该活跃结点从结点管理部分中取出，workset 即表示用户配置的对应管理活跃结点的数据结构；vertex.compute(i) 表示通过该活跃结点对应的算法对该活跃结点的盈余流进行运算。

需要说明的是，算法选择设备可以根据上述算法模板获取到由用 户配置的算法和数据结构，并根据该算法和数据结构得到该操作算法 集合，该操作算法集合可以为：

其中，workset::bucket(i->d)表示用户配置的管理活跃结点的数 据结构；vertex.compute1(node*i){…workset.push(j);}表示 活跃结点及对应的算法，GLOB_UPDT_FREQ=0.5表示用户配置的更新 参数。通过上述操作算法集合可以实现多个算法并行运算。

进一步地，算法选择设备可以对该网络流图的数据结构加细粒度 锁，从而防止数据竞争，例如，防止活跃结点对应算法之外的其它算 法对该活跃结点的读写操作。

S103、算法选择设备在该第一残量网络中通过该至少两个算法并 行进行预流推进，得到第二残量网络，并在所述第二残量网络中确定 该至少两个算法对应的关键边的数量。

其中，这里所说的并行是指在其中一个算法执行的过程中，可以 同时执行另一个算法，并不限定是在同一时刻开始执行。

具体地，算法选择设备根据该至少两个算法从该管理活跃结点的 数据结构中获取对应的活跃结点，并根据该至少两个算法并行将该对 应的活跃结点的盈余流通过距离标识比自己低的相邻结点向汇点进行 推进。

其中，该盈余流包括该活跃结点的入流量与出流量的正差值。

可选地，若该相邻结点存在该盈余流，则算法选择设备确定该相 邻结点为新的活跃结点，并将该新的活跃结点放入该管理活跃结点的 数据结构中。

进一步地，算法选择设备在通过该至少两个算法并行进行预流推 进时，获取被重标识的边数，并根据该算法模板获取更新参数，在确 定该更新参数和该被重标识的边数满足预设条件时，更新所有结点到 汇点的距离标识，以得到该所有结点到汇点的新的距离标识，并根据 该所有结点到汇点的新的距离标识得到第二残量网络。

示例地，算法选择设备在确定该被重标识的边数与该更新参数的 乘积大于网络流图的边数和结点数的乘积时，确定更新该新的活跃结 点的流量，算法选择设备具体可以由汇点进行反向宽度优先搜索实现 对所有结点到汇点距离标识的更新，并在距离标识更新后，根据更新 后的距离标识得到第二残量网络，并在该第二残量网络中统计该至少 两个算法对应的关键边的数量。

可选地，算法选择设备在确定该管理活跃结点的数据结构不存在 活跃结点时，则确定汇点的流量为该网络最大流，这样，由于通过并 行执行该至少两个算法计算该网络流图，加快了获取该网络最大流的 速度，从而提高了计算效率。

进一步地，算法选择设备在该第一残量网络中通过该至少两个算 法并行进行预流推进前，获取总线程数，并配置对应该至少两个算法 的线程数，则算法选择设备在该第一残量网络中通过该至少两个算法 根据该对应的线程数并行进行预流推进。

其中，该线程数包括该总线程数与该至少两个算法的算法数量的 比值，也就是说，算法选择设备为每个算法配置的线程数是相同的。

例如，算法并行执行的代码可以是：

parallel_for(the number of algorithms)并行执行所有算法， 其中，the number of algorithms表示算法的数量， parallel_for(thread_group[i])执行算法i，其中，thread_group[i] 表示算法i对应的线程组；algorithm_i()表示算法i。

需要说明的是，线程数越多，则对应算法的运算时间越快，运算 效率越高。

S104、算法选择设备确定该关键边的数量的最大值对应的算法为 该网络流图的最优网络最大流算法。

具体地，算法对应的关键边的数量越多，则表明该算法的冗余操 作越少，因此，确定该算法为对应该网络流图的最优网络最大流算法。

进一步地，算法选择设备在确定该关键边的数量的最大值对应的 算法为最优网络最大流算法后，根据该关键边的数量为该至少两个算 法重新配置线程数。

具体地，在确定最优网络最大流算法后，则为该最优网络最大流 分配更多的线程，从而使得该算法在运算的过程中，减少运算时间， 提高运算效率，从而提高该算法的算法性能。

采用上述执行主体为算法选择设备的方案，算法选择设备通过操 作算法集合中的多种算法对网络流图进行预流推进，并在预流推进后， 将各算法对应的关键边的数量最多的算法确定为最优网络最大流算 法，使得在获取网络最大流的计算过程中，能够动态调整自适应不同 的网络流图，得到最优性能的算法，从而提高网络最大流计算的效率。

本发明实施例提供一种最优网络最大流算法的选择方法，如图2 所示，包括：

S201、算法选择设备获取网络流图，并根据该网络流图得到第一 残量网络。

其中，该残量网络是通过对网络流图的变换得到的。

S202、算法选择设备根据该第一残量网络获取活跃结点。

S203、算法选择设备根据算法模板获取该活跃结点对应的算法和 数据结构，并对该网络流图的数据结构加细粒度锁。

其中，活跃结点为入流量大于出流量的结点，该算法模板包括该 用户配置的管理活跃结点的数据结构和用户配置的对应该活跃结点的 算法以及该网络流图的数据结构。

具体地，该算法选择设备将获取到的活跃结点放入该管理活跃结 点的数据结构中。

示例地，该算法模板包括主控部分，提供算法的框架；算法部分， 可以由用户配置至少两个算法；结点管理部分，包括获取的活跃结点 以及用户配置的对应管理活跃结点的数据结构（如bucket、FIFO_queue 和stack中的任一种）；更新事件，用于更新第一残量网络中各结点 到汇点的距离标识；更新参数，由用户进行配置；网络流图数据结构， 用于存放残量网络。

其中，算法部分、结点管理部分和更新参数可以由用户进行配置。

例如，上述算法框架可以为：

其中，activeV表示残量网络存在活跃结点的个数，while(activeV) 表示残量网络存在活跃结点的个数不为零时执行算法，i= workset.remove()表示将该活跃结点从结点管理部分中取出，workset 即表示用户配置的对应管理活跃结点的数据结构；vertex.compute(i) 表示通过该活跃结点对应的算法对该活跃结点的盈余流进行运算。

需要说明的是，算法选择设备可以根据上述算法模板获取到由用 户配置的算法和数据结构，并根据该算法和数据结构得到该操作算法 集合，该操作算法集合可以为：

其中，workset::bucket(i->d)表示用户配置的管理活跃结点的数 据结构；vertex.compute1(node*i){…workset.push(j);}表示 活跃结点及对应的算法，GLOB_UPDT_FREQ=0.5表示用户配置的更新 参数。通过上述操作算法集合可以实现多个算法并行运算。

S204、算法选择设备根据该算法和数据结构获得该操作算法集合。

其中，该操作算法集合包括至少两个算法。

S205、算法选择设备根据该至少两个算法从该管理活跃结点的数 据结构中获取对应的活跃结点。

S206、算法选择设备获取总线程数，并根据该总线程数配置对应 该至少两个算法的线程数。

其中，该线程数包括该总线程数与该至少两个算法的算法数量的 比值。

需要说明的是，线程数越多，则对应算法的运算时间越快，运算 效率越高。

S207、算法选择设备在该第一残量网络中通过该至少两个算法根 据该对应的线程数并行进行预流推进。

其中，该盈余流包括该活跃结点的入流量与出流量的正差值。

例如，算法并行执行的代码可以是：

parallel_for(the number of algorithms)并行执行所有算法， 其中，the number of algorithms表示算法的数量， parallel_for(thread_group[i])执行算法i，其中，thread_group[i] 表示算法i对应的线程组；algorithm_i()表示算法i。

S208、在预流推进后，若该活跃结点的相邻结点存在盈余流，则 算法选择设备确定该相邻结点为新的活跃结点，并将该新的活跃结点 放入该管理活跃结点的数据结构中。

S209、算法选择设备在通过该至少两个算法并行进行预流推进时， 获取被重标识的边数，并根据该算法模板获取更新参数。

需要说明的是，若算法选择设备在进行预流推进后，确定管理活 跃结点的数据结构中不存在活跃结点，则确定汇点的流量为网络最大 流，这样，由于通过并行执行该至少两个算法计算该网络流图，加快 了获取该网络最大流的速度，从而提高了计算效率。

S210、算法选择设备在确定该更新参数和该被重标识的边数满足 预设条件时，更新所有结点到汇点的距离标识，以得到该所有结点到 汇点的新的距离标识。

示例地，算法选择设备在确定该被重标识的边数与该更新参数的 乘积大于网络流图的边数和结点数的乘积时，确定更新所有结点到汇 点的距离标识，算法选择设备具体可以由汇点进行反向宽度优先搜索 实现对所有结点到汇点的距离标识更新，并在距离标识更新后，根据 更新后的距离标识得到第二残量网络，并在该第二残量网络中统计该 至少两个算法对应的关键边的数量。

S211、算法选择设备根据该新的距离标识得到该第二残量网络。

S212、算法选择设备在该第二残量网络中确定该至少两个算法对 应的关键边的数量。

S213、算法选择设备确定该关键边的数量的最大值对应的算法为 该网络流图的最优网络最大流算法。

S214、算法选择设备为该最优网络最大流算法重新配置线程数。

具体地，在确定最优网络最大流算法后，则为该最优网络最大流 分配更多的线程，从而使得该算法在运算的过程中，减少运算时间， 提高运算效率，从而提高该算法的算法性能。

采用上述方案，使得在获取网络最大流的计算过程中，能够动态 调整自适应不同的网络流图，得到最优性能的算法，从而提高网络最 大流计算的效率。

需要说明的是，对于上述方法实施例，为了简单描述，故将其都 表述为一系列的动作组合，但是本领域技术人员应该知悉，本发明并 不受所描述的动作顺序的限制，其次，本领域技术人员也应该知悉， 说明书中所描述的实施例均属于优选实施例，所涉及的动作和模块并 不一定是本发明所必须的。

本发明实施例提供一种算法选择设备30，如图3所示，包括：

获取单元31，用于获取网络流图，并根据该网络流图得到第一残 量网络，并获取操作算法集合。

其中，该残量网络是通过对网络流图的变换得到的，该操作算法 集合包括至少两个算法。

处理单元32，用于在该第一残量网络中通过该至少两个算法并行 进行预流推进，得到第二残量网络，并在预流推进后确定该至少两个 算法对应的关键边的数量，并在所述第二残量网络中确定该关键边的 数量的最大值对应的算法为该网络流图的最优网络最大流算法。

进一步地，该获取单元31还用于，根据该网络流图得到第一残量 网络后，根据该第一残量网络获取活跃结点。

具体地，该获取单元31将获取到的活跃结点放入该管理活跃结点 的数据结构中。

该获取单元31具体用于，根据算法模板获取该活跃结点对应的算 法和数据结构，并根据该算法和数据结构获得该操作算法集合，其中， 该算法模板包括用户配置的管理活跃结点的数据结构和用户配置的对 应该活跃结点的算法以及该网络流图的数据结构。

示例地，该算法模板包括主控部分，提供算法的框架；算法部分， 可以由用户配置至少两个算法；结点管理部分，包括获取的活跃结点 以及用户配置的对应管理活跃结点的数据结构（如bucket、FIFO_queue 和stack中的任一种）；更新事件，用于更新第一残量网络中各结点 的距离标识；更新参数，由用户进行配置，网络流图数据结构，用于 存放残量网络。

其中，算法部分、结点管理部分和更新参数可以由用户进行配置。

例如，上述算法框架可以为：

其中，activeV表示残量网络存在活跃结点的个数，while(activeV) 表示残量网络存在活跃结点的个数不为零时执行算法，i= workset.remove()表示将该活跃结点从结点管理部分中取出，workset 即表示用户配置的对应管理活跃结点的数据结构；vertex.compute(i) 表示通过该活跃结点对应的算法对该活跃结点的盈余流进行运算。

需要说明的是，该算法选择设备可以根据上述算法模板获取到由 用户配置的算法和数据结构，并根据该算法和数据结构得到该操作算 法集合，该操作算法集合可以为：

其中，workset::bucket(i->d)表示用户配置的管理活跃结点的数 据结构；vertex.compute1(node*i){…workset.push(j);}表示 活跃结点及对应的算法，GLOB_UPDT_FREQ=0.5表示用户配置的更新 参数。通过上述操作算法集合可以实现多个算法并行运算。

进一步地，该处理单元32还用于，对网络流图的数据结构加细粒 度锁，从而防止数据竞争，例如，防止活跃结点对应算法之外的其它 算法对该活跃结点的读写操作。

可选的，处理单元32具体用于，根据该至少两个算法从该管理活 跃结点的数据结构中获取对应的活跃结点，并根据该至少两个算法并 行将该对应的活跃结点的盈余流通过相邻结点向汇点进行推进。

其中，该盈余流包括该活跃结点的入流量与出流量的正差值。

需要说明的是，这里所说的并行是指在其中一个算法执行的过程 中，可以同时执行另一个算法，并不限定是在同一时刻开始执行。

进一步的，该处理单元还用于，在将该对应的活跃结点的盈余流 通过距离标识比自己低的相邻结点向汇点进行推进后，若该相邻结点 存在该盈余流，则确定该相邻结点为新的活跃结点，并将该新的活跃 结点放入该管理活跃结点的数据结构中。

该获取单元31还用于，在该第一残量网络中通过该至少两个算法 并行进行预流推进前，获取总线程数，并且该处理单元根据该总线程 数配置对应该至少两个算法的线程数，并在该第一残量网络中通过该 至少两个算法根据该对应的线程数并行进行预流推进。

其中，该线程数包括该总线程数与该至少两个算法的算法数量的 比值，也就是说，该算法选择设备为每个算法配置的线程数是相同的。

例如，算法并行执行的代码可以是：

parallel_for(the number of algorithms)并行执行所有算法， 其中，the number of algorithms表示算法的数量， parallel_for(thread_group[i])执行算法i，其中，thread_group[i] 表示算法i对应的线程组；algorithm_i()表示算法i。

需要说明的是，线程数越多，则对应算法的运算时间越快，运算 效率越高。

可选地，该处理单元32还用于，在通过所述至少两个算法并行进 行预流推进时，获取被重标识的边数，根据该算法模板获取更新参数， 并在确定该更新参数和该被重标识的边数满足预设条件时，更新所有 结点到汇点的距离标识，以得到该所有结点到汇点的新的距离标识， 并根据该新的距离标识得到该第二残量网络。

示例地，算法选择设备在确定该被重标识的边数与该更新参数的 乘积大于网络流图的边数和结点数的乘积时，确定更新所有结点到汇 点的距离标识，算法选择设备具体可以由汇点进行反向宽度优先搜索 实现对所有结点到汇点的距离标识的更新，并在距离更新后，根据更 新后的距离标识得到第二残量网络，并在该第二残量网络中统计该至 少两个算法对应的关键边的数量。

进一步地，该处理单元32还用于，在确定该关键边的数量的最大 值对应的算法为最优网络最大流算法后，根据该关键边的数量为该至 少两个算法重新配置线程数。

具体地，算法对应的关键边的数量越多，则表明该算法的冗余操 作越少，因此，则确定该算法为对应该网络流图的最优网络最大流算 法。

在确定最优网络最大流算法后，则为该最优网络最大流分配更多 的线程，从而使得该算法在运算的过程中，减少运算时间，提高运算 效率，从而提高该算法的算法性能。

可选地，该获取单元31还用于，在确定该管理活跃结点的数据结 构中不存在活跃结点时，则确定汇点的流量为该网络最大流，这样， 由于通过并行执行该至少两个算法计算该网络流图，加快了获取该网 络最大流的速度，从而提高了计算效率。

采用上述算法选择设备，该算法选择设备通过操作算法集合中的 多种算法对网络流图进行预流推进，并在预流推进后，将各算法对应 的关键边的数量最多的算法确定为最优网络最大流算法，使得在获取 网络最大流的计算过程中，能够动态调整自适应不同的网络流图，得 到最优性能的算法，从而提高网络最大流计算的效率。

本发明提供一种算法选择设备40，如图4所示，该算法选择设备 40包括：

处理器（processor）41、通信接口（Communications Interface）42、 存储器（memory）43和通信总线44；其中，所述处理器41、所述通 信接口42和所述存储器43通过所述通信总线44完成相互间的通信。

处理器41可能是一个多核中央处理器CPU，或者是特定集成电路 ASIC（Application Specific Integrated Circuit），或者是被配置成实施 本发明实施例的一个或多个集成电路。

存储器43用于存放程序代码，所述程序代码包括计算机操作指令 和网络流图。存储器43可能包含高速RAM存储器，也可能还包括非 易失性存储器（non-volatile memory），例如至少一个磁盘存储器。

所述通信接口42，用于实现这些装置之间的连接通信。

所述处理器41执行程序代码，用于获取网络流图，并根据该网络 流图得到第一残量网络，获取操作算法集合，在该第一残量网络中通 过该至少两个算法并行进行预流推进，得到第二残量网络，并在该第 二残量网络中确定该至少两个算法对应的关键边的数量，并确定该关 键边的数量的最大值对应的算法为该网络流图的最优网络最大流算 法。

其中，该操作算法集合包括至少两个算法。

可选地，该处理器41还用于，根据该第一残量网络获取活跃结点， 并根据算法模板获取该活跃结点对应的算法和数据结构，并根据该算 法和数据结构获得该操作算法集合。

其中，该算法模板包括用户配置的管理活跃结点的数据结构和用 户配置的对应该活跃结点的算法以及该网络流图的数据结构。

可选地，该处理器41还用于，对该网络流图的数据结构加细粒度 锁。

可选地，该处理器41具体用于，根据该至少两个算法从该管理活 跃结点的数据结构中获取对应的活跃结点，并根据该至少两个算法并 行将该对应的活跃结点的盈余流通过相邻结点向汇点进行推进。

其中，该盈余流包括该活跃结点的入流量与出流量的正差值。

可选地，该处理器41具体用于，若该相邻结点存在该盈余流，则 确定该相邻结点为新的活跃结点，并将该新的活跃结点该放入管理活 跃结点的数据结构中。

可选地，该处理器41还用于，在通过所述至少两个算法并行进行 预流推进时，获取被重标识的边数，并根据该算法模板获取更新参数， 在确定该更新参数和该被重标识的边数满足预设条件时，更新所有结 点到汇点的距离标识，以得到该所有结点到汇点的新的距离标识，并 根据该新的距离标识得到该第二残量网络。

可选地，该处理器41还用于，在确定该管理活跃结点的数据结构 中不存在活跃结点时，则确定汇点的流量为该网络最大流。

可选地，该处理器41还用于，获取总线程数，并根据该总线程数 配置对应该至少两个算法的线程数，在该第一残量网络中通过该至少 两个算法根据该对应的线程数并行进行预流推进。

其中，该线程数包括该总线程数与该至少两个算法的算法数量的 比值；

可选地，该处理器41还用于，根据该关键边的数量为该至少两个 算法重新配置线程数。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并 不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范 围内，可轻易想到变化或替换，都应涵盖在本发明的保护范围之内。 因此，本发明的保护范围应所述以权利要求的保护范围为准。