On Sat, Aug 7, 2010 at 09:36, Amit Saxena <learn.tech...@gmail.com> wrote:
snip
> The purpose of this activity is to model a hierarchical representation of
> dependent components, each of one will be represented as a service.
>
> I had a look at the Graph module (
> http://search.cpan.org/~jhi/Graph-0.94/lib/Graph.pod) but I am not sure how
> it can be used to implement multiple parent and multiple child
> implementation of a tree. In other words, I would like to have similar
> methods which are available in the "Tree" implementations in CPAN.
snip
A [tree][0] is a [Graph][1]. Often you will see trees implemented as
[Directed Acyclic Graphs][2] (or DAGs) because pointers or references
only flow one way. Here is an example using the [Graph][3] module:
#!/usr/bin/perl
use strict;
use warnings;
use Graph;
#FIXME: naive implementation, there may be a much better way to do this
sub run_in_parallel {
my $g = shift->copy;
while (my @v = $g->vertices) {
my @run = grep { $g->is_successorless_vertex($_) } @v;
print "running ", join(", ", @run), " in parallel\n";
for my $compenent (@run) {
$g->delete_vertex($compenent);
};
}
}
my $g = Graph->new;
my $f = Graph->new;
while (<DATA>) {
my ($component, @dependencies) = split;
unless ($g->has_vertex($component)) {
$g->add_vertex($component);
$f->add_vertex($component);
}
for my $dependency (@dependencies) {
unless ($g->has_vertex($dependency)) {
$g->add_vertex($dependency);
$f->add_vertex($dependency);
}
$g->add_edge($dependency, $component);
$f->add_edge($component, $dependency);
}
}
print "everything will work if you run the programs in this order: ",
join(", ", $g->topological_sort), "\n";
run_in_parallel($f);
#component dependency list
__DATA__
a b c d
b e
c f g
d
e
f
g
[0]: http://en.wikipedia.org/wiki/Tree_(graph_theory)
[1]: http://en.wikipedia.org/wiki/Graph_(mathematics)
[2]: http://en.wikipedia.org/wiki/Directed_acyclic_graph
[3]: http://search.cpan.org/dist/Graph/lib/Graph.pod
--
Chas. Owens
wonkden.net
The most important skill a programmer can have is the ability to read.
--
To unsubscribe, e-mail: beginners-unsubscr...@perl.org
For additional commands, e-mail: beginners-h...@perl.org
http://learn.perl.org/
