in reply to Multi level dependency structure

Edit: dammit, I *just* saw that you can't install CPAN modules. Still, Graph.pm has no dependencies, so maybe there's a chance?

I've been there. What you need is a real directed graph structure. I'm not sure how it will handle a 120k edge graph, but I've put a sizeable subset of the CPAN dependency graph (our entire org's module dep graph, actually -- including the high level modules, web apps, etc. so DBIC and other heavyweight stuff) in a Graph.pm object.

It makes for extremely readable code too. Below is an example (not guaranteed to run, I don't have Perl on this machine):

use Graph::Directed;
my $graph = Graph::Directed->new;

# Building the graph.  In this example, edges are directed from a job 
+to a dependency.

while (my $line = $file->getline) {
    my ($job, @deps) = split(/,/, $line);
    foreach my $dep (@deps) {
        # adds both $job and $dep as nodes in the graph if they don't 
+exist already
        $graph->add_edge($job, $dep);
    }
}

# What does job FOO require?
say "FOO requires $_" foreach $graph->all_successors('FOO');

# Who requires FOO?
say "FOO is required by $_" foreach $graph->all_predecessors('FOO');

# Jobs that do not have prerequisites.
say "$_ can be executed right now!" foreach $graph->sink_vertices;

# Somebody messed up here:
say "A job requires itself!" if $graph->has_a_cycle;

[download]

It's really comfortable, and reading the POD for Graph.pm might give you lots of ideas of cool stuff to do with your dependency graph :)

Replies are listed 'Best First'.
Re^2: Multi level dependency structure
by VinsWorldcom (Prior) on Feb 12, 2016 at 02:52 UTC

    pokki, absolutely brilliant! ++ I needed to see this work myself and had Graph::Easy but couldn't duplicate. The CPAN install for Graph::Directed was easy (Win7 x64 / Strawberry 5.18.1) and I whipped this up based on your example:

    #!perl
use strict;
use warnings;
use Graph::Directed;
my $graph = Graph::Directed->new;

while ( my $line = <DATA> ) {
    chomp $line;
    my ( $job, @deps ) = split( /,/, $line );
    for my $dep (@deps) {
        $graph->add_edge( $job, $dep );
    }
}

for my $job ( sort ( $graph->vertices ) ) {
    print "$job requires ";
    for ( sort ( $graph->all_successors($job) ) ) {
        print "$_ ";
    }
    print "\n";
}

__DATA__
job1,
job2,job1,
job3,job2
job4,job2
job5,job2,job4
job6,jobz
joba,job4,jobb
jobz,jobbc,job2

    [download]

    and outputs

    job1 requires
job2 requires job1
job3 requires job1 job2
job4 requires job1 job2
job5 requires job1 job2 job4
job6 requires job1 job2 jobbc jobz
joba requires job1 job2 job4 jobb
jobb requires
jobbc requires
jobz requires job1 job2 jobbc

    [download]
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom