Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re: Reconciling multiple lists (similar to "merge" in CVS?)

by jdporter (Paladin)
on Jan 05, 2007 at 23:45 UTC ( [id://593227]=note: print w/replies, xml ) Need Help??


in reply to Reconciling multiple lists (similar to "merge" in CVS?)

The hard part in what you're talking about is determining an appropriate display order. Your example illustrates that the non-trivial case can occur. Therefore, you probably want a topological sort (e.g. by Sort::Topological or the topological_sort method of Graph) to generate an optimal order. Once you've done that, the rest is a cinch.

But just having topological sort doesn't solve all the problems. You first need to generate an appropriate DAG based on the input lists. You could build a graph, adding each input list, such that each edge in the input list increments the corresponding edge in the graph. When that's done, invert the weight (count) of each edge, and extract a minimum spanning tree (also provided by Graph) from the graph. Use that as the input to the topological sort.

A word spoken in Mind will reach its own level, in the objective world, by its own weight

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others goofing around in the Monastery: (8)
As of 2024-04-23 17:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found