Topological sort/Extracted top item: Difference between revisions

{{Sorting Algorithm}}

[[Category:Sorting]]

 

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.

* [[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;

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 top2 [extra1, des1c1, des1a2, des1a1, des1c, des1b, des1a, ipcommon, ip2c, ip2b, ip2a, des1, ip3, ip2, top2]

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

 

=={{header|Julia}}==

top1 des1 ip1 ip2

top2 des1 ip2 ip3

println("Compile order for $f: ", compileorder("top1", topodict))

end

<pre>

Top level files: ["top2", "top1"]

=={{header|Kotlin}}==

{{trans|Java}}

 

import java.util.LinkedList

println("Top levels: ${g.topLevels()}")

for (f in files) println("\nCompile order for $f: ${g.compileOrder(f)}")

 

{{out}}

 

Compile order for ip1: [extra1, ipcommon, ip1a, ip1]

</pre>

 

=={{header|Perl}}==

 

use strict;

print "TOP LEVELS: @{[grep $deps !~ /\h$_\b/, $deps =~ /^\w+/gm]}\n";

print "\nTARGET $_ ORDER: @{[ uniq before split ]}\n"

{{out}}

<pre>

=={{header|Phix}}==

Minor tweaks to the Topological_sort code: top_levels, propagate() and -1 now means "not required".

{{out}}

Items on the same line can be compiled at the same time, and each line is alphabetic.

=={{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}}

=={{header|Raku}}==

(formerly Perl 6)

my %ba;

for %deps.kv -> $after, @befores {

top_topos(%deps, 'top2');

top_topos(%deps, 'ip1');

{{out}}

<pre>Top levels are: top1 top2

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

jobL.=; stage.=; #.=0; @.=; JL= /*define some handy─dandy variables. */

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

do show=1 for s; if stage.show\=='' then say show stage.show

{{out|output|text=&nbsp; when using the default input of: &nbsp; <tt> top1 </tt>}}

<pre>

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}}

{{libheader|Wren-llist}}

{{libheader|Wren-seq}}

 

var s = "top1, top2, ip1, ip2, ip3, ip1a, ip2a, ip2b, ip2c, ipcommon, des1, " +

var g = Graph.new(s, deps)

System.print("Top levels: %(g.topLevels)")

 

{{out}}