Topological sort/Extracted top item: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) (Added 11l) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 46: | Line 46: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">F _topx(data, tops, &_sofar) -> [[String]] |
||
‘Recursive topological extractor’ |
‘Recursive topological extractor’ |
||
_sofar [+]= copy(tops) |
_sofar [+]= copy(tops) |
||
Line 106: | Line 106: | ||
I tops.len > 1 |
I tops.len > 1 |
||
print("\nThe compile order for top levels: #. is...".format(sorted(Array(tops)).map(s -> String(s)).join(‘ and ’))) |
print("\nThe compile order for top levels: #. is...".format(sorted(Array(tops)).map(s -> String(s)).join(‘ and ’))) |
||
printorder(topx(&data, tops))</ |
printorder(topx(&data, tops))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 133: | Line 133: | ||
=={{header|C}}== |
=={{header|C}}== |
||
Take code from [[Topological sort#c]] and add/change the following: |
Take code from [[Topological sort#c]] and add/change the following: |
||
< |
<syntaxhighlight lang="c">char input[] = "top1 des1 ip1 ip2\n" |
||
"top2 des1 ip2 ip3\n" |
"top2 des1 ip2 ip3\n" |
||
"ip1 extra1 ip1a ipcommon\n" |
"ip1 extra1 ip1a ipcommon\n" |
||
Line 207: | Line 207: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight>output (the last item is just to show that it doesn't have to be top level)<syntaxhighlight lang="text">Compile order for: top1 |
||
level 1: extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 |
level 1: extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 |
||
level 2: ip1 ip2 des1a des1c |
level 2: ip1 ip2 des1a des1c |
||
Line 227: | Line 227: | ||
Compile order for: ip1 |
Compile order for: ip1 |
||
level 1: extra1 ip1a ipcommon |
level 1: extra1 ip1a ipcommon |
||
level 2: ip1</ |
level 2: ip1</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 389: | Line 389: | ||
} |
} |
||
return L[i:], nil |
return L[i:], nil |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 405: | Line 405: | ||
Derived from the [[Topological sort#J|topological sort]] implementation: |
Derived from the [[Topological sort#J|topological sort]] implementation: |
||
< |
<syntaxhighlight lang="j">compileOrder=: dyad define |
||
targets=. ;: x |
targets=. ;: x |
||
parsed=. <@;:;._2 y |
parsed=. <@;:;._2 y |
||
Line 417: | Line 417: | ||
topLevel=: [: ({.&> -. [:;}.&.>) <@;:;._2 |
topLevel=: [: ({.&> -. [:;}.&.>) <@;:;._2 |
||
</syntaxhighlight> |
|||
</lang> |
|||
The changes include: |
The changes include: |
||
Line 431: | Line 431: | ||
Example: |
Example: |
||
< |
<syntaxhighlight lang="j">dependencies=: noun define |
||
top1 des1 ip1 ip2 |
top1 des1 ip1 ip2 |
||
top2 des1 ip2 ip3 |
top2 des1 ip2 ip3 |
||
Line 462: | Line 462: | ||
des1 |
des1 |
||
top1 top2 |
top1 top2 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|8}} |
{{works with|Java|8}} |
||
< |
<syntaxhighlight lang="java">import java.util.*; |
||
import static java.util.Arrays.asList; |
import static java.util.Arrays.asList; |
||
import static java.util.stream.Collectors.toList; |
import static java.util.stream.Collectors.toList; |
||
Line 537: | Line 537: | ||
return result.stream().distinct().collect(toList()); |
return result.stream().distinct().collect(toList()); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre>Top levels: [top1, top2] |
<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 top1 [extra1, des1c1, des1a2, des1a1, des1c, des1b, des1a, ip2c, ip2b, ip2a, ipcommon, ip1a, des1, ip2, ip1, top1] |
||
Line 544: | Line 544: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">const topotext = """ |
||
top1 des1 ip1 ip2 |
top1 des1 ip1 ip2 |
||
top2 des1 ip2 ip3 |
top2 des1 ip2 ip3 |
||
Line 578: | Line 578: | ||
println("Compile order for $f: ", compileorder("top1", topodict)) |
println("Compile order for $f: ", compileorder("top1", topodict)) |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Top level files: ["top2", "top1"] |
Top level files: ["top2", "top1"] |
||
Line 589: | Line 589: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="scala">// version 1.1.51 |
||
import java.util.LinkedList |
import java.util.LinkedList |
||
Line 649: | Line 649: | ||
println("Top levels: ${g.topLevels()}") |
println("Top levels: ${g.topLevels()}") |
||
for (f in files) println("\nCompile order for $f: ${g.compileOrder(f)}") |
for (f in files) println("\nCompile order for $f: ${g.compileOrder(f)}") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 664: | Line 664: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="nim">import algorithm, sequtils, strutils, sets, tables |
||
type |
type |
||
Line 741: | Line 741: | ||
if tops.len > 1: |
if tops.len > 1: |
||
echo "\nThe compile order for top levels $# is..." % topList.mapIt("“" & it & "”").join(" and ") |
echo "\nThe compile order for top levels $# is..." % topList.mapIt("“" & it & "”").join(" and ") |
||
printOrder Data.topx(tops)</ |
printOrder Data.topx(tops)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 765: | Line 765: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use strict; |
use strict; |
||
Line 789: | Line 789: | ||
print "TOP LEVELS: @{[grep $deps !~ /\h$_\b/, $deps =~ /^\w+/gm]}\n"; |
print "TOP LEVELS: @{[grep $deps !~ /\h$_\b/, $deps =~ /^\w+/gm]}\n"; |
||
print "\nTARGET $_ ORDER: @{[ uniq before split ]}\n" |
print "\nTARGET $_ ORDER: @{[ uniq before split ]}\n" |
||
for $deps =~ /^\w+/gm, 'top1 top2';</ |
for $deps =~ /^\w+/gm, 'top1 top2';</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 813: | Line 813: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Minor tweaks to the Topological_sort code: top_levels, propagate() and -1 now means "not required". |
Minor tweaks to the Topological_sort code: top_levels, propagate() and -1 now means "not required". |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">names</span> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">names</span> |
||
<span style="color: #008080;">enum</span> <span style="color: #000000;">RANK</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">NAME</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">DEP</span> <span style="color: #000080;font-style:italic;">-- content of names |
<span style="color: #008080;">enum</span> <span style="color: #000000;">RANK</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">NAME</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">DEP</span> <span style="color: #000080;font-style:italic;">-- content of names |
||
Line 932: | Line 932: | ||
<span style="color: #000000;">topsort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">input</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"top1"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"top2"</span><span style="color: #0000FF;">})</span> |
<span style="color: #000000;">topsort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">input</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"top1"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"top2"</span><span style="color: #0000FF;">})</span> |
||
<span style="color: #000000;">topsort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">input</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"ip1"</span><span style="color: #0000FF;">})</span> |
<span style="color: #000000;">topsort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">input</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"ip1"</span><span style="color: #0000FF;">})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
Items on the same line can be compiled at the same time, and each line is alphabetic. |
Items on the same line can be compiled at the same time, and each line is alphabetic. |
||
Line 959: | Line 959: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
Where the compile order between a subset of files is arbitrary, they are shown on the same line. |
Where the compile order between a subset of files is arbitrary, they are shown on the same line. |
||
< |
<syntaxhighlight lang="python">try: |
||
from functools import reduce |
from functools import reduce |
||
except: pass |
except: pass |
||
Line 1,022: | Line 1,022: | ||
print("\nThe compile order for top levels: %s is..." |
print("\nThe compile order for top levels: %s is..." |
||
% ' and '.join(str(s) for s in sorted(tops)) ) |
% ' and '.join(str(s) for s in sorted(tops)) ) |
||
printorder(topx(data, tops))</ |
printorder(topx(data, tops))</syntaxhighlight> |
||
'''Sample Output''' |
'''Sample Output''' |
||
Line 1,047: | Line 1,047: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(define dep-tree ; go straight for the hash, without parsing strings etc. |
(define dep-tree ; go straight for the hash, without parsing strings etc. |
||
#hash((top1 . (des1 ip1 ip2)) |
#hash((top1 . (des1 ip1 ip2)) |
||
Line 1,096: | Line 1,096: | ||
(print-build-order dep-tree 'top2) |
(print-build-order dep-tree 'top2) |
||
(with-handlers [(exn? (λ (x) (displayln (exn-message x) (current-error-port))))] |
(with-handlers [(exn? (λ (x) (displayln (exn-message x) (current-error-port))))] |
||
(build-tree #hash((top . (des1 ip1)) (ip1 . (net netip)) (netip . (mac ip1))) 'top))</ |
(build-tree #hash((top . (des1 ip1)) (ip1 . (net netip)) (netip . (mac ip1))) 'top))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,115: | Line 1,115: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
(formerly Perl 6) |
(formerly Perl 6) |
||
<lang |
<syntaxhighlight lang="raku" line>sub top_topos ( %deps, *@top ) { |
||
my %ba; |
my %ba; |
||
for %deps.kv -> $after, @befores { |
for %deps.kv -> $after, @befores { |
||
Line 1,180: | Line 1,180: | ||
top_topos(%deps, 'top2'); |
top_topos(%deps, 'top2'); |
||
top_topos(%deps, 'ip1'); |
top_topos(%deps, 'ip1'); |
||
top_topos(%deps, 'top1', 'top2');</ |
top_topos(%deps, 'top1', 'top2');</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Top levels are: top1 top2 |
<pre>Top levels are: top1 top2 |
||
Line 1,210: | Line 1,210: | ||
Where the compile order between a subset of files is arbitrary, they are shown on the same line. |
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. |
<br>This REXX version can handle multiple top levels. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program displays the compile order of jobs (indicating the dependencies). */ |
||
parse arg job /*obtain optional argument from the CL.*/ |
parse arg job /*obtain optional argument from the CL.*/ |
||
jobL.=; stage.=; #.=0; @.=; JL= /*define some handy─dandy variables. */ |
jobL.=; stage.=; #.=0; @.=; JL= /*define some handy─dandy variables. */ |
||
Line 1,276: | Line 1,276: | ||
/* [↓] display the stages for the job.*/ |
/* [↓] display the stages for the job.*/ |
||
do show=1 for s; if stage.show\=='' then say show stage.show |
do show=1 for s; if stage.show\=='' then say show stage.show |
||
end /*show*/ /*stick a fork in it, we're all done. */</ |
end /*show*/ /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= when using the default input of: <tt> top1 </tt>}} |
{{out|output|text= when using the default input of: <tt> top1 </tt>}} |
||
<pre> |
<pre> |
||
Line 1,309: | Line 1,309: | ||
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: |
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: |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.5 |
||
proc topsort {data} { |
proc topsort {data} { |
||
# Clean the data |
# Clean the data |
||
Line 1,401: | Line 1,401: | ||
puts "\tround [incr i]:\t$deps" |
puts "\tround [incr i]:\t$deps" |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,427: | Line 1,427: | ||
{{libheader|Wren-llist}} |
{{libheader|Wren-llist}} |
||
{{libheader|Wren-seq}} |
{{libheader|Wren-seq}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/llist" for DLinkedList |
||
import "/seq" for Lst |
import "/seq" for Lst |
||
Line 1,488: | Line 1,488: | ||
var g = Graph.new(s, deps) |
var g = Graph.new(s, deps) |
||
System.print("Top levels: %(g.topLevels)") |
System.print("Top levels: %(g.topLevels)") |
||
for (f in files) System.print("\nCompile order for %(f): %(g.compileOrder(f))")</ |
for (f in files) System.print("\nCompile order for %(f): %(g.compileOrder(f))")</syntaxhighlight> |
||
{{out}} |
{{out}} |