Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re: decomposing binary matrices

by Herkum (Parson)
on Feb 16, 2007 at 14:10 UTC ( #600435=note: print w/replies, xml ) Need Help??


in reply to decomposing binary matrices

Have you take a look at Graph? If that does not help then you can get Mastering Algorithms with Perl. I got it recently and I found that it very accessible to someone who did not have much math knowledge (that would be me! :) ).

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

    Thanks, I tried drawing the graph on a piece of paper, and while I'm not yet sure I think it may be possible to say that: the graph for any undecomposable submatrix has a cycle that traverses all its nodes; and that: the nodes in the longest cycle form the largest undecomposable submatrix. Thus from the example in the OP, you can get cycles A-2-E-4-A and B-3-C-1-D-5-B, but there is no cycle looping through all 10 of the nodes.

    That does not immediately help, since Graph will only find "the first cycle" - I can't tell from the docs (nor from a brief look at the code), but I suspect that since all my edges are undirected, it will just immediately return (eg) A-2-A as a cycle - but this concept may well help me search for an algorithm.

    Update: this page tells me:

    Finding the longest cycle in a graph includes the special case of Hamiltonian cycle (see gif), so it is NP-complete.
    Damn.

    Hugo

      That was the reason I suggested the Mastering Algorithms with Perl book. It dealt quite a few algorithms and devotes a chapter to matrices. It also goes into great detail for several different methods for using Graph.

      Graph by itself is not very useful because it is expected that you know what your are doing, which I find frustrating when I encounter a problem. But there is a lot more to it than first appearances would suggest.

Log In?
Username:
Password:

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

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







    Results (85 votes). Check out past polls.

    Notices?