Patent ID: 12223691

DETAILED DESCRIPTION OF THE EMBODIMENTS

The present invention will be described in detail below with reference to specific embodiments. It should be understood that these embodiments are only intended to describe the present invention, rather than to limit the scope of the present invention. In addition, it should be understood that various changes and modifications may be made on the present invention by those skilled in the art after reading the content of the present invention, and these equivalent forms also fall within the scope defined by the appended claims of the present invention.

An original termination condition of a push-relabel algorithm is to check whether there is no active node in a residual graph, which creates redundant computations in an application that requires only a maximum flow value, or a minimum cut rather than a complete maximum flow with all detail. In the application, a set S and a set T are separated for a long time late in the algorithm and will not change until the end, and this period is called a “finishing phase”. During the “finishing phase”, the push-relabel algorithm is busy pushing an excess flow in the set T to a sink node t, and relabeling the height of an active node in the set S to allow the excess flow to flow back to a source node s. For an application that does not require an exact maximum flow, the “finishing phase” of the push-relabel algorithm is redundant.

In view of this, the present invention proposes an early termination condition of the push-relabel algorithm defined by a separation condition and a stable condition. The separation condition is defined as the absence of an augmenting path from a source node to the sink node in the residual graph, and the stable condition is defined as the absence of an augmenting path from any active node to the sink node in the residual graph.

Based on the early termination condition, the push-relabel algorithm includes the following content:

For a graph G(V,E), V denotes a set of vertices, and E denotes a set of edges. A source node is defined as s∈V, and a sink node is defined as t∈V. A capacity function of the edge is defined as c:E→R, where R denotes a set of real numbers. A flow network is defined as F=(G,c,s,t).

A pseudo-flow is defined as fp:E→R, and fpsatisfies the following two constraints:(1) Skew symmetry: f(u,v)=−f(v,u), where (u,v) denotes a directed edge from u to v, and (v,u) denotes a directed edge from v to u.(2) Capacity constraint: f(u,v)≤c(u,v).

An excess flow of nodes is defined as ef:V→R. For u, ef(u)=Σv∈Vf(v,u).

For u, if ef(u)>0, u is an active node.

A pre-flow is defined as f:E→R. The pre-flow is a pseudo-flow, and for all non-source nodes, the excess flow is not negative: ∀v∈V/{s}, ef(v)≥0.

A residual graph of the graph G with respect to the pre-flow f is defined as Gf(V,Ef), and Efdenotes an edge set of the residual graph.

An excess capacity is defined as cf:E→R. For an edge e, the excess capacity is cf(e)=c(e)−f(e)

A height label function of nodes is defined as h:V→N, where N denotes a set of integers. If ∀(u,v)∈Ef, h(u)≤h(v)+1, then the height label is “legal”.

A feasible edge is defined. An edge (u,v) is feasible if h(u)≤h(v)+1.

A path is defined as P(u,v). The path is an ordered sequence of nodes {u, w0, w1, . . . , wk, v}. For any neighboring nodes in the sequence, for example, wiand wi+1, (wi, wi+1)∈E.

Reachable is defined. If there is a path P(u,v), u is reachable to v.

A number of nodes in P(u,v) with the least number of nodes minus one yield a distance from u to v, which is denoted as d(u,v). d(u,v) is initialized to 0.

A set T is composed of all nodes reachable to a sink node t.

Therefore, the max-flow/min-cut solution algorithm for early terminating push-relabel algorithm includes the following steps:

An initialization operation is performed.

The pre-flow is initialized, f(e)←0, ∀e∈E, and the height label is initialized, h(v)←d(v,t).

Alternatively, the height of the source node s is initialized to |V|, and the labels of other nodes are initialized to 0. At this point, a push operation should be performed immediately for all edges from the source node without checking whether they are feasible edges.

A push operation is performed.

An active node u is found from the set T. A feasible edge (u,v) is found for the active node, and the push operation is performed in the following order:
δ←min(ef(u),cf(u,v))
f(u,v)←f(u,v)+δ
f(v,u)←f(v,u)−δ
ef(u)←ef(u)−δ
ef(v)←ef(v)+δ

A relabel operation is performed.

An active node u is found from the set. If there is no feasible edge found for the active node, the relabel operation is performed as follows:

h⁡(u)←1+mincf(u,v)>0h⁡(v)

A T tree update operation is performed.

Starting from the sink node t, all nodes reachable to t are searched to update the set T.

Any push operations, relabel operations and T tree update operations may be performed in random order.

A termination determination is made at any time of the above calculation process, and it is determined whether the separation condition and the stable condition are satisfied at the same time. If yes, the algorithm terminates, otherwise, it returns to the push operation. If there is no source node s in the set T, the separation condition is satisfied; if there is no active node in the set T, the stable condition is satisfied.

InFIG.1, each bar denotes a test case, and the abscissa denotes the number of iteration cycles. In the iteration cycle denoted by the leftmost part, there is no (s,t)—cut. In the iteration cycle denoted by the second part from the left, there is already a (s,t)—cut, but it is not yet a minimum cut. In the iteration cycle denoted by the third part from the left, there is already a minimum cut, but the algorithm will still run because there are still active nodes in T, i.e., the stable condition is not satisfied. In the iteration cycle denoted by the first part from the right, there are no more active nodes in T, but the algorithm with the original termination condition will continue to run because there are still active nodes in S. The algorithm of the present invention will stop at the right end of the third part from the left, while the original algorithm will stop at the right end of the first part from the right. It can be seen that the algorithm of the present invention can save a lot of computations.

FIG.2shows statistical results acquired from more test data. The second bar from top indicates that the minimum cut is determined. This is not exactly the same as the third bar from the bottom, which indicates that the stable condition is met. An iterative gap between the averages of these two bars is called a termination gap. The left and right edges of the bar graph are respectively the minimum and maximum values of the number of iterations that satisfy the corresponding conditions. The left slash in the middle indicates the average. It can be seen from the figure that the time to determine the minimum cut is close to the time to satisfy the stable condition, and it is far from the original termination of the push-relabel algorithm (the first from the bottom up).

The present invention is applicable to all max-flow/min-cut problems that can use the push-relabel algorithm, and can run on a central processing unit (CPU), a graphics processing unit (GPU) or a field programmable gate array (FPGA). This embodiment provides an FPGA implementation example.

To evaluate the method proposed by the present invention, the present invention uses the widely used Middlebury benchmark to test the push-relabel algorithm. A baseline image is segmented into 25×25 tiles. The tile size is also the size of a processor array. The processor array can process 625 nodes in a two-dimensional (2D) grid graph in parallel. The present invention uses SystemVerilog to describe the hardware implementation of the entire system. The present invention uses Xilinx's Virtex Ultrascale VU190 as an evaluation board and Xilinx Vivado 2020.1 as an electronic design automation (EDA) tool. The clock frequency of the VU190 evaluation board is set to 66 MHz. Compared to the state-of-the-art method, the early termination function of the present invention can achieve at least a 12-fold speedup.