Optimization problem - finding a maximum

Question

I have a problem at hand which can be reduced to something like this :

Assume a bunch of random points in a two-dimension plane X-Y where for each Y, there could be multiple points on X and for each X, there could be multiple points on Y.

Whenever a point (Xi,Yi) is chosen, no other point with X = Xi OR Y = Yi can be chosen. We have to choose the maximum number of points.

Answer 1

This can be reduced to simple maximum flow problem. If you have a point (xi, yi), in graph it should be represented with path from source S to point xi, from xi to yi and from yi to the last node (sink) T.

Note, if we have points (2, 2) and (2, 5), there's still only one path from S to x2. All paths (edges) have capacity 1.

The flow in this network is the answer.

about general problem
http://en.wikipedia.org/wiki/Max_flow

update
I don't have graphic editor right now to visualise problem, but you can easily draw example by hand. Let's say, points are (3, 3) (3, 5) (2, 5)

Then edges (paths) would be
S -> x2, S -> x3
y3 -> T, y5 -> T
x3 -> y3, x3 -> y5, x2 -> y5

Flow: S -> x2 -> y5 -> T and S -> x3 -> y3 -> T
The amount of 'water' going from source to sink is 2 and so is the answer.

Also there's a tutorial about max flow algorithms
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow

Answer 2

Isn't this just the Hungarian algorithm?

Create an n×n matrix, with 0 at marked vertices, and 1 at unmarked vertices. The algorithm will choose n vertices, one for each row and column, which minimizes their sum. Simply count all the chosen vertices which equal 0, and you have your answer.

from munkres import Munkres

matrix = [[0, 0, 1],
          [0, 1, 1],
          [1, 0, 0]]

m = Munkres()
total = 0
for row, column in m.compute(matrix):
    if matrix[row][column] == 0:
        print '(%i, %i)' % (row, column)
        total += 1

print 'Total: %i' % total

This runs in O(n³) time, where n is the number of rows in the matrix. The maximum flow solution runs in O(V³), where V is the number of vertices. As long as there are more than n chosen intersections, this runs faster; in fact, it runs orders of magnitude faster, as the number of chosen vertices goes up.