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

Published on 12 May 2024 09:40 PM

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

Source code in the fortran programming language

      SUBROUTINE TSORT(NL,ND,IDEP,IORD,IPOS,NO)
      IMPLICIT NONE
      INTEGER NL,ND,NO,IDEP(ND,2),IORD(NL),IPOS(NL),I,J,K,IL,IR,IPL,IPR
      DO 10 I=1,NL
      IORD(I)=I
   10 IPOS(I)=I
      K=1
   20 J=K
      K=NL+1
      DO 30 I=1,ND
      IL=IDEP(I,1)
      IR=IDEP(I,2)
      IPL=IPOS(IL)
      IPR=IPOS(IR)
      IF(IL.EQ.IR .OR. IPL.GE.K .OR. IPL.LT.J .OR. IPR.LT.J) GO TO 30
      K=K-1
      IPOS(IORD(K))=IPL
      IPOS(IL)=K
      IORD(IPL)=IORD(K)
      IORD(K)=IL
   30 CONTINUE
      IF(K.GT.J) GO TO 20
      NO=J-1
      END


      PROGRAM EX_TSORT
      IMPLICIT NONE
      INTEGER NL,ND,NC,NO,IDEP,IORD,IPOS,ICODE,I,J,IL,IR
      PARAMETER(NL=15,ND=44,NC=69)
      CHARACTER*(20) LABEL
      DIMENSION IDEP(ND,2),LABEL(NL),IORD(NL),IPOS(NL),ICODE(NC)
      DATA LABEL/'DES_SYSTEM_LIB','DW01','DW02','DW03','DW04','DW05',
     1 'DW06','DW07','DWARE','GTECH','RAMLIB','STD_CELL_LIB','SYNOPSYS',
     2 'STD','IEEE'/
      DATA ICODE/1,14,13,12,1,3,2,11,15,0,2,15,2,9,10,0,3,15,3,9,0,4,14,
     213,9,4,3,2,15,10,0,5,5,15,2,9,10,0,6,6,15,9,0,7,7,15,9,0,8,15,9,0,
     39,15,9,0,10,15,10,0,11,14,15,0,12,15,12,0,0/

C DECODE DEPENDENCIES AND BUILD IDEP ARRAY
      I=0
      J=0
   10 I=I+1
      IL=ICODE(I)
      IF(IL.EQ.0) GO TO 30
   20 I=I+1
      IR=ICODE(I)
      IF(IR.EQ.0) GO TO 10
      J=J+1
      IDEP(J,1)=IL
      IDEP(J,2)=IR
      GO TO 20
   30 CONTINUE

C SORT LIBRARIES ACCORDING TO DEPENDENCIES (TOPOLOGICAL SORT)
      CALL TSORT(NL,ND,IDEP,IORD,IPOS,NO)

      PRINT*,'COMPILE ORDER'
      DO 40 I=1,NO
   40 PRINT*,LABEL(IORD(I))
      PRINT*,'UNORDERED LIBRARIES'
      DO 50 I=NO+1,NL
   50 PRINT*,LABEL(IORD(I))
      END


subroutine tsort(nl,nd,idep,iord,no)

  implicit none
  
  integer,intent(in) :: nl
  integer,intent(in) :: nd
  integer,dimension(nd,2),intent(in) :: idep
  integer,dimension(nl),intent(out) :: iord
  integer,intent(out) :: no
  
  integer :: i,j,k,il,ir,ipl,ipr,ipos(nl)
  
  do i=1,nl
    iord(i)=i
    ipos(i)=i
  end do
  k=1
  do
    j=k
    k=nl+1
    do i=1,nd
      il=idep(i,1)
      ir=idep(i,2)
      ipl=ipos(il)
      ipr=ipos(ir)
      if (il==ir .or. ipl>=k .or. ipl<j .or. ipr<j) cycle
      k=k-1
      ipos(iord(k))=ipl
      ipos(il)=k
      iord(ipl)=iord(k)
      iord(k)=il
    end do
    if (k<=j) exit
  end do
  no=j-1

end subroutine tsort


  

You may also check:How to resolve the algorithm Monte Carlo methods step by step in the Go programming language
You may also check:How to resolve the algorithm Ackermann function step by step in the 8th programming language
You may also check:How to resolve the algorithm User input/Text step by step in the R programming language
You may also check:How to resolve the algorithm User input/Text step by step in the Racket programming language
You may also check:How to resolve the algorithm Taxicab numbers step by step in the PureBasic programming language