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
#!/usr/bin/perl
use warnings;
use strict;
use Graph;
my $tree = Graph->new;
$tree->add_edge("d", "b");
$tree->add_edge("b", "a");
$tree->add_edge("b", "c");
$tree->add_edge("d", "f");
$tree->add_edge("f", "e");
$tree->add_edge("f", "g");
print "is tree: (should be 1) ", $tree->is_tree, "\n";
$tree->add_vertex('h');
print "is tree: (should be 0) ", $tree->is_tree, "\n";
$tree->delete_vertex('h');
print "is tree: (should be 1) ", $tree->is_tree, "\n";
$tree->add_edge('b', 'g');
print "is tree: (should be 0) ", $tree->is_tree, "\n";
$tree->delete_edge('b', 'g');
print "is tree (should be 1): ", $tree->is_tree, "\n";
$tree->add_edge('y', 'z');
print "is tree (should be 0): ", $tree->is_tree, "\n";
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;
my %vertices;
for my $e ($self->edges) {
$vertices{$e->[1]}++;
}
#At least one vertex that is pointed to by more than one vertex
return 0 if grep { $_ > 1 } values %vertices;
#the graph is a tree
return 1;
}
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
http://learn.perl.org/
