Shell Programming and Scripting

awk -F'`~' '
function from(n,pre,i,v,x)
{
    if(n in T) {
       v=split(T[n],x,",")
       for(i=1; i<=v;i++)
          from(F[x[i]], pre "~" L[x[i]]);
    } else print substr(pre,2);
}
{
   L[NR]=$1;
   F[NR]=$4;
   if($3 in T) T[$3]=T[$3]","NR;
   else T[$3]=NR;
}
END { from("SNA") }' infile

#!/bin/bash
function from()
{
 local pre=$2
 if [ ${#T[$1]} -gt 0 ]
 then
     set ${T[$1]}
     while [ $# -gt 0 ]
     do
        from "${F[$1]}" "$pre~${L[$1]}"
        shift
     done
  else
     echo ${pre:1}
  fi
}

while read line
do
   set ${line//\`~/ }
   ((L[++ln]=$1))
   ((F[ln]=$4))
   [ "$3" = "SNA" ] && T[9999]="${T[9999]} $ln" || T[$3]="${T[$3]} $ln"
done < infile

from 9999