++ed by:
Alex Balhatchet
and 1 contributors

# NAME

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

version 1.01

# SYNOPSIS

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

# DESCRIPTION

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.

# METHODS

## get_Graph

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.

## _remove_redundancy

``  \$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 -&gt; \$b -&gt; \$a -&gt; 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`

## to_png

``  \$solver->to_png(\$file)``

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

## to_dot

``  \$solver->to_dot(\$file)``

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