There's more than one way to do things PerlMonks

### Dependency Inference

by PetaMem (Priest)
 on Jul 12, 2005 at 15:46 UTC 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

Replies are listed 'Best First'.
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->vertices(...)
\$g->edges(...)

my @ts = \$g->topological_sort;

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

-Mark

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 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

Create A New User
Domain Nodelet?
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 romping around the Monastery: (2)
As of 2022-12-04 22:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?