OT: Genetic Algorithm Recipe Bug Fix

[Anton Vredegoor]

John Hunter <jdhunter at ace.bsd.uchicago.edu> wrote:

>    Anton> http://home.hccnet.nl/a.vredegoor/twomax
>
>Hmm, now if I can only figure out what it all means :-)

Me too. A friend of mine showed me that it's really a bipartite graph
optimization problem and that it's in NP because it's harder than the
maximum clique problem. Go figure :-)

Anyway it seems to be possible to solve a maximum clique problem like
this:

- start with a graph containing your clique problem
- copy the graph and color the original nodes white and the nodes of
the copy black
- connect the two graphs by drawing lines between black and white
nodes that originate from the same node, and between black and white
nodes where the original graph had a line between the original nodes.
- make a matrix where the rows represent black nodes and the columns
represent white nodes and where a "1" is in the matrix if there's a
line between two nodes

You now should have a matrix with ones on the diagonal and which is
symmetric along the diagonal.

Solve the matrix using the code above (I did some back porting to
Python22)

Look at the columns that are kept, it should be the nodes of a maximum
clique.

Is anybody still with me? I'd like to know if anyone can reproduce
this result or understand my explanation (I'm just repeating what I
saw on the blackboard)

Anton