Using awk language for constructing a function call graph from a txt file containing function IDs

Question

I have a txt file with two columns which in each column I have function Ids which indicate the first function calls the second function such as below:

1,4

12,5

4,8

8,1

5,23

Now, I am going to use awk commands to find a flow of my function calls. For example, based on the above content of my file, I wanna to extract a flow of 1,4,8 and 12,5,23

For each flow, I will continue to add the function ids until I reach to a circle or I reach to end of the file. My files are very huge and I don't wanna to use python.

Answer 1

You'll want a recursive-descent program, like this:

$ cat recurse.awk
BEGIN { FS=OFS="," }
{
    roots[NR] = $1
    map[$1] = $2
}
END {
    for (rootNr=1; rootNr<=NR; rootNr++) {
        root = roots[rootNr]
        if ( !(seen[root]++) ) {
            tree = root
            descend(root)
            print tree
        }
    }
}

function descend(root,  branch) {
    if (root in map) {
        branch = map[root]
        if ( !(seen[branch]++) ) {
            tree = tree OFS branch
            descend(branch)
        }
    }
}

$ awk -f recurse.awk file
1,4,8
12,5,23