Alex Balhatchet >
Algorithm-DependencySolver >
Algorithm::DependencySolver

Algorithm::DependencySolver - A dependency solver for scheduling access to a shared resource

version 1.00

use Algorithm::DependencySolver::Solver; use Algorithm::DependencySolver::Traversal; use Algorithm::DependencySolver::Operation; my @operations = ( Algorithm::DependencySolver::Operation->new( id => 1, depends => [qw(z)], affects => [qw(x)], prerequisites => ["3"], ), Algorithm::DependencySolver::Operation->new( id => 2, depends => [qw(x)], affects => [qw(y)], prerequisites => [], ), Algorithm::DependencySolver::Operation->new( id => 3, depends => [qw(y)], affects => [qw(z)], prerequisites => [], ), ); my $solver = Algorithm::DependencySolver::Solver->new(nodes => \@operations); $solver->to_png("pretty-graph.png"); my $traversal = Algorithm::DependencySolver::Traversal->new( Solver => $solver, visit => sub { my $operation = shift; print "Visited operation: ", $operation->id, "\n"; }, ); $traversal->run;

This dependency solver is somewhat different to the existing Algorithm::Dependency module.

Algorithm::Dependency creates a heirarchy where each node depends on a set of other nodes. In Algorithm::DependencySolver, there exists a set of operations and a set of resources, with a set of edges from operations to resources (the dependencies), and a set of edges from resources to operations (the affects). Given this input, the module outputs a directed acyclic graph (DAG) containing just the operations as its nodes.

Aditionally, Algorithm::DependencySolver allows for input which whould have resulted in a cyclic output graph to be resolved by means of explicit sequencing. This is done by marking nodes as depending on other nodes. See Algorithm::DependencySolver::Operation::prerequisites.

Returns the dependency graph as a Graph object. Note that only operations are included in the graph, not resources. This is of most use to the Algorithm::DependencySolver::Traversal module, and the `to_dot`

and `to_png`

methods.

$self->_remove_redundancy($G); # Ignore the return value

Applied to a graph object, removes redundant edges. An edge is redundant if it can be removed without invalidating the graph.

The fundamental law of the dependency graph is that a node can only be traversed when all of its predecessors have been traversed.

Given some node, `$n`

, and a predecessor of `$n`

, `$a`

, then it is safe to remove `$a`

if and only if another node exists, `$b`

, which is a predecessor of `$n`

, and there is a path from `$a`

to `$b`

(i.e., traversal of `$b`

requires that `$a`

has been visited).

Note that cycles may cause this algorithm to behave unexpectedly (depending on what one expects). Consider what happens if `$n`

has two successors, `$a`

and `$b`

, such that there is a cycle between `$a`

and `$b`

(i.e., there is an edge from `$a`

to `$b`

, and vice-versa). Suppose that the edge from `$n`

to `$a`

has been removed. Can the edge from `$n`

to `$b`

safely be removed?

Using the algorithm described above, yes! This is because there is another path from `$n`

to `$b`

: `$n -> $b -> $a -> b`

. We can, of course, detect such occurrences; however, I choose not to, because it's not clear to me what the most elegant result should be in these situations. Semantically, it does not matter whether the edge from `$n`

to the `$a,$b`

-cycle is from `$n`

to `$a`

, or `$n`

to `$b`

. Which should it be? Both, or one-or-the-other (presumably decided arbitrarily)?

Properties:

* This method can be safely called on cyclic graphs (i.e., it will not enter a non-terminating loop)

* This method will not fail early if a cycle is encountered (i.e., it will do as much work as it can, even though the graph is probably invalid)

* If `_apply_orderings`

is to be called on the graph object, it *must* be done *before* calling `_remove_redundancy`

$solver->to_png($file)

Outputs a dependency graph (showing only operations) to the given file in PNG format

$solver->to_dot($file)

Outputs a dependency graph (showing only operations) to the given file in Graphviz's dot format

syntax highlighting: