Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Dependency Inference

by PetaMem (Priest)
on Jul 12, 2005 at 15:46 UTC ( #474300=perlquestion: print w/ replies, xml ) Need Help??
PetaMem has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks,

this might be rather an algorithmic question instead of a perl-specific one, but then again, I need the solution to be implemented in Perl, so...

Given a set of things - say Objects - how do I best represent and infer dependencies between them. E.g.:

X ----- Y --+-- Z | ,-- 5 ----+-- O | / | 1 ----- 2 --+-- 3 --+ | | | | +-- 4 | | | | | | A --+-- E --+-- G --+-- H --+ B --+ | F --+
The above is just a visualization of some facts like "Y requires X", "Z requires Y and 2", "H requires G and 3" and so on. Also, the other way round "3 allows for 5 and H",

basically every member of this graph should be able to say what he requires or what he allows for. My questions are:

Any suitable object to represent this already available at CPAN? This reminds me of the module dependencies so there should be an implementation already.

What is the best way to declare such dependencies? Similar to @ISA when declaring inheritance?

Thanks for sharing your thoughts on this.

Bye
 PetaMem
    All Perl:   MT, NLP, NLU

Comment on Dependency Inference
Download Code
Re: Dependency Inference
by derby (Abbot) on Jul 12, 2005 at 16:08 UTC

    Perl really doesn't declare inheritance (in the classical sense). The @ISA array tells perl what other symbol tables to look at when the called method isn't in the current package.

    For your purposes, you could use a plain old hash with lots of references and magic strings or you could use one of the numerous Tree packages.

    -derby
Re: Dependency Inference
by kvale (Monsignor) on Jul 12, 2005 at 16:09 UTC
    What you are describing is mathematically a directed graph and can be represented in Perl as a Graph object using the module Graph. That module also has a number of methods for processing graphs. For instance, one could do a topological sort to establish the hierarchy of dependencies.
    use Graph::Directed; my $g = Graph::Directed->new; # A directed graph. $g->add_edge(...); $g->add_vertex(...); $g->vertices(...) $g->edges(...) my @ts = $g->topological_sort;

    For modules in particular, check out Module::Dependency for useful methods.

    -Mark

Re: Dependency Inference
by tlm (Prior) on Jul 12, 2005 at 23:53 UTC

    Basically the set of dependencies is (or should be) a directed acyclic graph. One does what's called a "topological sort" to determine the proper ordering of the nodes (it's nothing more than a post-ordering in a depth-first traversal). Take a look at Algorithm::Dependency.

    A standard approach to represent dependencies is to do list the "target" followed by all the items it directoy depends on. E.g.

    myapp foo.o bar.o baz.o
    Both A::D and make use this basic idea.

    the lowliest monk

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://474300]
Approved by Limbic~Region
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (5)
As of 2014-08-29 04:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (275 votes), past polls