Description
A module-dependency pair is of the form MOD1,MOD2, which means:
  • MOD1 is dependent on MOD2; therefore
  • MOD2 must be installed before MOD1.
The input data is a list of module-dependency pairs, where
  • two adjacent pairs are separated by exactly one space, and
  • the list does not contain leading or trailing blanks.
  • For example, B,D A,B A,C A,D C,E C,F E,G F,H G,H is a dependency-pair list.
To find an order to install modules in a list without violating the dependencies, the following iteration repeats:
  • Search the list for the modules can be installed directly, i.e., NOT dependent on others.
  • Print these modules, then remove them from the list.
This script is divided into two stages:
Stage1
  • If a module is the first one of some pair, then it depends on the second one. It can NOT be installed directly.
  • This stage excludes them from the modules of the list by
    • First remove the first module of every dependency-pair.
    • The result may contain several instances of some modules. We have to remove these duplicates.
Raw Input Desired Output 
B,D A,B A,C A,D C,E C,F E,G F,H G,H

D B C E F G H
Script 
[ 1] h
[ 2] s/( |^)[^ ,]+,/\1/g
[ 3] s/^/\n/
[ 4] :loop0
[ 5] s/\n([^ ]+)(( [^ ]+)*) \1( |$)/\n\1\2\4/
[ 6] t loop0
[ 7] s/\n([^ ]+ )/\1\n/
[ 8] /\n[^ ]*$/!b loop0
[ 9] s/\n//
Comments
  1. Step [1] saves the contents of PS to HS.
  2. Step [2] removes the first module of every dependency-pair, changing
    B,D A,B A,C A,D C,E C,F E,G F,H G,H to D B C E F G H.
    After Step [2], PS matches ^[^ ]+([^ ]+)$.
    Note that there are duplicates in this case, which should be removed.
  3. To remove duplicates, we first take the leftmost non-examined module, then check where there exists any other instance behind it:
    • Step [3] prepends to PS a newline character which is used as a mark. We choose the module immediately after the mark to remove any duplicate of it.
    • The mark also divides PS into two parts with examined modules in the first part and non-examined modules in the second one.
    • Steps [4] thru [6] constitute a loop which removes any module that is the same as the one immediately following mark. The preceding blank is also removed.
    • When all duplicates of the module being examined have been removed, Step [7] moves the mark next to the leftmost non-examined module, then Step [8] jumps back to Step [4] if there are at least two non-examined modules.
    • Step [9] removes the mark.
Stage2
  • The result of feeding B,D A,B A,C A,D C,E C,F E,G F,H G,H to the first stage is D B C E F G H.
  • Then we have to check each module of it with the original list to find modules not depending on others, i.e., not the first modules of some pairs.
  • For example, check D B C E F G H against
    B,D A,B A,C A,D C,E C,F E,G F,H G,H, modules can be installed directly are D and H.
Script 
[10] G
[11] s/^/\n/
[12] :loop1
[13] /\n([^ \n]+)( [^\n]+|)\n(.* |)\1,/{
[14] s/\n([^ \n]+ ?)/\n/
[15] /\n\n/!b loop1
[16] }
[17] :loop2
[18] s/(\n([^ ]+)( [^ ]+)*\n(.*[ ,]|))\2( |$)/\1\5/
[19] t loop2
[20] s/\n([^ \n]+ ?)/\1\n/
[21] /\n\n/!b loop1
[22] s/ +/ /g
[23] s/\n /\n/
[24] s/ $//
[25] s/,( |$)/\1/g
[26] s/\n//
[27] P
[28] /\n$/d
[29] D
Comments
  1. Step [10] appends the list saved in Step [1] to PS.
  2. Step [11] prepends to PS a newline character which is used as a mark. The function of the mark is similar with that one introduced in Step [3].
  3. After Step [11], PS are divided into three parts by two newline characters:
    • the first part contained qualified modules,
    • the second part contained non-examined modules, and
    • the third part is the dependency-pair list.
  4. If the module being examined is found to be the first one of some pair,
    • RE of Step [13] will match, and
    • that module is NOT what we want; therefore, Step [14] removes that module from the second part.
    • Step [15] makes sed jump back to Step [11] if there exists a non-examined module.
  5. Otherwise, the module being examined is qualified,
    • We have to remove from the third part(the dependency list) every instance of it. This is done via a loop consisting of Steps [17] thru [19].
    • Note that a qualified module may be the second one of some pair or sits alone. For example, after installing module D and H, and removing them from the list, the list becomes
      B A,B A,C A C,E C,F E,G F G.
    • Step [20] moves the module from the second part to the first one.
    • If there exists a non-examined module in the second part, Step [21] makes sed jump back to Step [12].
  6. The redundant blanks and commas are taken care by Steps [22] thru [24], and Step [25], respectively.
  7. Then PS contains
    • The modules can be installed directly,
    • followed by two newline characters: the first one is the mark, and the second one is inserted by `G' of Step [10], and
    • a dependency list for the next iteration.