## Topological Sort and Tasks Scheduling (Kahn’s algorithm)

Topological Sort of a directed graph (a graph with unidirectional edges) is a linear ordering of its vertices such that for every directed edge (U, V) from vertex U to vertex VU comes before V in the ordering.

Given a directed graph, find the topological ordering of its vertices.

Example 1:

Input: Vertices=4, Edges=[3, 2], [3, 0], [2, 0], [2, 1]
Output: Following are the two valid topological sorts for the given graph:
1) 3, 2, 0, 1
2) 3, 2, 1, 0

Example 2:

Input: Vertices=5, Edges=[4, 2], [4, 3], [2, 0], [2, 1], [3, 1]
Output: Following are all valid topological sorts for the given graph:
1) 4, 2, 3, 0, 1
2) 4, 3, 2, 0, 1
3) 4, 3, 2, 1, 0
4) 4, 2, 3, 1, 0
5) 4, 2, 0, 3, 1

Here are a few fundamental concepts related to topological sort:

1. Source: Any node that has no incoming edge and has only outgoing edges is called a source.
2. Sink: Any node that has only incoming edges and no outgoing edge is called a sink.
3. So, we can say that a topological ordering starts with one of the sources and ends at one of the sinks.
4. A topological ordering is possible only when the graph has no directed cycles, i.e. if the graph is a Directed Acyclic Graph (DAG). If the graph has a cycle, some vertices will have cyclic dependencies which makes it impossible to find a linear ordering among vertices.

To find the topological sort of a graph we can traverse the graph in either a Breadth First Search (BFS) way using Kahn’s algorithm or Depth First Search (DFS). We will start with all the sources, and in a stepwise fashion, save all sources to a sorted list. We will then remove all sources and their edges from the graph. After the removal of the edges, we will have new sources, so we will repeat the above process until all vertices are visited.

[preserved_text 1fbfd1112ea81554cf8bd39aca16ff45 /]

#### Time Complexity

In step ‘d’, each vertex will become a source only once and each edge will be accessed and removed once. Therefore, the time complexity of the above algorithm will be O(V+E), where ‘V’ is the total number of vertices and ‘E’ is the total number of edges in the graph.

#### Space Complexity

The space complexity will be O(V+E), since we are storing all of the edges for each vertex in an adjacency list.

There are ‘N’ tasks, labeled from ‘0’ to ‘N-1’. Each task can have some prerequisite tasks which need to be completed before it can be scheduled. Given the number of tasks and a list of prerequisite pairs, find out if it is possible to schedule all the tasks.

Example 1:

Input: Tasks=3, Prerequisites=[0, 1], [1, 2]
Output: true
Explanation: To execute task '1', task '0' needs to finish first. Similarly, task '1' needs to finish
before '2' can be scheduled. A possible scheduling of tasks is: [0, 1, 2]


Example 2:

Input: Tasks=3, Prerequisites=[0, 1], [1, 2], [2, 0]
Output: false
Explanation: The tasks have cyclic dependency, therefore they cannot be scheduled.

As you can see, we can represent the task and its dependency as an edge in a directed graph. There’s a little change in the above code that need to be changed to solve this problem so I let this as an exercise for you. Instead of returning a list, you just need to return a boolean.

Another application of Topological Sort is to check if a directed graph contains a cycle.

## Eight queens problem, backtracking, Python3

• Problem:

Given an 8×8 board, your job is to place 8 queens on the board such that none of them can attack each other (If you are not familiar with chess, then google it first). The problem can be more general, given a n x n (n > 3) board, place n queens on the board such that there is no way a queen can attack the others. There are 92 solutions to this problem.

• Solutions

The way to solve this problem is already described in the title. Here’s let solve it step by step. First let’s try some thoughts on a small board to see if we can apply the approach which we are about to come up with on small board to a wider one.

To develop an algorithm for this problem, we can first study a smaller instance of the problem by using just four queens and a 4 * 4 board. How would you go about solving this smaller problem? You may attempt to randomly place the queens on the board until you find a solution that may work for this smaller case. But when attempting to solve the original eight-queens problem, this approach may lead to chaos.

Consider a more organized approach to solving this problem. Since no two queens can occupy the same column, we can proceed one column at a time and attempt to position a queen in each column. We start by placing a queen in the upper-left square or position (0, 0) using the 2-D array notation:

With this move, we now eliminate all squares horizontally, vertically, and diagonally from this position for the placement of additional queens since these positions are guarded by the queen we just placed.

With the first queen placed in the first column, we now move to the second column. The first open position in this column where a queen can be placed without being attacked by the first queen we placed is at position (2,1). We can place a queen in this position and mark those squares that this queen guards, removing yet more positions for the placement of additional queens.

We are now ready to position a queen in the third column. But you may notice there are no open positions in the third column. Thus, the placement of the first two queens will not result in a valid solution. At this point, you may be tempted to remove all of the existing queens and start over. But that would be a drastic move.

We first return to the second column and try alternate positions for that queen before possibly having to return all the way back to the first column.
The next step is to return to the second column and pick up the queen we placed at position (2,1) and remove the markers that were used to indicate the squares that queen was guarding.
We then place the queen at the next available square within the same column (3, 1) and mark the appropriate squares guarded from this position, as shown here:
Now we can return to the third column and try again. This time, we place a queen at position (1, 2), but this results in no open squares in the fourth column.
We could try other squares in the same column, but none are open. Thus, we must pick up the queen from the third column and again backtrack to try other combinations. We return to the second column and pick up the queen we placed earlier at position (3, 1) so we can try other squares within this column.

But there are no more open squares in the second column to try, so we must back up even further, returning to the first column. When returning to a column, the first step is always to pick up the queen previously placed in that column.

After picking up the queen in the first column, we place it in the next position (1, 0) within that column.

We can now repeat the process and attempt to find open positions in each of the remaining columns. These final steps, which are illustrated here, results in a solution to the four-queens problem.

Having found a solution for the four-queens problem, we can use the same approach to solve the eight-queens problem. The only difference between the two is that there is likely to be more backtracking required to find a solution. In addition, while the four-queens problem has two solutions, the eight-queens problem has 92 solutions.

The original problem definition only considered finding a solution for a normal 8 * 8 chessboard. A more general problem, however, is known as the n-queens problem, which allows for the placement of n queens on a board of size n*n where n > 3. The same backtracking technique described earlier can be used with the n-queens problem, although finding a solution to larger-sized boards can be quite time consuming.

The possible data structures for representing the actual board.

The most obvious choice is a 2-D array of size n * n. The elements of the array can contain boolean values with True indicating the placement of the queens. To determine if a given square is unguarded, loops can be used to iterate over all of the squares to which a queen can move from that position. If a queen is found in any of the squares searched during the loop iterations, then we know the square is currently guarded by at least one queen. The placement and removal of the queens is also quite easy to implement using the 2-D array structure.

As an alternative, we can actually use a 1-D array consisting of n elements. Each element of the 1-D array corresponds to one column on the board. The elements of the 1-D array will contain row indices indicating the positions of the queens on the board.

Since only one queen can be placed within a given column, we need only keep track of the row containing the queen in the column. When determining if a square is unguarded, we can iterate through the row and column indices for the preceding columns on the board from which the given square can be attacked by a queen. Instead of searching for a True value within the elements of a 2-D array, we need only determine if the elements of the 1-D array contain one of the row indices being examined.

When searching horizontally backward, we examine the elements of the 1-D array looking for an index equal to that of the current row. If one is found, then there is a queen already positioned on the current row as is the case in the above example. If a queen was not found on the current row, then we would have to search diagonally to the upper left and to the lower left. We only search in this two directions because we place the queen from left to right, column by column. In these two cases, we search the squares indicated by the arrows and examine the row indices of each and compare them to the entries in the 1-D array. If any of the indices match, then a queen is currently guarding the position and it is not a legal move.

Code using backtracking to solve n-queens problem.

from board import Board

def solve_n_queens(board, col, ways):
# check if n-queens has been placed on the board
# base case
if board.num_queens() == board.size():
ways.append([x for x in board._board])
return False
else:
for row in range(board.size()):
if board.unguarded(row, col):
# place a queen in that square
board.place_queen(row, col)
# continue placing queens in the following columns
if solve_n_queens(board, col+1, ways):
# we are finished if a solution was found
return True
else:
# no solution was found with the queen in this square
# so it has to be removed from the board
# and try the next row in this col
if board._board[0] == 1:
print(board._board)
board.remove_queen(row, col)

# If the loop terminates no queen can be placed within this column
return False

if __name__ == '__main__':

for col in range(0, 1):
ways = []
board = Board(8)
res = solve_n_queens(board, col, ways)
print(*ways, sep='\n')
print(len(ways))


The board

from array import Array

class Board:
def __init__(self, size):
self._size = size
self._board = Array(size)

def size(self):
return self._size

def num_queens(self):
return len([x for x in self._board if x is not None])

def place_queen(self, row, col):
self._board[col] = row

def remove_queen(self, row, col):
self._board[col] = None

def unguarded(self, row, col):
# first check if this row is guarded
if row in self._board:
return False
# check up left diagonal
up_left_row = row - 1
up_left_col = col - 1
while self._in_bound(up_left_row, up_left_col):
if self._board[up_left_col] is not None and \
self._board[up_left_col] == up_left_row:
return False
up_left_row -= 1
up_left_col -= 1
# check lower left diagonal
low_left_row = row + 1
low_left_col = col - 1
while self._in_bound(low_left_row, low_left_col):
if self._board[low_left_col] is not None and \
self._board[low_left_col] == low_left_row:
return False
low_left_row += 1
low_left_col -= 1

return True

def _in_bound(self, row, col):
return row >= 0 and row < self.size() and \
col >= 0 and col < self.size()


And the Array that’s used to construct Board

import ctypes

class Array:
def __init__(self, size):
assert size > 0, "Array size must be > 0"
self._size = size
PyArrayType = ctypes.py_object * size
self._elements = PyArrayType()
self.clear(None)

def __len__(self):
return self._size

def __getitem__(self, index):
assert index >= 0 and index < len(self), "Array subcript out of range"
return self._elements[index]

def __setitem__(self, index, value):
assert index >= 0 and index < len(self), "Array subcript out of range"
self._elements[index] = value

def clear(self, value):
for i in range(len(self)):
self._elements[i] = value

def __iter__(self):
return _ArrayIterator(self._elements)

def __str__(self):
str_template = ""
for item in self:
str_template += " %4s "
str_template = str_template.strip()
return "[" + str_template % tuple(self) + "]"

def __contains__(self, val):
for i in self:
if i is not None and i == val:
return True
return False


## Check if a number is palindromic, O(1) space complexity (Python3)

• Reverse digits

Since this is a simple problem so I don’t explain much here. You can either convert to string and then reverse that string or using mod 10. Here a chunk of code that uses the mod 10 approach:

def reverse(x):
result, x_remaining = 0, abs(x)
while x_remaining:
result = result * 10 + x_remaining % 10
x_remaining //= 10
return -result if x < 0 else result

• Check palindrome

We can easily solve this problem by converting the number into string and pairwise comparing digits starting from the least significant digit and the most significant digit, and working inwards, stopping if there is a mismatch. But time and space complexity of this approach is O(n).

We already know how to extract the least significant digit using mod 10, but how can we extract the most significant digit? The answer is using log base 10. To calculate the number of digits of a decimal integer, we have the formula:

num_digits = math.floor(math.log10(n)) +1

Everything works the same with the converting approach, which is pairwise comparing.

import math

def is_palindrome_number(x):
# since string representation of negative numbers
# is not palindromic
if x <= 0:
return x == 0

num_digits = math.floor(math.log10(x)) + 1
# msd : most significant digit
# msd is used to remove the msd from x
for i in range(num_digits // 2):
# check equality of msd and lsd
if x // msd_mask != x % 10:
return False
x %= msd_mask # get rid of the msd of x
x //= 10 # get rid of the lsd of x
msd_mask //= 100 # 100 because msd and lsd removal
# all pair of msd and lsd match
return True

# another solution could be reverse the digit and check if
# it equals with the original one (or they are the same)


## Compute x/y (quotient) using only the addition, subtraction and shifting operators (Python3)

Solutions:

• Brute-force:

A brute-force approach is to iteratively subtract y from x until what remains is less than y. The number of such subtractions is exactly the quotient, x/y, and the remainder is the term that’s less than y. The complexity of the brute-force approach is very high, when y=1 and x = K, it will take K iterations. K could be 1, 100, or even 10^20, etc.

• The grade-school division algorithm to binary numbers

A better approach is to try and get more work done in each iteration. We can compute the largest k such that pow(2,k)*y <= x, subtract pow(2k,)*y from x, and pow(2,k) to the quotient. For example, if x = 1011 (base 2), y = 10 (base 2), then k = 2. We subtract 1000 from 1011 to get 11, add pow(2,k) = 100 (base 2) to the quotient, and continue by updating x to 11.

The advantage of using pow(2,k)*y is that it can be compute very efficiently using shifting. If it takes n bits to represent x/y, there are O(n) iterations. If the largest k such that pow(2,k)*y <= x is computed by iterating through k, each iteration has time complexity O(n). This leads to an O(n^2) algorithm.

A better way to find the largest k in each iteration is to recognize that it keeps decreasing. Therefore, instead of testing in each iteration whether 2^0 * y, 2^1 * y, 2^2 * y, …. is less than or equal to x, after we initially find the largest k such that pow(2,k)*y <= x, in subsequent iterations we test 2^k-1 * y, 2^k-2 *y, 2^k-3 *y, …

For the example given earlier, after setting the quotient to 100 (binary), we continue with 11. Now the largest k such that pow(2, k)*y <= 11 is 0, so we add 2*0 to the quotient, which is now 101. We continue with 11 – 10 = 1. Since 1 < y, we are done, the quotient is 101, and the remainder is 1 (binary).

def divide(x, y):
result, power = 0, 32
# starting at 2^32 y
y_power = y << power
while x >= y:
# searching for biggest k such that
# 2^k * y <= x
while y_power > x:
y_power >>= 1
power -= 1

result += 1 << power
# subtract 2^k * y from x
x -= y_power
return result


With each iteration, we process an additional bit. Therefore, assuming individual shift and add operation take O(1), the time complexity is O(n).

## Compute x * y without arithmetic operator (Python3)

Problem:

Write a program that multiplies two nonnegative integers. The only operator you are allowed to use are:

• Assignment
• the bitwise operator >>, <<, |, &, ^ and
• equality check

Solution:

A brute-force approach would be to perform repeated addition. Initialize the result to 0 and then ad x to it y times. The time complexity is very high.

The algorithm taught in grade-school for decimal multiplication does not use repeated addition – it uses shift and add to achieve a much better time complexity. We can do the same with binary numbers – to multiply x and y we initialize the result to 0 and iterate through the bits of x, adding pow(2, k)*k to the result if kth bit of x is 1.

The value pow(2,k)*y can be computed by left-shifting y by k. Since we cannot use add, we have to implement it. We apply the grade-school algorithm for addition to the binary case, compute the sum of bit-by-bit, and ‘rippling’ the carry along.

Example: 13(1101) * 9(1001), using the algorithm described above.
In the first iteration, since the LSB of 13 is 1, we set the result to 1001. The second bit of 13(1101) is 0 so we move on to the third bit. This bit is 1, so we shift 1001 to the left by 2 to obtain 100100, which we add to 1001 to get 101101. The final bit of 1101 is 1, so we shift 1001 to the left by 3 (this is calculate pow(2, k)*y) to obtain 1001000, which we add to 101101 to get 1110101 = 117.

Each addition is itself performed bit-by-bit. For example when adding 101101 and 1001000, the LSB of the result is 1. The next bit is 1 (since the next bit of the operands are 0). The next bit is 1 (since exactly one of the next bits of the operands is 1). The next bit is 0 (since both the next bits of the operands are 1). We also ‘carry’ a 1 to the next position. The next bit is 1 (since the carry-in is 1 and both the next bits of the operands are 0). The remaining bits are assigned similarly.

def multiply(x, y):
# just note it somewhere and when you need to
# do bit-addition quickly, you know where to find it
running_sum, carryin, k, temp_a, temp_b = 0, 0, 1, a, b
while temp_a or temp_b:
ak, bk = a & k, b & k
carryout = (ak & bk) | (ak & carryin) | (bk & carryin)
running_sum |= ak ^ bk ^ carryin
carryin, k, temp_a, temp_b = (carryout << 1, k << 1, temp_a >> 1, temp_b >> 1)
return running_sum | carryin

# first initialize result to 0
running_sum = 0
while x: # examines each bit of x
if x & 1: # the current bit is 1
# first iteration will make result = y
# as in the example
# right shift x to get next LSB
# left shift y to get pow(2, k)
x, y = x >> 1, y << 1
return running_sum


Time complexity: O(n^2), where n is the number of bits.

## Find a closet integer with the same weight (Python3)

Theory:

The weight of a nonnegative integer n to be the number of bits that are set to 1 in its binary presentation. For example, 92 base 2 is 1011100, its weight is 4.

Problem:

Write a program which takes input as a nonnegative integer and returns a number m which is not equal to n, but has the same weight as and their difference |n-m| must be minimum. For example, if x = 6, you should return 5. You can assume the integer fits in 4 bits.

Solutions:

• Brute-force

A brute-force approach might be to try all integers n-1, n+1, n-2, n+2, … stopping as soon as we encounter one with the same weight as n. This is clearly unacceptable if we want to perform this operation repeatedly.

• Heuristic

If we swap the LSB and the right most bit that differ from it, we get the result. But this is only true for some cases. For example, if n in binary is 10, then the result is 01. But this is not true if we go back and apply this heuristic approach to the example in the Theory section.

• Analyze

Assume we not gonna deal with numbers that their binary presentation consist only 0s or 1s. The move that need to be done here is swap two bits, and after swapping the result must be a number such that its difference with the original is minimal. Lets say we need to swap (or flip if since they’re different) bit at position k1 and position k2 (k1 > k2), then the difference between the original and the new swapped number is pow(2, k1) – pow(2, k2). In order to minimize the difference, k1 must be as small as possible, and k2 is next to k1. We conclude that the final solution is to swap the two rightmost consecutive bits that differ.

Example 92 (1011100), if we apply heuristic approach, it yields 89 (1011001), the final solution which we come up with yields 90 (1011010).

def closet_same_weight(n):
NUM_UNSIGNED_BITS = 64
for i in range(NUM_UNSIGNED_BITS - 1):
# two right most consecutive bits differ
if (x >> i) & 1 != (x >> (i+1)) & 1:
# swap using 'XOR flip'
x ^= (1 << i) | (1 << (i+1))
return x

# raise error if all bits are either 0 or 1
raise ValueError('All bits are 0 or 1')


Time complexity: O(n), with n is the number of bits.

## Reverse bits (Python3)

Problem:

Write a program that takes a 64-bit unsigned integer and returns the 64-bit unsigned integer consisting of the bits of the input in reverse order. For example, input 110110, output should be 011011

Solutions:

• Simple brute force solution.

If we need to perform this operation just once, there is a simple brute-force algorithm iterate through the 32 least significant bits of the input, and swap each with the corresponding most significant bit. But this is not efficient if you want to perform this operation repeatedly.

• Using lookup table (cache)

As you may know, one of the way to speed up repeated operations is using lookup table. So the first step is somehow recognize how you can apply lookup table to this problem. If we divide 64-bit word into 4 16-bit words, then everything is crystal-clear.

64-bit word -> 4 16-bit word: y3 y2 y1 y0

y0 and y1 are 2 16-bit word consisting 32 least significant bits, y2 and y3 are 2 16-bit word consisting 32 most significant bits. From left to right, y3 is reverse of y0, y2 is reverse of y1, y1 is reverse of y2 and y0 is reverse of y3. So the first thing we need to do is create a lookup table A, where A[y] yields the reversed bits of y, lets say we name it PRECOMPUTED_REVERSE. Then the code looks like this:

def reverse_bits(n):
# first, use bitmask to extract 16 least significant bits (y0)
# then lookup in the table to get its reversed bits
# and left shift 3 times of masksize to make it become y3
# next right shift 16 bits to get the next 16 LSB
# then lookup in the table to get its reversed bits
# and left shift 2 times of masksize to make it become y2
# next right shift 32 bits to get the first 16 MSB (y2)
# then lookup in the table to get its reversed bits
# and left shift 1 time of masksize to make it become y1
# finally, right shift 3 times of masksize to get y3
# lookup to get its reversed bits
# the other bits.
# the for step can be described graphically like this:
# step1 we get: y0. - - -
# step2 we get: - y1. - -
# step3 we get: - - y2. -
# step4 we get: - - - y3.
# y1. means reverse of y1
# OR all of thems to get the final result



Time complexity: O(n/L) with L is width of word we choose (here is 16)

## Swap bits – flip XOR (Python3)

Theory:

A 64-bit integer can be viewed as an array of 64 bits, with the bit at index 0 corresponding to the least significant bit (LSB – the right most bit) and the bit at index 63 corresponding to the most significant bit (MSB – the left most bit).

Solution:

A brute-force approach would be to use bitmasks to extract the ith and the jth bits, saving them to local variables. Consequently, write the saved jth bit to index i and the saved ith bit to index j.

The brute-force approach works generally, if we were swapping objects stored in an array. However, since a bit can only take two values, we can do it a little better. We first test if the bits to be swapped differ. If they do, swapping them is the same as flipping their individual values.

Example:

The 8-bit integer 73 can be viewed as array of bits, with the LSB being at index 0.

MSB(0 1 0 0 1 0 0 1)LSB

Result of swapping the 6th and 1th bit, from right to left (in bold) respectively:

MSB(0 0 0 0 1 0 1 1)LSB

which is 11 in decimal.

def swap_bits(x, i, j):
# extract the i-th and j-th bits, and see if they differ
if (x >> i) & 1 != (x >> j) & 1:
# i-th and j-th bit differ. We will swap them by
# flipping their values.
# We can perform the 'fip XOR'
bit_mask = (1 << i) | (1 << j)
return x


Time complexity: O(1)

## Compute the parity of a word (Python3)

Theory:

• The parity of a word is 1 if the number of 1s in the word is odd; otherwise, it is 0. For example, the parity of 1011 is 1, and the parity of 10001000 is 0.
• Parity check are used to detect single bit errors in data storage and comminucation
• Trick must know: x&(x-1) equals with x with its lowest set bit erased. Example:

Given n = 845, in binary = 1101001101, n – 1 in binary = 1101001100, and n after n&(n-1) in binary = 1101001100. Continue, n after n&(n-1) in binary yields 1101001000, then 1101000000, so on. Until n becomes zero.

Solutions:

• Brute force
def parity(n):
result = 0
while n:
result ^= (n & 1)
n >>= 1
return result


The brute force algorithm iteratively tests the value of each bit while tracking the number of 1s seen so far.
First, we initialize result = 0, while n is still not 0, result is updated by applying the ^ (xor) operator on the returned value when we check if the least significant bit of n is 1 or 0. More explanation, value of result first is 0, so if there is 3 1s in n, result will be 1 (value of result is 1 or 0 each while-loop). n >>= 1 right shifts n 1 bit, eventually n will reach 0.
Time complexity: O(n) with n is number of bits of the given number.

• Improved brute force

Do you notice in the theory section above, the trick can be applied here to shorten the running time of the brute force solution. This is true because number of 1s equals with number of the lowest set bit. The change is minor:

def parity_improved(n):
result = 0
while n:
result ^= 1
n &= n-1
return result


Time complexity: O(k), with k is the number of lowest set bit.

Different approaches.

The problem statement refers to computing the parity for a very large number of words. When you have to perform a large number of parity computations, more generally, any kind of bit fiddling computations, two keys to performance are processing multiple bits at a time and caching results in an array-based lookup table.

• Caching approach

Clearly, we cannot cache the parity of every 64-bit integer, we would need pow(2,64) bits of storage, which is of the order of two exabytes. However, when computing the parity of a collection of bits, it does not matter how we group those bits, the computation is associative. Therefor, we can compute the parity of a 64-bit integer by grouping its bits into four non-overlapping 16 bit subwords, computing the parity of each subwords and then computing the parity of these four subresults. We choose 16 since pow(2, 16) is relatively small, which makes it feasible to cache the parity of all 16-bit words using an array. Furthermore, since 16 evenly divides 64.

Example with a lookup table for 2-bit words. The cache is [0, 1, 1, 0], these are parities of [00, 01, 10, 11], respectively. To compute parity of 11001010, we would compute the parities of 11, 00, 10, 10. By table lookup, we see these are 0,0,1,1, respectively, so the final result is 0.

To lookup the parity of the first two bits in 11101010, we right shift by 6, to get 00000011, and use this as an index into the cache. To lookup the parity of the next two bits 10, we right shift by 4. However, right shift does not remove the leading 11 when we right shift by 4 – results in 00001110. To get the last two bits after the right shift by 4, we bitwise-AND 00001110 with 00000011 (the “mask” to extract the last 2 bits). The result is 00000010. Similar masking needed fir the two other 2-bit lookups.

Given PRECOMPUTED_PARITIES is an array of parities of all numbers from 0 up to 65535. The code is fairly understandable.

def parity_caching(n):
# first right shift 48 to get first 16 bits
# then righ shift 32 to get next 16 bits
# then right shift 16 to get next 16 bits
# final and with BIT_MASK to get the final 16 bits
# and xor all of them together to get final result
return (PRECOMPUTED_PARITIES[n >> (3 * MASK_SIZE)] ^


Time complexity: O(n/L), with L is the width we cache the results.

• Use the parity property

XOR has the property of being associative, it does not matter how we group bits, as well as commutative, the order in which we perform the XORs does not change result. The XOR of a group of bits is its parity. For example, the parity of [b63,b62,…,b2,b1,b0] equals the parity of the XOR of [b63,b62,..b32] and [b31,b30,..,b2,b1]. The XOR of these two 32-bit values can be computed with a single shift and a single 32-bit XOR instruction. We repeat the same operation on 32-, 16-, 8-, 4-, 2- and 1-but operands to get the final result. Note that the leading bits are not meaningful, and we have to explicitly extract the result from the least-significant bit.

Example with an 8-bit word. The parity of 11010111 is the asme as the parity of 1101 XOR with 0111 – results in 1010. This in turn is the same as the parity of 10 XOR with 10 – results in 00. The final result of 0 XOR with 0 is 0. Note that the first XOR yields 11011010 and only the last 4 bits are relevant going forward. The second XOR yields 11101100, and only the last 2 bits are relevant. The third XOR yields 10011010. The last bit is the result, and to extract it we have to bitwise AND with 00000001. The code:

def parity_property(n):
x ^= x >> 32
x ^= x >> 16
x ^= x >> 8
x ^= x >> 4
x ^= x >> 2
x ^= x >> 1
return x & 0x1


Time complexity: O(logn)

## Learn openCV3 (Python): Contours, Convex Contours, Bounding Rect, Min Area Rect, Min Enclosing Circle, Approximate Bounding Polygon.

Beside edges detection, contour detection is also one of the vital tasks in computer vision. One thing to notice here is that when find contours, we usually work with thresholded image. What is thresholding image? Just Google it, it’s simply putting a threshold value for pixels, if those pixels have value bigger than threshold value, they’re gonna be set to a new value.

This is a very simple example, when we find contour in an image that have black background and a white rectangle in its center.

First we create a 200×200 grayscale image having black background by using numpy.zeros method. Then we create a 100×100 white squares in that image. Next we threshold the image, every pixels that have values higher than 127 will be set to 255. Then we use opencv’s findContours() method to find all contours in the image. cv2.RETR_TREE basically means you want to get all contours. This method returns a tuple with 3 elements,  we only need to focus on the second one, contours. Keep in mind that findContours(), as well as many other methods in opencv, usually only work well with gray scale images. Finally we use drawContours() with green color to make all contours visible.

import cv2
import numpy as np

ESC = 27

# create a black image with size 200x200 (in grayscale)
img = np.zeros((200, 200), dtype=np.uint8)
# set the center of image to be a 50x50 white rectangle
img[50:150, 50:150] = 255

# threshold the image
# if any pixels that have value higher than 127, assign it to 255
ret, threshed_img = cv2.threshold(img, 127, 255, 0)

# find contour in image
# cv2.RETR_TREE retrieves the entire hierarchy of contours in image
# if you only want to retrieve the most external contour
# use cv.RETR_EXTERNAL
image, contours, hierarchy = cv2.findContours(threshed_img, cv2.RETR_TREE,
cv2.CHAIN_APPROX_SIMPLE)
# convert image back to BGR
color_img = cv2.cvtColor(img, cv2.COLOR_GRAY2BGR)
# draw contours onto image
img = cv2.drawContours(color_img, contours, -1, (0, 255, 0), 2)

cv2.imshow("contours", img)

while True:
keycode = cv2.waitKey()
if keycode != -1:
keycode &amp;= 0xFF
if keycode == ESC:
break

cv2.distroyAllWindows


Result:

Next, we will see how to find a bounding box, minimum area rectangle, and minimum enclosing circle. (There is a tutorial on opencv website talking about this, you can check it out now or later)

Let’s take this image as an example.

You already know how to find contours in an image, so we won’t talk detailedly about that anymore. What we’re gonna talk about is finding bounding rect, min area rect, and enclosing circle of the ‘object’ in that image.

First let’s write code to find contours .

import cv2
import numpy as np

# read and scale down image

# threshold image
ret, threshed_img = cv2.threshold(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY),
127, 255, cv2.THRESH_BINARY)
# find contours and get the external one
image, contours, hier = cv2.findContours(threshed_img, cv2.RETR_EXTERNAL,
cv2.CHAIN_APPROX_SIMPLE)

cv2.drawContours(img, contours, -1, (255, 255, 0), 1)

cv2.imshow("contours", img)

ESC = 27
while True:
keycode = cv2.waitKey()
if keycode != -1:
keycode &amp;= 0xFF
if keycode == ESC:
break
cv2.destroyAllWindows()


There is a different here. Instead of retrieving all contours, we only retrieve the outermost contour. Here’s the result:

The contour wrap the ‘object’ is drawn in (255, 255, 0) color. The thickness is only 1, you can change the thickness by altering the last argument in cv2.drawContours().
Here’s how cv2.RETR_TREE will look like:

It’s time to find the bounding rect, min area rect, and min enclosing circle.

import cv2
import numpy as np

# read and scale down image

# threshold image
ret, threshed_img = cv2.threshold(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY),
127, 255, cv2.THRESH_BINARY)
# find contours and get the external one
image, contours, hier = cv2.findContours(threshed_img, cv2.RETR_TREE,
cv2.CHAIN_APPROX_SIMPLE)

# with each contour, draw boundingRect in green
# a minAreaRect in red and
# a minEnclosingCircle in blue
for c in contours:
# get the bounding rect
x, y, w, h = cv2.boundingRect(c)
# draw a green rectangle to visualize the bounding rect
cv2.rectangle(img, (x, y), (x+w, y+h), (0, 255, 0), 2)

# get the min area rect
rect = cv2.minAreaRect(c)
box = cv2.boxPoints(rect)
# convert all coordinates floating point values to int
box = np.int0(box)
# draw a red 'nghien' rectangle
cv2.drawContours(img, [box], 0, (0, 0, 255))

# finally, get the min enclosing circle
# convert all values to int
center = (int(x), int(y))
# and draw the circle in blue
img = cv2.circle(img, center, radius, (255, 0, 0), 2)

print(len(contours))
cv2.drawContours(img, contours, -1, (255, 255, 0), 1)

cv2.imshow("contours", img)

ESC = 27
while True:
keycode = cv2.waitKey()
if keycode != -1:
keycode &amp;= 0xFF
if keycode == ESC:
break
cv2.destroyAllWindows()


Use cv2.boundingRect to get the bounding rectangle (in green), cv2.minAreaRect to get the minimum area rectangle (in red), and cv2.minEnclosingCircle to get minimum enclosing circle (in blue).

Result:

More on contours, convex hull.

import cv2
import numpy as np

# threshold image
ret, threshed_img = cv2.threshold(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY),
127, 255, cv2.THRESH_BINARY)
# get contours from image
image, contours, hier = cv2.findContours(threshed_img, cv2.RETR_EXTERNAL,
cv2.CHAIN_APPROX_SIMPLE)

# for each contour
for cnt in contours:
# get convex hull
hull = cv2.convexHull(cnt)
# draw it in red color
cv2.drawContours(img, [hull], -1, (0, 0, 255), 1)

cv2.imshow("contours", img)

ESC = 27
while True:
keycode = cv2.waitKey(25)
if keycode != -1:
keycode &amp;= 0xFF
if keycode == ESC:
break

cv2.destroyAllWindows()


Result:

With the demonstration, you can figure out what ‘convex hull’ is.

Besides convex hull, there is one more thing you need to know is ‘approximate polygon’. I consider an approximate polygon is a basic shape of an object. In OpenCV, approximate bounding polygon can be calculated by using cv2.approxPolyDP. This method use Douglas-Peucker algorithm.

import numpy
import cv2

# threshold image
# this step is neccessary when you work with contours
ret, threshed_img = cv2.threshold(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY),
127, 255, cv2.THRESH_BINARY)
# find contours in image
image, contours, hier = cv2.findContours(threshed_img, cv2.RETR_EXTERNAL,
cv2.CHAIN_APPROX_SIMPLE)

for cnt in contours:
# calculate epsilon base on contour's perimeter
# contour's perimeter is returned by cv2.arcLength
epsilon = 0.01 * cv2.arcLength(cnt, True)
# get approx polygons
approx = cv2.approxPolyDP(cnt, epsilon, True)
# draw approx polygons
cv2.drawContours(img, [approx], -1, (0, 255, 0), 1)

# hull is convex shape as a polygon
hull = cv2.convexHull(cnt)
cv2.drawContours(img, [hull], -1, (0, 0, 255))

cv2.imshow('contours', img)
ESC = 27

while True:
keycode = cv2.waitKey()
if keycode != -1:
keycode &amp;= 0xFF
if keycode == ESC:
break

cv2.destroyAllWindows()


Result:

The approx bounding polygon is in green, and the convex hull is in red.

Again, you can find code example on OpenCV website, I post this because I want to share what I’ve learn. My explanations might be different than things that you get on opencv website, so you will not read the same thing twice.

• #### Ronald Wahome 1:01 am on November 9, 2017 Permalink | Reply

Really well explained better than the documentation as far as the approxPolyDP function goes. Thanks!

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r