We don't bite newbies here... much | |
PerlMonks |
Re: Determine group membership for partial sequencesby Anno (Deacon) |
on Aug 23, 2007 at 22:09 UTC ( [id://634743]=note: print w/replies, xml ) | Need Help?? |
It appears that what you are after is a relation among the nodes such that two nodes are related if one overlays the other, directly or indirectly (or if the nodes are identical). Direct overlay is what is stated in the data. The indirect relations can be described as the transitive closure of the relation of immediate overlays. The desired chains would be the equivalence classes of this extended relationship.
Fortunately, there is a module (by Abigail) that implements transitive closure. It is the work-horse of the following solution: The %graph hash is built much like %overlays in your code, except that both ascending and descending pairs are considered related. After the Floyd-Marshall algortithm has built the closure, the groups can be pulled off one by one. The resulting output shows indeed only one large group which contains the spurious one that appeared in your output. Update: Come to think of it, what you're doing is determine the connected components of a graph. There are algorithms (and CPAN modules) that implement that directly. Using Floyd-Warshall in this way is possible, but probably less than optimal. Anno
In Section
Seekers of Perl Wisdom
|
|