Topological sort: Difference between revisions
Content added Content deleted
(CoffeeScript) |
(adding fortran 77) |
||
Line 648: | Line 648: | ||
Output: <code>["std", "synopsys", "ieee", "dware", "gtech", "ramlib", "std_cell_lib", "dw02", "dw05", "dw06", "dw07", "dw01", "des_system_lib", "dw03", "dw04"]</code> |
Output: <code>["std", "synopsys", "ieee", "dware", "gtech", "ramlib", "std_cell_lib", "dw02", "dw05", "dw06", "dw07", "dw01", "des_system_lib", "dw03", "dw04"]</code> |
||
=={{header|Fortran}}== |
|||
===FORTRAN 77=== |
|||
Main routine for topological sort. |
|||
''Input'' : IDEP is an array ND x 2 of dependencies, with IDEP(I,1) depending on IDEP(I,2). |
|||
NL is the number of libraries to sort, ND the number of dependencies, one for each pair of ordered libraries. |
|||
Array IPOS is used internally by the routine, to maintain a list of positions of libraries in IORD. |
|||
''Output'' : IORD(1:NO) is the compile order, and IORD(NO+1:NL) contains unordered libraries. |
|||
This implementation is not optimal: for each ''level'' of dependency (for example A -> B -> C counts has two levels), there is a loop through all dependencies in IDEP. It would be possible to optimize a bit, without changing the main idea, by first sorting IDEP according to first column, and using more temporary space, keeping track of where is located data in IDEP for each library (all dependencies of a same library being grouped). |
|||
<lang fortran> 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</lang> |
|||
An example. Dependencies are encoded to make program shorter (in array ICODE). |
|||
<lang fortran> 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</lang> |
|||
Output: |
|||
<pre> |
|||
COMPILE ORDER |
|||
IEEE |
|||
STD |
|||
SYNOPSYS |
|||
STD_CELL_LIB |
|||
RAMLIB |
|||
GTECH |
|||
DWARE |
|||
DW07 |
|||
DW06 |
|||
DW05 |
|||
DW02 |
|||
DW01 |
|||
DW04 |
|||
DW03 |
|||
DES_SYSTEM_LIB |
|||
UNORDERED LIBRARIES |
|||
</pre> |
|||
Output with alternate input (DW01 depends also on DW04): |
|||
<pre> |
|||
COMPILE ORDER |
|||
IEEE |
|||
STD |
|||
SYNOPSYS |
|||
STD_CELL_LIB |
|||
RAMLIB |
|||
GTECH |
|||
DWARE |
|||
DW07 |
|||
DW06 |
|||
DW05 |
|||
DW02 |
|||
UNORDERED LIBRARIES |
|||
DW04 |
|||
DW03 |
|||
DW01 |
|||
DES_SYSTEM_LIB |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
A straightforward solution, for ease of understanding rather than execution speed. |
A straightforward solution, for ease of understanding rather than execution speed. |