How to resolve the algorithm Topological sort step by step in the Perl programming language

Published on 12 May 2024 09:40 PM
#Perl

How to resolve the algorithm Topological sort step by step in the Perl programming language

Table of Contents

Problem Statement

Given a mapping between items, and items they depend on, a topological sort orders items so that no item precedes an item it depends upon. The compiling of a library in the VHDL language has the constraint that a library must be compiled after any library it depends on. A tool exists that extracts library dependencies.

Write a function that will return a valid compile order of VHDL libraries from their dependencies.

Use the following data as an example:

Note: the above data would be un-orderable if, for example, dw04 is added to the list of dependencies of dw01.

There are two popular algorithms for topological sorting:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Topological sort step by step in the Perl programming language

Source code in the perl programming language

sub print_topo_sort {
    my %deps = @_;

    my %ba;
    while ( my ( $before, $afters_aref ) = each %deps ) {
        for my $after ( @{ $afters_aref } ) {
            $ba{$before}{$after} = 1 if $before ne $after;
            $ba{$after} ||= {};
        }
    }

    while ( my @afters = sort grep { ! %{ $ba{$_} } } keys %ba ) {
        print "@afters\n";
        delete @ba{@afters};
        delete @{$_}{@afters} for values %ba;
    }

    print !!%ba ? "Cycle found! ". join( ' ', sort keys %ba ). "\n" : "---\n";
}

my %deps = (
    des_system_lib => [qw( std synopsys std_cell_lib des_system_lib dw02
                                                        dw01 ramlib ieee )],
    dw01           => [qw( ieee dw01 dware gtech                         )],
    dw02           => [qw( ieee dw02 dware                               )],
    dw03           => [qw( std synopsys dware dw03 dw02 dw01 ieee gtech  )],
    dw04           => [qw( dw04 ieee dw01 dware gtech                    )],
    dw05           => [qw( dw05 ieee dware                               )],
    dw06           => [qw( dw06 ieee dware                               )],
    dw07           => [qw( ieee dware                                    )],
    dware          => [qw( ieee dware                                    )],
    gtech          => [qw( ieee gtech                                    )],
    ramlib         => [qw( std ieee                                      )],
    std_cell_lib   => [qw( ieee std_cell_lib                             )],
    synopsys       => [qw(                                               )],
);
print_topo_sort(%deps);
push @{ $deps{'dw01'} }, 'dw04'; # Add unresolvable dependency
print_topo_sort(%deps);

You may also check:How to resolve the algorithm Detect division by zero step by step in the Stata programming language
You may also check:How to resolve the algorithm Semordnilap step by step in the VBScript programming language
You may also check:How to resolve the algorithm The sieve of Sundaram step by step in the Amazing Hopper programming language
You may also check:How to resolve the algorithm Sum of squares step by step in the CoffeeScript programming language
You may also check:How to resolve the algorithm Loops/N plus one half step by step in the Euphoria programming language