view release on metacpan or  search on metacpan

lib/Algorithm/DependencySolver/Solver.pm  view on Meta::CPAN

        return \%r;
    } else {
        return;
    }
}

# Safe to call on cyclic graphs. Will not fail early if cycle
# encountered
method _apply_orderings($G) {

    for my $nodeB (@{$self->get_nodes}) {
        for my $nodeA_id (@{$nodeB->prerequisites}) {
            my %seen;
            my $recurse;
            $recurse = sub {
                my $node_id = shift;
                return if $seen{$node_id}++;
                for my $to_id ($G->successors($node_id)) {
                    if ($to_id eq $nodeA_id) {
                        $G->delete_edge($node_id, $to_id);
                    }
                    else {
                        $recurse->($to_id);
                    }
                }
            };
            $recurse->($nodeB->id);
        }
    }
}

=head2 _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, C<$n>, and a predecessor of C<$n>, C<$a>, then it is
safe to remove C<$a> if and only if another node exists, C<$b>, which
is a predecessor of C<$n>, and there is a path from C<$a> to C<$b>
(i.e., traversal of C<$b> requires that C<$a> has been visited).

Note that cycles may cause this algorithm to behave unexpectedly
(depending on what one expects). Consider what happens if C<$n> has
two successors, C<$a> and C<$b>, such that there is a cycle between
C<$a> and C<$b> (i.e., there is an edge from C<$a> to C<$b>, and
vice-versa). Suppose that the edge from C<$n> to C<$a> has been
removed. Can the edge from C<$n> to C<$b> safely be removed?

Using the algorithm described above, yes! This is because there is
another path from C<$n> to C<$b>: C<$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 C<$n> to the C<$a,$b>-cycle is from C<$n> to C<$a>, or C<$n> to
C<$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 C<_apply_orderings> is to be called on the graph object, it
  I<must> be done I<before> calling C<_remove_redundancy>

=cut

method _remove_redundancy($G) {

    for my $node ($G->vertices) {
        for my $pred ($G->predecessors($node)) {
            next unless $G->has_edge($pred, $node);

            my @other_predecessors =
              grep { $_ ne $pred } $G->predecessors($node);

            my $other_paths_to_pred = grep {
                # Returns true only if the edge from $pred to $node can
                # safely be removed
                any { $_ eq $pred } $G->all_predecessors($_);
            } @other_predecessors;

            if ($other_paths_to_pred) {
                $G->delete_edge($pred, $node);
            }
        }
    }
}



method build_affects_index() {
    my %index;
    for my $node (@{$self->get_nodes}) {
        for my $resource (@{$node->affects}) {
            push @{$index{$resource}}, $node;
        }
    }
    return \%index;
}

method to_s() {
    return $self->get_GraphEasy->as_ascii();
}

=head2 to_png

  $solver->to_png($file)

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