Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW

A fast DAG class needed

by lima1 (Curate)
on Nov 16, 2007 at 13:59 UTC ( #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:
package DAG; use strict; use warnings; use Graph::Directed; use Carp; use base 'Graph::Directed'; sub new { my ( $self, %args ) = @_; $args{multiedged} = 1; my $obj = $self->SUPER::new(%args); return $obj; } sub set_parents { my ( $self, $p1, $p2, $c, $checks ) = @_; $checks ||=1; if ( ( $self->in_degree($c) || 0) > 0) { croak "already has parents"; } $self->add_edge_by_id($p1, $c, 1); $self->add_edge_by_id($p2, $c, 2); if ($checks && !$self->is_dag()) { $self->delete_edge_by_id($p1, $c, 1); $self->delete_edge_by_id($p2, $c, 2); croak 'Not a DAG anymore'; } return $self; }
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:
... sub is_ancestor { my ( $self, $v1, $v2 ) = @_; for my $child ( $self->get_successors($v1) ) { return 1 if $child eq $v2; } for my $child ( $self->get_successors($v1) ) { my $found = $self->is_ancestor( $child, $v2 ); return 1 if $found; } return 0; } sub set_parents { my ( $self, $p1, $p2, $c, $checks ) = @_; $checks ||=1; if ( ( $self->in_degree($c) || 0) > 0) { croak "already has parents"; } $self->add_edge_by_id($p1, $c, 1); if ($checks && $self->is_ancestor($c, $p1)) { $self->delete_edge_by_id($p1, $c, 1); croak 'Not a DAG anymore'; } $self->add_edge_by_id($p2, $c, 2); if ($checks && $p1 ne $p2 && $self->is_ancestor($c, $p2)) { $self->delete_edge_by_id($p2, $c, 2); croak 'Not a DAG anymore'; } return $self; }
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:

P1 --+ +--> Child P2 --+
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.

Replies are listed 'Best First'.
Re: A fast DAG class needed
by dwm042 (Priest) on Nov 16, 2007 at 16:00 UTC
    I suspect that what you want is called a spanning tree on a directed graph. There are some fast algorithms for finding spanning trees. The best intro discussion I can find quickly is the Wikipedia article on minimum spanning trees which will give you a place to start. I also think the book Mastering Algorithms in Perl touches these topics.

    Update: Now, if my gut instinct is wrong and you actually want every possible *tree* associated with a directed graph, then you have to know that the number of trees grows so rapidly as a function of the number of nodes that you're in for a time intensive process regardless.

    Update 2: Argh, totally off base here. DAGs aren't necessarily rooted, as trees are.

Re: A fast DAG class needed
by perlfan (Vicar) on Nov 16, 2007 at 21:20 UTC
    Can you be a little more clear about what you want to do? There are a lot of graph geeks here, so the more details the better ;-)

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://651202]
Approved by grep
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (4)
As of 2021-04-15 06:07 GMT
Find Nodes?
    Voting Booth?

    No recent polls found