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

Published on 12 May 2024 09:40 PM
#Python

How to resolve the algorithm Topological sort step by step in the Python 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 Python programming language

Explanation of the Source Code:

The provided source code is written in Python and performs topological sorting on a directed acyclic graph (DAG). Topological sorting is used to determine the order in which dependencies should be processed to avoid circular dependencies.

Implementation:

Function toposort2:

  • This function takes a dictionary data as input, where each key represents a dependency (e.g., a library or package) and the corresponding set of values represents the dependencies of that key.
  • It first removes self-dependencies from the dictionary.
  • Then, it identifies any extra items present in the dependencies that are not keys in the dictionary.
  • It updates the dictionary to include these extra items as keys with empty dependency sets.
  • It then enters a loop that iteratively identifies nodes with no dependencies, adds them to a sorted order, and deletes them from the dictionary.
  • If no nodes with no dependencies are found, it breaks out of the loop and checks for any remaining dependencies, failing if a cycle is detected.

Function TopologicalSorter:

  • This function is from the graphlib module and provides an alternative implementation of topological sorting.
  • It takes the same dictionary data as input.
  • It ignores self-dependencies and identifies extra items as done in toposort2.
  • It returns a static order of the dependencies.

Usage:

  • The source code includes two examples of using topological sorting.
  • In the first example, the toposort2 function is used to sort the data dictionary, and the result is printed as a list of sorted nodes separated by newlines.
  • In the second example, the TopologicalSorter from graphlib is used to sort the data dictionary, and the result is printed as a tuple of sorted nodes.

Output:

The output of the code will be a sorted list or tuple of dependencies, with each line or element representing a layer of dependencies. The order ensures that dependencies are processed before the items that depend on them.

Note: The reduce function used in toposort2 is deprecated in Python 3 and should be replaced with functools.reduce.

Source code in the python programming language

try:
    from functools import reduce
except:
    pass

data = {
    'des_system_lib':   set('std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee'.split()),
    'dw01':             set('ieee dw01 dware gtech'.split()),
    'dw02':             set('ieee dw02 dware'.split()),
    'dw03':             set('std synopsys dware dw03 dw02 dw01 ieee gtech'.split()),
    'dw04':             set('dw04 ieee dw01 dware gtech'.split()),
    'dw05':             set('dw05 ieee dware'.split()),
    'dw06':             set('dw06 ieee dware'.split()),
    'dw07':             set('ieee dware'.split()),
    'dware':            set('ieee dware'.split()),
    'gtech':            set('ieee gtech'.split()),
    'ramlib':           set('std ieee'.split()),
    'std_cell_lib':     set('ieee std_cell_lib'.split()),
    'synopsys':         set(),
    }

def toposort2(data):
    for k, v in data.items():
        v.discard(k) # Ignore self dependencies
    extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys())
    data.update({item:set() for item in extra_items_in_deps})
    while True:
        ordered = set(item for item,dep in data.items() if not dep)
        if not ordered:
            break
        yield ' '.join(sorted(ordered))
        data = {item: (dep - ordered) for item,dep in data.items()
                if item not in ordered}
    assert not data, "A cyclic dependency exists amongst %r" % data

print ('\n'.join( toposort2(data) ))


from graphlib import TopologicalSorter

#   LIBRARY     mapped_to   LIBRARY DEPENDENCIES
data = {
    'des_system_lib':   set('std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee'.split()),
    'dw01':             set('ieee dw01 dware gtech'.split()),
    'dw02':             set('ieee dw02 dware'.split()),
    'dw03':             set('std synopsys dware dw03 dw02 dw01 ieee gtech'.split()),
    'dw04':             set('dw04 ieee dw01 dware gtech'.split()),
    'dw05':             set('dw05 ieee dware'.split()),
    'dw06':             set('dw06 ieee dware'.split()),
    'dw07':             set('ieee dware'.split()),
    'dware':            set('ieee dware'.split()),
    'gtech':            set('ieee gtech'.split()),
    'ramlib':           set('std ieee'.split()),
    'std_cell_lib':     set('ieee std_cell_lib'.split()),
    'synopsys':         set(),
    }
# Ignore self dependencies
for k, v in data.items():
    v.discard(k)   

ts = TopologicalSorter(data)
print(tuple(ts.static_order()))

You may also check:How to resolve the algorithm Determine sentence type step by step in the Go programming language
You may also check:How to resolve the algorithm Character codes step by step in the ABAP programming language
You may also check:How to resolve the algorithm Find if a point is within a triangle step by step in the Java programming language
You may also check:How to resolve the algorithm Associative array/Creation step by step in the Raku programming language
You may also check:How to resolve the algorithm Sorting algorithms/Insertion sort step by step in the Erlang programming language