Topological sort/Extracted top item: Difference between revisions

Given a mapping between items, and items they depend on, a [[wp:Topological sorting|topological sort]] orders items so that no item precedes an item it depends upon.

 

<small>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.</small>

<br><br>

* [[Topological sort]]

<br><br>

=={{header|C}}==

Take code from [[Topological sort#c]] and add/change the following:

"top2 des1 ip2 ip3\n"

"ip1 extra1 ip1a ipcommon\n"

 

return 0;

level 1: extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1

level 2: ip1 ip2 des1a des1c

Compile order for: ip1

level 1: extra1 ip1a ipcommon

 

=={{header|Go}}==

 

import (

}

return L[i:], nil

{{out}}

<pre>

Derived from the [[Topological sort#J|topological sort]] implementation:

 

targets=. ;: x

parsed=. <@;:;._2 y

 

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

 

The changes include:

Example:

 

top1 des1 ip1 ip2

top2 des1 ip2 ip3

des1

top1 top2

 

=={{header|Java}}==

{{works with|Java|8}}

import static java.util.Arrays.asList;

import static java.util.stream.Collectors.toList;

class Graph {

List<String> vertices;

int numVertices;

 

vertices = asList(s.split(","));

numVertices = vertices.size();

 

for (int[] edge : edges)

}

 

List<String> toplevels() {

List<String> result = new ArrayList<>();

outer:

for (int c = 0; c < numVertices; c++) {

for (int r = 0; r < numVertices; r++) {

continue outer;

}

 

while (!queue.isEmpty()) {

for (int c = 0; c < numVertices; c++) {

queue.add(c);

}

return result.stream().distinct().collect(toList());

}

<pre>Top levels: [top1, top2]

Compile order for top1 [extra1, des1c1, des1a2, des1a1, des1c, des1b, des1a, ip2c, ip2b, ip2a, ipcommon, ip1a, des1, ip2, ip1, top1]

Compile order for ip1 [extra1, ipcommon, ip1a, ip1]</pre>

 

 

 

}

}

}

}

 

{{out}}

 

 

 

 

</pre>

=={{header|Python}}==

Where the compile order between a subset of files is arbitrary, they are shown on the same line.

from functools import reduce

except: pass

print("\nThe compile order for top levels: %s is..."

% ' and '.join(str(s) for s in sorted(tops)) )

 

'''Sample Output'''

=={{header|Racket}}==

 

(define dep-tree ; go straight for the hash, without parsing strings etc.

#hash((top1 . (des1 ip1 ip2))

(print-build-order dep-tree 'top2)

(with-handlers [(exn? (λ (x) (displayln (exn-message x) (current-error-port))))]

 

{{out}}

 

build-tree: circular dependency tree at node: ip1</pre>

 

=={{header|REXX}}==

Where the compile order between a subset of files is arbitrary, they are shown on the same line.

<br>This REXX version can handle multiple top levels.

parse arg job /*obtain optional argument from the CL.*/

$=

do j=1 while tree.j\=='' /*build job tree.*/

end /*k*/

end /*j*/

end /*k*/ /* [↑] build arrays of job departments*/

end /*j*/

 

do words($) /*process all the jobs specified. */

if z==0 then do; #.x=1; iterate; end /*if no dependents, then skip this one.*/

 

do r=1 for words(yyy) /*verify that there are no duplicates. */

end /*r*/

if yyy='' then leave /*if null, then we're done with jobList*/

 

 

end /*s*/ /* [↑] construct various job stages. */

 

/* [↓] display the stages for the job.*/

<pre>

 

1 des1b extra1 ip1a ipcommon ip2a ip2b ip2c des1a1 des1a2 des1c1 extra1

4 top1

</pre>

<pre>

 

1 ip3 des1b ip2a ip2b ip2c ipcommon des1a1 des1a2 des1c1 extra1

4 top2

</pre>

<pre>

 

1 ip3 des1b extra1 ip1a ipcommon ip2a ip2b ip2c des1a1 des1a2 des1c1 extra1

The <tt>topsort</tt> proc is taken from [[Topological sort#Tcl]] with <tt>{*}</tt> removed from the line commented so that results are returned by level:

 

proc topsort {data} {

# Clean the data

puts "\tround [incr i]:\t$deps"

}

 

{{out}}

round 3: des1

round 4: top2

</pre>