Question:
Algorithm to determine the depth of a comparison network
Mr. Johnson draws an n-input comparison network with m comparators according to the following conventions.
The lines of the network go left-to-right, and comparators are drawn vertically to connect two lines. The network is drawn on an underlying grid, so that each comparator occupies one of at most m columns. Comparators can share columns, but they do not overlap.
Mr. Johnson represents a given drawing as a list L of triples, in which each triple (x, y, c) represents a comparator connecting line x to line y in column c.
Describe an efficient algorithm to determine the depth of a comparison network, where the input is Mr. Johnson's representation of a drawing of the network. Analyze your algorithm in terms of m and n.
Please look at the attachment for an example of his drawing and representation of a 4-input sorting network.