Description
Given a dependency file where each line describes module(s) on which a give one depends. For example, in the following datafile,
  • D:A,F,C means module `D' depends on `A', `F' and `C'. Therefore, modules `A', `F' and `C' must be installed before `D'.
  • B: means module `B' does not depend on any other.
We divide the job into two stages:
  1. Figure out what modules do not depend on others.
    They are `B' and `H' in this case. The first script will generate B|H, which will be used as an ERE in the second stage .
  2. Remove those modules from the dependency lists.
    For example, transform F:B,E to F:E
Raw Input Desired Output 
D:A,F,C
C:H
F:B,E,H
B:
E:H
H:
A:G
G:B

B|H
Script and Comments
Script1 
[ 1] /^[^:]+:$/H
[ 2] $!d
[ 3] g
[ 4] s/(^\n|:$)//g
[ 5] s/:\n/|/g
Comments
  1. The `-r' option of GNU sed must be used when running this and the next scripts to make sed interpret REs as EREs.
  2. This script will generate a list consisting of modules separated by `|'. These modules do not depend on any others and this list will be used as an ERE in next script.
  3. If a module does not depend on any other, Step [1] appends that line to the Hold Space.
  4. Step [2] starts a new cycle to process the next line if the current line is not the last one of the file;
  5. otherwise, command `g' of Step [3] copies the lines kept by Step [1] from Hold Space to Pattern Space.
  6. Steps [4] and [5] are used to transform kept lines to the form like B|H.
Raw Input Desired Output 
D:A,F,C
C:H
F:B,E,H
B:
E:H
H:
A:G
G:B

D:A,F,C
C:
F:E
E:
A:G
G:
Script and Comments
Script1 
[ 1] /^($MOD):$/d
[ 2] :loop
[ 3] s/(:|,)($MOD)(,|$)/\1/
[ 4] t loop
[ 5] s/,$//
Comments
  1. Given B|H, we want to remove from the datafile lines like B: and H: and lines contains `B' or `H' in the right hand side of the colons. `B|H' is assumed to be kept in a shell variable named `MOD'.
  2. To remove exactly module `B' from a dependency line, we have to take into account 4 cases:
    targetreplace it with
    :B, :
    :B$ :
    ,B, ,
    ,B$ (empty)
    Step [3] processes first three cases well, but leaves a trailing comma in the fourth case. Step [5] is used to remove the trailing comma.
  3. Steps [2] thru [4] constitute a loop which iterates till there is no more removable module in that line.