Patent ID: 8533139
Filing Date: 2013-09-10
Classification: G06N

Abstract:
1. A method of speeding up computation of a minimum cut in a graph with a topology of an n-dimensional k-connected grid, wherein the computation is performed using a variant of the Boykov-Kolmogorov algorithm, the method comprising: determining a size of an n-dimensional rectangular block; padding the grid with a number of dummy nodes to make the extents of the grid evenly divisible by the size of the block in each dimension; dividing the grid into blocks of a determined size; representing a residual graph without explicit connectivity information, wherein the connectivity information is determined on the fly and is based on the graph's known regular structure; associating a set of fields with each node, wherein the fields comprise: arranging the fields associated with each node into separate arrays, wherein each array corresponds to a single field and each array element corresponds to a single node; assigning an array index to each node based on the node's grid coordinates; defining a fixed ordering of the node's k outgoing edges; assigning an integer index to each of the node's k outgoing edges based on the fixed ordering; accessing the node's neighbors by computing the neighbors' array indices based on the array index of the node; and accessing the reverse edge of the node's outgoing edge by determining the integer index of the neighbor's outgoing edge in the opposite direction.