On Nov 14, 2007 12:24 PM, Chas. Owens <[EMAIL PROTECTED]> wrote:
> On Nov 13, 2007 8:13 PM, vijay <[EMAIL PROTECTED]> wrote:
> > I am trying to use Graph::Directed to test if a structure is a DAG or
> > a tree. There is a simple method to test whether the graph is a DAG.
> > However, I could not find a way to test if it is a tree.
> snip
>
> If my understanding of the graph data structure is correct you should
> be ably to test for whether a graph is a tree or not like this
snip
I am an idiot, the grep in the previous code was wasteful.
package Graph;
sub is_tree {
my $self = shift;
#The graph is not a DAG, therefore it can't be a tree
return 0 unless $self->is_dag;
#At least one vertex is not connected to the rest of the graph
return 0 unless $self->is_weakly_connected;
#At least one vertex is pointed to by more than one vertex
my %vertices;
for my $e ($self->edges) {
$vertices{$e->[1]}++;
return 0 if $vertices{$e->[1]} > 1;
}
#the graph is a tree
return 1;
}
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
http://learn.perl.org/
