Topological sort/Extracted top item

Topological sort/Extracted top item is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Given a mapping between items, and items they depend on, a topological sort orders items so that no item precedes an item it depends upon.

The compiling of a design in the VHDL language has the constraint that a file must be compiled after any file containing definitions it depends on. A tool exists that extracts file dependencies.

• Assume the file names are single words, given without their file extensions.
• Files mentioned as only dependants, have no dependants of their own, but their order of compiling must be given.
• Any self dependencies should be ignored.

A top level file is defined as a file that:

1. Has dependents.
2. Is not itself the dependent of another file

Task Description

Given the following file dependencies as an example:

FILE    FILE DEPENDENCIES
====    =================
top1    des1 ip1 ip2
top2    des1 ip2 ip3
ip1     extra1 ip1a ipcommon
ip2     ip2a ip2b ip2c ipcommon
des1    des1a des1b des1c
des1a   des1a1 des1a2
des1c   des1c1 extra1

The task is to create a program that given a graph of the dependency:

1. Determines the top levels from the dependencies and show them.
2. Extracts a compile order of files to compile any given (usually top level) file.
3. Give a compile order for file top1.
4. Give a compile order for file top2.

You may show how to compile multiple top levels as a stretch goal

Note: this task differs from task Topological sort in that the order for compiling any file might not include all files; and that checks for dependency cycles are not mandated.

C.f. Topological sort

C

Take code from Topological sort#c and add/change the following: <lang c>char input[] = "top1 des1 ip1 ip2\n" "top2 des1 ip2 ip3\n" "ip1 extra1 ip1a ipcommon\n" "ip2 ip2a ip2b ip2c ipcommon\n" "des1 des1a des1b des1c\n" "des1a des1a1 des1a2\n" "des1c des1c1 extra1\n";

... int find_name(item base, int len, const char *name) { int i; for (i = 0; i < len; i++) if (!strcmp(base[i].name, name)) return i; return -1; }

int depends_on(item base, int n1, int n2) { int i; if (n1 == n2) return 1; for (i = 0; i < base[n1].n_deps; i++) if (depends_on(base, base[n1].deps[i], n2)) return 1; return 0; }

void compile_order(item base, int n_items, int *top, int n_top) { int i, j, lvl; int d = 0; printf("Compile order for:"); for (i = 0; i < n_top; i++) { printf(" %s", base[top[i]].name); if (base[top[i]].depth > d) d = base[top[i]].depth; } printf("\n");

for (lvl = 1; lvl <= d; lvl ++) { printf("level %d:", lvl); for (i = 0; i < n_items; i++) { if (base[i].depth != lvl) continue; for (j = 0; j < n_top; j++) { if (depends_on(base, top[j], i)) { printf(" %s", base[i].name); break; } } } printf("\n"); } printf("\n"); }

int main() { int i, n, bad = -1; item items; n = parse_input(&items);

for (i = 0; i < n; i++) if (!items[i].depth && get_depth(items, i, bad) < 0) bad--;

int top[3]; top[0] = find_name(items, n, "top1"); top[1] = find_name(items, n, "top2"); top[2] = find_name(items, n, "ip1");

compile_order(items, n, top, 1); compile_order(items, n, top + 1, 1); compile_order(items, n, top, 2); compile_order(items, n, top + 2, 1);

return 0; }</lang>output (the last item is just to show that it doesn't have to be top level)<lang>Compile order for: top1 level 1: extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 level 2: ip1 ip2 des1a des1c level 3: des1 level 4: top1

Compile order for: top2 level 1: ip3 extra1 ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 level 2: ip2 des1a des1c level 3: des1 level 4: top2

Compile order for: top1 top2 level 1: ip3 extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 level 2: ip1 ip2 des1a des1c level 3: des1 level 4: top1 top2

Compile order for: ip1 level 1: extra1 ip1a ipcommon level 2: ip1</lang>

Go

<lang go>package main

import (

   "fmt"
   "strings"

)

var data = ` FILE FILE DEPENDENCIES

=============

top1 des1 ip1 ip2 top2 des1 ip2 ip3 ip1 extra1 ip1a ipcommon ip2 ip2a ip2b ip2c ipcommon des1 des1a des1b des1c des1a des1a1 des1a2 des1c des1c1 extra1`

func main() {

   g, dep, err := parseLibDep(data)
   if err != nil {
       fmt.Println(err)
       return
   }
   // Task 1: Determine top levels.  The input parser returns a list (dep)
   // of libraries that are dependants of at least one other library.
   // Top levels are then libraries in the graph that are not on this list.
   var tops []string
   for n := range g {
       if !dep[n] {
           tops = append(tops, n)
       }
   }
   fmt.Println("Top levels:", tops)
   // Task 2 is orderFrom method, below
   showOrder(g, "top1")         // Task 3
   showOrder(g, "top2")         // Task 4
   showOrder(g, "top1", "top2") // Stretch

   fmt.Println("Cycle examples:")
   // reparse with a cyclic dependency
   g, _, err = parseLibDep(data + `

des1a1 des1`)

   if err != nil {
       fmt.Println(err)
       return
   }
   showOrder(g, "top1")       // runs into cycle
   showOrder(g, "ip1", "ip2") // does not involve cycle

}

func showOrder(g graph, target ...string) {

   order, cyclic := g.orderFrom(target...)
   if cyclic == nil {
       reverse(order) // compile order is reverse of dependency order
       fmt.Println("Target", target, "order:", order)
   } else {
       fmt.Println("Target", target, "cyclic dependencies:", cyclic)
   }

}

func reverse(s []string) {

   last := len(s) - 1
   for i, e := range s[:len(s)/2] {
       s[i], s[last-i] = s[last-i], e
   }

}

type graph map[string][]string // adjacency list representation type depList map[string]bool

// parseLibDep parses the text format of the task and returns a dependency // graph and a list of nodes that are dependants of at least one other node. func parseLibDep(data string) (g graph, d depList, err error) {

   lines := strings.Split(data, "\n")
   if len(lines) < 3 || !strings.HasPrefix(lines[2], "=") {
       return nil, nil, fmt.Errorf("data format")
   }
   lines = lines[3:]
   g = graph{}
   d = depList{}
   for _, line := range lines {
       libs := strings.Fields(line)
       if len(libs) == 0 {
           continue
       }
       lib := libs[0]
       var deps []string
       for _, dep := range libs[1:] {
           g[dep] = g[dep]
           if dep == lib {
               continue
           }
           for i := 0; ; i++ {
               if i == len(deps) {
                   deps = append(deps, dep)
                   d[dep] = true
                   break
               }
               if dep == deps[i] {
                   break
               }
           }
       }
       g[lib] = deps
   }
   return g, d, nil

}

// OrderFrom produces a topological ordering of the subgraph of g reachable // from a set of start nodes, where the subgraph is a directed acyclic graph. // If the subgraph contains a cycle, orderFrom returns the first cycle found // and returns a nil order. Cycles which are in the graph but not in the // subgraph reachable from start are not detected. func (g graph) orderFrom(start ...string) (order, cyclic []string) {

   L := make([]string, len(g))
   i := len(L)
   temp := map[string]bool{}
   perm := map[string]bool{}
   var cycleFound bool
   var cycleStart string
   var visit func(string)
   visit = func(n string) {
       switch {
       case temp[n]:
           cycleFound = true
           cycleStart = n
           return
       case perm[n]:
           return
       }
       temp[n] = true
       for _, m := range g[n] {
           visit(m)
           if cycleFound {
               if cycleStart > "" {
                   cyclic = append(cyclic, n)
                   if n == cycleStart {
                       cycleStart = ""
                   }
               }
               return
           }
       }
       delete(temp, n)
       perm[n] = true
       i--
       L[i] = n
   }
   for _, n := range start {
       if perm[n] {
           continue
       }
       visit(n)
       if cycleFound {
           return nil, cyclic
       }
   }
   return L[i:], nil

}</lang>

Output:

Top levels: [top1 top2]
Target [top1] order: [des1a1 des1a2 des1a des1b des1c1 extra1 des1c des1 ip1a ipcommon ip1 ip2a ip2b ip2c ip2 top1]
Target [top2] order: [des1a1 des1a2 des1a des1b des1c1 extra1 des1c des1 ip2a ip2b ip2c ipcommon ip2 ip3 top2]
Target [top1 top2] order: [des1a1 des1a2 des1a des1b des1c1 extra1 des1c des1 ip1a ipcommon ip1 ip2a ip2b ip2c ip2 top1 ip3 top2]
Cycle examples:
Target [top1] cyclic dependencies: [des1a1 des1a des1]
Target [ip1 ip2] order: [extra1 ip1a ipcommon ip1 ip2a ip2b ip2c ip2]

J

Derived from the topological sort implementation:

<lang j>compileOrder=: dyad define

 targets=. ;: x
 parsed=. <@;:;._2 y
 names=. ~.({.&>parsed),targets,;parsed
 depends=. (> =@i.@#) names e.S:1 (#names){.parsed
 depends=. (+. +./ .*.~)^:_ depends
 b=. +./depends (] , #~) names e. targets
 names (</.~ \: ~.@])&(keep&#) +/"1 depends
 (b#names) (</.~ /: ~.@]) +/ }.+./ .*.~&(b#"1 b#depends)^:a: 1

)

topLevel=: [: ({.&> -. [:;}.&.>) <@;:;._2 </lang>

The changes include:

1. Added an argument for the target(s) we wish to find dependencies for
2. Make sure that these targets are included in our dependency structures
3. Make sure that things we can depend on are included in our dependency structures
4. Select these targets, and the things they depend on, once we know what depends on what
5. When ordering names by dependencies:
   1. only consider names and dependencies we want to keep
   2. extract names grouped by their dependency chain length

Example:

<lang j>dependencies=: noun define

 top1    des1 ip1 ip2
 top2    des1 ip2 ip3
 ip1     extra1 ip1a ipcommon
 ip2     ip2a ip2b ip2c ipcommon
 des1    des1a des1b des1c
 des1a   des1a1 des1a2
 des1c   des1c1 extra1

)

  >topLevel dependencies

top1 top2

  ;:inv@> 'top1' compileOrder dependencies

extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 ip1 ip2 des1a des1c des1 top1

  ;:inv@> 'top2' compileOrder dependencies

ip3 extra1 ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 ip2 des1a des1c des1 top2

  ;:inv@> 'top1 top2' compileOrder dependencies

ip3 extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 ip1 ip2 des1a des1c des1 top1 top2 </lang>

Python

Where the compile order between a subset of files is arbitrary, they are shown on the same line. <lang python>try:

   from functools import reduce

except: pass

1. Python 3.x: def topx(data:'dict', tops:'set'=None) -> 'list':

def topx(data, tops=None):

   'Extract the set of top-level(s) in topological order'
   for k, v in data.items():
       v.discard(k) # Ignore self dependencies
   if tops is None:
       tops = toplevels(data)
   return _topx(data, tops, [], set())

def _topx(data, tops, _sofar, _sofar_set):

   'Recursive topological extractor'
   _sofar += [tops] # Accumulates order in reverse
   _sofar_set.union(tops)
   depends = reduce(set.union, (data.get(top, set()) for top in tops))
   if depends:
       _topx(data, depends, _sofar, _sofar_set)
   ordered, accum = [], set()
   for s in _sofar[::-1]:
       ordered += [sorted(s - accum)]
       accum |= s
   return ordered

def printorder(order):

   'Prettyprint topological ordering'
   if order:
       print("First: " + ', '.join(str(s) for s in order[0]))
   for o in order[1:]:
       print(" Then: " + ', '.join(str(s) for s in o))

def toplevels(data):

   \
   Extract all top levels from dependency data
   Top levels are never dependents
   
   for k, v in data.items():
       v.discard(k) # Ignore self dependencies
   dependents = reduce(set.union, data.values())
   return  set(data.keys()) - dependents

if __name__ == '__main__':

   data = dict(
       top1  = set('ip1 des1 ip2'.split()),
       top2  = set('ip2 des1 ip3'.split()),
       des1  = set('des1a des1b des1c'.split()),
       des1a = set('des1a1 des1a2'.split()),
       des1c = set('des1c1 extra1'.split()),
       ip2   = set('ip2a ip2b ip2c ipcommon'.split()),
       ip1   = set('ip1a ipcommon extra1'.split()),
       )

   tops = toplevels(data)
   print("The top levels of the dependency graph are: " + ' '.join(tops))

   for t in sorted(tops):
       print("\nThe compile order for top level: %s is..." % t)
       printorder(topx(data, set([t])))
   if len(tops) > 1:
       print("\nThe compile order for top levels: %s is..."
             % ' and '.join(str(s) for s in sorted(tops)) )
       printorder(topx(data, tops))</lang>

Sample Output

The top levels of the dependency graph are: top2 top1

The compile order for top level: top1 is...
First: des1a1, des1a2, des1c1, extra1
 Then: des1a, des1b, des1c, ip1a, ip2a, ip2b, ip2c, ipcommon
 Then: des1, ip1, ip2
 Then: top1

The compile order for top level: top2 is...
First: des1a1, des1a2, des1c1, extra1
 Then: des1a, des1b, des1c, ip2a, ip2b, ip2c, ipcommon
 Then: des1, ip2, ip3
 Then: top2

The compile order for top levels: top1 and top2 is...
First: des1a1, des1a2, des1c1, extra1
 Then: des1a, des1b, des1c, ip1a, ip2a, ip2b, ip2c, ipcommon
 Then: des1, ip1, ip2, ip3
 Then: top1, top2

REXX

Where the compile order between a subset of files is arbitrary, they are shown on the same line.
This REXX version can handle multiple top levels. <lang REXX>/*REXX pgm displays the compile order of jobs (indicating dependencies).*/ parse arg job /*get optional jobname from C.L. */ jobL.=; stage.=; #.=0; @.=; JL= /*define some variables. */ tree. = tree.1 = ' top1 des1 ip1 ip2 ' tree.2 = ' top2 des1 ip2 ip3 ' tree.3 = ' ip1 extra1 ip1a ipcommon ' tree.4 = ' ip2 ip2a ip2b ip2c ipcommon ' tree.5 = ' des1 des1a des1b des1c ' tree.6 = ' des1a des1a1 des1a2 ' tree.7 = ' des1c des1c1 extra1 ' $=

             do j=1  while  tree.j\==                /*build job tree*/
             parse var tree.j x deps;  @.x=space(deps) /*extract jobs. */
             if wordpos(x,$)==0  then $=$ x            /*Unique? Add it*/
                      do k=1  for words(@.x);  _=word(@.x,k)
                      if wordpos(_,$)==0  then $=space($ _)
                      end   /*k*/
             end            /*j*/

!.=;  !!.=

             do j=1  for words($);   x=word($,j);   !.x.0=words(@.x)
                 do k=1  for !.x.0;   !.x.k=word(@.x,k);   !!.x.k=!.x.k
                 end   /*k*/          /* [↑]  build arrays of job deps.*/
             end       /*j*/

 do words($)                          /*process all the jobs specified.*/
     do j=1  for words($);   x=word($,j);   z=words(@.x);   allN=1;   m=0
     if z==0  then do;  #.x=1;  iterate;  end   /*if no dependents ··· */
       do k=1  for z;   y=!.x.k                 /*examine all stage #s.*/
       if datatype(y,'W')  then m=max(m,y)      /*find highest stage #.*/
                           else do;  allN=0     /*one entry ¬ numeric. */
                                if #.y\==0  then !.x.k=#.y
                                end             /* [↑] replace with a #*/
       end   /*k*/
     if allN & m\==0  then #.x=max(#.x,m+1)     /*replace with stage #.*/
     end     /*j*/                    /* [↑] maybe set the stage number*/
 end         /*words($)*/

jobL.1=job /*define the bottom level jobList*/ s=1 /*define the stage level for jobL*/

       do j=1;  yyy=jobL.j
          do r=1  for words(yyy)      /*verify that there are no dups. */
              do c=1  while c<words(yyy);      z=word(yyy,c)
              p=wordpos(z,yyy,c+1);  if p\==0  then yyy=delword(yyy,p,1)
              end   /*c*/             /* [↑]   Dup?    Then delete it. */
          end       /*r*/
       jobL.j=yyy
       if yyy=  then leave          /*if null, then done with jobList*/
       z=words(yyy)                   /*number of jobs in the jobList. */
       s=s+1                                   /*bump the stage number.*/
             do k=1  for z;  _=word(yyy,k)     /*get a stage # for job.*/
             jobL.s=jobL.s @._                 /*add a job to a stage. */
             end   /*k*/
       end         /*j*/

do k=1  for s;  JL=JL jobL.k;  end    /*build a complete jobList (JL). */

  do s=1  for words(JL)               /*process each job in the jobList*/
  _=word(JL,s);     level=#._         /*get proper level for the job.  */
  stage.level=stage.level _           /*assign level to the job stage #*/
  end   /*s*/                         /* [↑] build various job stages. */

say '─────── The compile order for job: ' job; say

                                      /* [↓] display the stages for job*/
    do show=1  for s;  if stage.show\==  then say show stage.show;  end
                                      /*stick a fork in it, we're done.*/</lang>

output   when using the input of:   top1

─────── The compile order for job:  top1 

1  des1b extra1 ip1a ipcommon ip2a ip2b ip2c des1a1 des1a2 des1c1 extra1
2  ip1 ip2 des1a des1c
3  des1
4  top1

output   when using the input of:   top2

─────── The compile order for job:  top2

1  ip3 des1b ip2a ip2b ip2c ipcommon des1a1 des1a2 des1c1 extra1
2  ip2 des1a des1c
3  des1
4  top2

output   when using the input of:   top1 top2

─────── The compile order for job:  top1 top2

1  ip3 des1b extra1 ip1a ipcommon ip2a ip2b ip2c des1a1 des1a2 des1c1 extra1
2  ip1 ip2 des1a des1c
3  des1
4  top1 top2