Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re: decomposing binary matrices (2)

by blokhead (Monsignor)
on Feb 27, 2007 at 19:08 UTC ( #602374=note: print w/replies, xml ) Need Help??


in reply to decomposing binary matrices (2)

If you look at this problem in terms of bipartite matchings (see Re: decomposing binary matrices), then your clean routine is simply removing edges that are never used in any maximum matching (a graph theorist would say: a matching that saturates your set of variables). An efficient way to check this is the following: To check if an edge (u,v) is used in some matching, remove (nodes) u & v from the graph and see if the remaining graph has a maximum matching. I think this is essentially what you are doing, but I'm not sure.

Now, checking a graph for a maximum matching can be done efficiently (see for example http://www.maths.lse.ac.uk/Courses/MA314/matching.pdf). Well, at least much more efficiently than how you have been doing it by trying all possible solutions. Overall, this process for clean would be something like cubic time in the size of your matrix.

I'm away from a perl interpreter at the moment, but can maybe offer something a little more concrete later. Unfortunately, Graph doesn't have any pre-packaged thingy for finding matchings.

blokhead

Replies are listed 'Best First'.
Re^2: decomposing binary matrices (2)
by hv (Parson) on Feb 27, 2007 at 21:01 UTC

    Ah yes, I think I understand - I'd looked at the perfect match algorithm before, but discarded it then because at the time I was trying to solve the splitting problem for which I needed specifically a cycle, and it looked like extending the algorithm to require a cycle was going to degenerate it into something no better than the brute force.

    If I'm no longer looking for a cycle, then I can probably use that algorithm. I'll give it a go, and come back.

    Update: I *do* understand now. I had read your approach as "to check the edge uv, remove the edge and check ...", but eventually worked out that couldn't be right, that I had to remove the two vertices instead.

    What's more, thinking about it in the graph form it is clear to me that after cleanup the split also becomes trivial - the graph simply falls apart into disconnected subgraphs.

    Thanks,

    Hugo

Re^2: decomposing binary matrices (2)
by hv (Parson) on Feb 28, 2007 at 09:22 UTC

    Excellent, it works. :)

    The code below demonstrates and tests the cleanup() method and its dependencies - the rest is just a minimal hack to wrap a test harness around it. I also hacked in %rev at the last minute when I realised %$assign was the wrong way round for my needs, I still need to refactor that.

    Thanks very much for your help,

    Hugo

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://602374]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (3)
As of 2021-10-20 12:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My first memorable Perl project was:







    Results (81 votes). Check out past polls.

    Notices?