Do you know where your variables are? | |
PerlMonks |
A fast DAG class neededby lima1 (Curate) |
on Nov 16, 2007 at 13:59 UTC ( [id://651202]=perlquestion: print w/replies, xml ) | Need Help?? |
lima1 has asked for the wisdom of the Perl Monks concerning the following question:
My knowledge about Graphs is quite limited, so I hope this is an easy question for some of you: I need a class that only accepts DAGs (Directed Acyclic Graphs). Based on Graph, the easiest solution is:
I add always parents-child triples. So add_parents() ist just a method that adds two edges. This code is really slow. My current attempt is a simple breadth first search: Which is faster, but still too slow. Do you see how I could improve the performance? My goal is a simple random walk optimization, so I always remove the two incoming edges of a node and then add new ones. The number of nodes is between 100 and 700. Am I doing something wrong here? Should I use another Graph module as base? Update: Sorry for writing so unclear :( . What I now have is a big set of parents-child triples: I start with greedy adding triples to the graph until all nodes are added. Then I start a simple MCMC optimization in the way that I select randomly a node, remove the incoming edges if they exist and then add two new valid incoming edges (another triple where the selected node is a child). So I have a DAG, remove zero or two edges, add two new ones (both directing in the same node) and want that the class very quickly checks whether the two new edges have introduced a directed circle. With hundred nodes I get only about 50 iterations a second (without any scoring function). I am quite sure that there is a lot to improve. Update 2: Graph::edges is quite expensive. After removing this in my MCMC iterations,I get about 200 iterations a second, which is at least something I can live with.
Back to
Seekers of Perl Wisdom
|
|