Topological sort/Extracted top item: Difference between revisions
→{{header|jq}}
m (ordered the categories so that they appear in the correct order when displayed.) |
|||
| (6 intermediate revisions by 5 users not shown) | |||
Line 42:
* [[Topological sort]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F _topx(data, tops, &_sofar) -> [[String]]
‘Recursive topological extractor’
_sofar [+]= copy(tops)
V depends = Set[String]()
L(top) tops
I top C data
depends.update(data[top])
I !depends.empty
_topx(data, depends, &_sofar)
[[String]] ordered
V accum = Set[String]()
L(i) (_sofar.len-1 .. 0).step(-1)
ordered [+]= sorted(Array(_sofar[i] - accum))
accum.update(_sofar[i])
R ordered
F toplevels(&data)
‘
Extract all top levels from dependency data
Top levels are never dependents
’
L(k, v) data
v.discard(k)
Set[String] dependents
L(k, v) data
dependents.update(v)
R Set(data.keys()) - dependents
F topx(&data, tops)
‘Extract the set of top-level(s) in topological order’
L(k, v) data
v.discard(k)
[Set[String]] _sofar
R _topx(data, tops, &_sofar)
F printorder(order)
‘Prettyprint topological ordering’
I !order.empty
print(‘First: ’order[0].map(s -> String(s)).join(‘, ’))
L(o) order[1..]
print(‘ Then: ’o.map(s -> String(s)).join(‘, ’))
V data = [
‘top1’ = Set([‘ip1’, ‘des1’, ‘ip2’]),
‘top2’ = Set([‘ip2’, ‘des1’, ‘ip3’]),
‘des1’ = Set([‘des1a’, ‘des1b’, ‘des1c’]),
‘des1a’ = Set([‘des1a1’, ‘des1a2’]),
‘des1c’ = Set([‘des1c1’, ‘extra1’]),
‘ip2’ = Set([‘ip2a’, ‘ip2b’, ‘ip2c’, ‘ipcommon’]),
‘ip1’ = Set([‘ip1a’, ‘ipcommon’, ‘extra1’])
]
V tops = toplevels(&data)
print(‘The top levels of the dependency graph are: ’Array(tops).join(‘ ’))
L(t) sorted(Array(tops))
print("\nThe compile order for top level: #. is...".format(t))
printorder(topx(&data, Set([t])))
I tops.len > 1
print("\nThe compile order for top levels: #. is...".format(sorted(Array(tops)).map(s -> String(s)).join(‘ and ’)))
printorder(topx(&data, tops))</syntaxhighlight>
{{out}}
<pre>
The top levels of the dependency graph are: top1 top2
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
</pre>
=={{header|C}}==
Take code from [[Topological sort#c]] and add/change the following:
<
"top2 des1 ip2 ip3\n"
"ip1 extra1 ip1a ipcommon\n"
Line 119 ⟶ 207:
return 0;
}</
level 1: extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1
level 2: ip1 ip2 des1a des1c
Line 139 ⟶ 227:
Compile order for: ip1
level 1: extra1 ip1a ipcommon
level 2: ip1</
=={{header|Go}}==
<
import (
Line 301 ⟶ 389:
}
return L[i:], nil
}</
{{out}}
<pre>
Line 317 ⟶ 405:
Derived from the [[Topological sort#J|topological sort]] implementation:
<
targets=. ;: x
parsed=. <@;:;._2 y
Line 329 ⟶ 417:
topLevel=: [: ({.&> -. [:;}.&.>) <@;:;._2
</syntaxhighlight>
The changes include:
Line 343 ⟶ 431:
Example:
<
top1 des1 ip1 ip2
top2 des1 ip2 ip3
Line 374 ⟶ 462:
des1
top1 top2
</syntaxhighlight>
=={{header|Java}}==
{{works with|Java|8}}
<
import static java.util.Arrays.asList;
import static java.util.stream.Collectors.toList;
Line 449 ⟶ 537:
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|jq}}==
'''Works with jq, the C implementation of jq'''
The program can easily be modified to work with gojq,
the Go implementation of jq, by changing `keys_unsorted` to `keys`.
The program has largely been adapted from [[#Wren|Wren]] but here the
dependencies are specified naturally in terms of the file names,
and care is taken to address the task requirements that
self-dependence is ignored, and that the specified ordering of
independents is respected. Additionally, cycles are ignored.
These aspects can be seen by defining `deps` as:
<pre>
{ "top1": ["top2", "x", "y", "z"], "top2": ["top1", "x", "y", "z"] }
</pre>
In this case, the result for `top1` would be:
<pre>
A compilation order for top1:
top2 x y z top1
</pre>
<syntaxhighlight lang="jq">
# Emit a stream of first occurrences of items in the stream
def firsts(stream):
foreach stream as $x (null;
($x|tostring) as $s
| if . == null or .[$s] == null then .[$s] = $x | .emit = $x
elif .[$s] then .emit = null
else .emit = null
end;
select(.emit).emit);
# {numVertices, vertices, adjacency }
def Graph($edges):
# Use `reverse` to ensure the ordering of independents is respected
([firsts($edges | keys_unsorted[], .[][])] | reverse) as $vertices
| ($vertices|length) as $nv
| reduce ($edges | keys_unsorted[]) as $k ({};
reduce ($edges[$k][]) as $v (.;
if $k == $v then . # ignore self-dependencies
else .[$k][$v] = true
end ) )
| {$vertices, numVertices: $nv, adjacency: .} ;
# Input: a Graph
def topLevels:
.result = []
# look for empty columns
| reduce .vertices[] as $c (.;
.outer = false
| .r = 0
| until(.outer or .r == .numVertices;
if .adjacency[.vertices[.r]][$c]
then .outer = true
end
| .r += 1 )
| if .outer == false then .result += [$c] end
)
| .result;
# Input: a Graph
def compileOrder($item):
. + {result: [], queue: [$item] }
| until (.queue | length == 0;
.queue[0] as $r
| .queue |= .[1:]
# Ignore cycles by subtracting .result:
| reduce (.vertices - .result)[] as $c (.;
if .adjacency[$r][$c] and (.queue|index($c) == null)
then .queue += [$c]
end )
| .result = [$r] + .result
)
| [firsts(.result[])];
### An example
def deps: {
"top1" : ["ip1", "des1", "ip2"],
"top2" : ["ip2", "des1", "ip3"],
"des1" : ["des1a", "des1b", "des1c"],
"des1a": ["des1a1", "des1a2"],
"des1c": ["des1c1", "extra1"],
"ip2" : ["ip2a", "ip2b", "ip2c", "ipcommon"],
"ip1" : ["ip1a", "ipcommon", "extra1"]
};
def files: ["top1", "top2", "ip1"];
Graph(deps)
| "Top levels: \(topLevels)",
(files[] as $f
| "\nA compilation order for \($f):",
(compileOrder($f)|join(" ")) )
</syntaxhighlight>
{{output}}
<pre>
Top levels: ["top2","top1"]
A compilation order for top1:
des1a1 des1a2 des1c1 des1a des1c des1b ip2a ip2b ip2c extra1 ipcommon ip1a des1 ip2 ip1 top1
A compilation order for top2:
des1a1 des1a2 des1c1 extra1 des1a des1c des1b ip2a ip2b ip2c ipcommon des1 ip2 ip3 top2
A compilation order for ip1:
extra1 ipcommon ip1a ip1
</pre>
=={{header|Julia}}==
<
top1 des1 ip1 ip2
top2 des1 ip2 ip3
Line 490 ⟶ 689:
println("Compile order for $f: ", compileorder("top1", topodict))
end
</
<pre>
Top level files: ["top2", "top1"]
Line 501 ⟶ 700:
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.util.LinkedList
Line 561 ⟶ 760:
println("Top levels: ${g.topLevels()}")
for (f in files) println("\nCompile order for $f: ${g.compileOrder(f)}")
}</
{{out}}
Line 572 ⟶ 771:
Compile order for ip1: [extra1, ipcommon, ip1a, ip1]
</pre>
=={{header|Nim}}==
{{trans|Python}}
<syntaxhighlight lang="nim">import algorithm, sequtils, strutils, sets, tables
type
StringSet = HashSet[string]
StringSeq = seq[string]
const Empty: StringSet = initHashSet[string]()
func topLevels(data: Table[string, StringSet]): StringSet =
## Extract all top levels from dependency data.
# Remove self dependencies.
var data = data
for key, values in data.mpairs:
values.excl key
let deps = toSeq(data.values).foldl(a + b)
result = toSeq(data.keys).toHashSet - deps
func topx(data: Table[string, StringSet]; tops: StringSet;
sofar: var seq[StringSet]): seq[StringSeq] =
## Recursive topological extractor.
sofar = sofar & tops
var depends: StringSet
for top in tops:
depends = depends + data.getOrDefault(top, Empty)
if depends.card != 0: discard data.topx(depends, sofar)
var accum = Empty
for i in countdown(sofar.high, 0):
result.add sorted(toSeq(sofar[i] - accum))
accum = accum + sofar[i]
func topx(data: Table[string, StringSet]; tops = initHashSet[string]()): seq[StringSeq] =
## Extract the set of top-level(s) in topological order.
# Remove self dependencies.
var data = data
for key, values in data.mpairs:
values.excl key
var tops = tops
if tops.card == 0: tops = data.topLevels
var sofar: seq[StringSet]
result = data.topx(tops, sofar)
proc printOrder(order: seq[StringSeq]) =
## Prettyprint topological ordering.
if order.len != 0:
echo "First: ", order[0].join(", ")
for i in 1..order.high:
echo " Then: ", order[i].join(", ")
when isMainModule:
const Data = {"top1": ["ip1", "des1", "ip2"].toHashSet,
"top2": ["ip2", "des1", "ip3"].toHashSet,
"des1": ["des1a", "des1b", "des1c"].toHashSet,
"des1a": ["des1a1", "des1a2"].toHashSet,
"des1c": ["des1c1", "extra1"].toHashSet,
"ip2": ["ip2a", "ip2b", "ip2c", "ipcommon"].toHashSet,
"ip1": ["ip1a", "ipcommon", "extra1"].toHashSet}.toTable
let tops = Data.topLevels()
let topList = sorted(tops.toSeq)
echo "The top levels of the dependency graph are: ", topList.join(", ")
for t in topList:
echo "\nThe compile order for top level “$#” is..." % t
printOrder Data.topx([t].toHashSet)
if tops.len > 1:
echo "\nThe compile order for top levels $# is..." % topList.mapIt("“" & it & "”").join(" and ")
printOrder Data.topx(tops)</syntaxhighlight>
{{out}}
<pre>The top levels of the dependency graph are: top1, top2
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</pre>
=={{header|Pascal}}==
Works with FPC (tested with version 3.2.2).
<syntaxhighlight lang="pascal">
program TopLevel;
{$mode delphi}
uses
SysUtils, Generics.Collections;
type
TAdjList = class
InList, // incoming arcs
OutList: THashSet<string>; // outcoming arcs
constructor Create;
destructor Destroy; override;
end;
TDigraph = class(TObjectDictionary<string, TAdjList>)
procedure AddNode(const s: string);
procedure AddArc(const s, t: string);
function AdjList(const s: string): TAdjList;
end;
constructor TAdjList.Create;
begin
InList := THashSet<string>.Create;
OutList := THashSet<string>.Create;
end;
destructor TAdjList.Destroy;
begin
InList.Free;
OutList.Free;
inherited;
end;
procedure TDigraph.AddNode(const s: string);
begin
if not ContainsKey(s) then
Add(s, TAdjList.Create);
end;
procedure TDigraph.AddArc(const s, t: string);
begin
AddNode(s);
AddNode(t);
if s <> t then begin
Items[s].OutList.Add(t);
Items[t].InList.Add(s);
end;
end;
function TDigraph.AdjList(const s: string): TAdjList;
begin
if not TryGetValue(s, Result) then
Result := nil;
end;
function GetCompOrder(g: TDigraph; const aTarget: string): TStringArray;
var
Stack: TList<string>;
Visited: THashSet<string>;
procedure Dfs(const aNode: string);
var
Next: string;
begin
Visited.Add(aNode);
for Next in g.AdjList(aNode).OutList do
if not Visited.Contains(Next) then
Dfs(Next);
Stack.Add(aNode);
end;
begin
if not g.ContainsKey(aTarget) then exit([aTarget]);
Stack := TList<string>.Create;
Visited := THashSet<string>.Create;
Dfs(aTarget);
Visited.Free;
Result := Stack.ToArray;
Stack.Free;
end;
function GetTopLevels(g: TDigraph): TStringArray;
var
List: TList<string>;
p: TPair<string, TAdjList>;
begin
List := TList<string>.Create;
for p in g do
with p.Value do
if (InList.Count = 0) and (OutList.Count <> 0) then
List.Add(p.Key);
Result := List.ToArray;
List.Free;
end;
function ParseRawData(const aData: string): TDigraph;
var
Line, Curr, Node: string;
FirstTerm: Boolean;
begin
Result := TDigraph.Create([doOwnsValues]);
for Line in aData.Split([LineEnding], TStringSplitOptions.ExcludeEmpty) do begin
FirstTerm := True;
for Curr in Line.Split([' '], TStringSplitOptions.ExcludeEmpty) do
if FirstTerm then begin
Node := Curr;
Result.AddNode(Curr);
FirstTerm := False;
end else
Result.AddArc(Node, Curr);
end;
end;
const
Data =
'top1 des1 ip1 ip2' + LineEnding +
'top2 des1 ip2 ip3' + LineEnding +
'ip1 extra1 ip1a ipcommon' + LineEnding +
'ip2 ip2a ip2b ip2c ipcommon' + LineEnding +
'des1 des1a des1b des1c' + LineEnding +
'des1a des1a1 des1a2' + LineEnding +
'des1c des1c1 extra1';
var
g: TDigraph;
begin
g := ParseRawData(Data);
WriteLn('Top levels: ', string.Join(', ', GetTopLevels(g)));
WriteLn;
WriteLn('Compile order for top1:', LineEnding, string.Join(', ', GetCompOrder(g, 'top1')));
WriteLn;
WriteLn('Compile order for top2:', LineEnding, string.Join(', ', GetCompOrder(g, 'top2')));
g.Free;
end.
</syntaxhighlight>
{{out}}
<pre>
Top levels: top2, top1
Compile order for top1:
extra1, ipcommon, ip1a, ip1, des1a2, des1a1, des1a, des1c1, des1c, des1b, des1, ip2c, ip2b, ip2a, ip2, top1
Compile order for top2:
des1a2, des1a1, des1a, extra1, des1c1, des1c, des1b, des1, ip2c, ip2b, ip2a, ipcommon, ip2, ip3, top2
</pre>
=={{header|Perl}}==
<
use strict;
Line 599 ⟶ 1,045:
print "TOP LEVELS: @{[grep $deps !~ /\h$_\b/, $deps =~ /^\w+/gm]}\n";
print "\nTARGET $_ ORDER: @{[ uniq before split ]}\n"
for $deps =~ /^\w+/gm, 'top1 top2';</
{{out}}
<pre>
Line 623 ⟶ 1,069:
=={{header|Phix}}==
Minor tweaks to the Topological_sort code: top_levels, propagate() and -1 now means "not required".
<!--<
<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
Line 742 ⟶ 1,188:
<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>
<!--</
{{out}}
Items on the same line can be compiled at the same time, and each line is alphabetic.
Line 769 ⟶ 1,215:
=={{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
Line 832 ⟶ 1,278:
print("\nThe compile order for top levels: %s is..."
% ' and '.join(str(s) for s in sorted(tops)) )
printorder(topx(data, tops))</
'''Sample Output'''
Line 857 ⟶ 1,303:
=={{header|Racket}}==
<
(define dep-tree ; go straight for the hash, without parsing strings etc.
#hash((top1 . (des1 ip1 ip2))
Line 906 ⟶ 1,352:
(print-build-order dep-tree 'top2)
(with-handlers [(exn? (λ (x) (displayln (exn-message x) (current-error-port))))]
(build-tree #hash((top . (des1 ip1)) (ip1 . (net netip)) (netip . (mac ip1))) 'top))</
{{out}}
Line 925 ⟶ 1,371:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
my %ba;
for %deps.kv -> $after, @befores {
Line 990 ⟶ 1,436:
top_topos(%deps, 'top2');
top_topos(%deps, 'ip1');
top_topos(%deps, 'top1', 'top2');</
{{out}}
<pre>Top levels are: top1 top2
Line 1,020 ⟶ 1,466:
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. */
Line 1,086 ⟶ 1,532:
/* [↓] display the stages for the job.*/
do show=1 for s; if stage.show\=='' then say show stage.show
end /*show*/ /*stick a fork in it, we're all done. */</
{{out|output|text= when using the default input of: <tt> top1 </tt>}}
<pre>
Line 1,119 ⟶ 1,565:
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
Line 1,211 ⟶ 1,657:
puts "\tround [incr i]:\t$deps"
}
}</
{{out}}
Line 1,237 ⟶ 1,683:
{{libheader|Wren-llist}}
{{libheader|Wren-seq}}
<
import "./seq" for Lst
var s = "top1, top2, ip1, ip2, ip3, ip1a, ip2a, ip2b, ip2c, ipcommon, des1, " +
Line 1,298 ⟶ 1,744:
var g = Graph.new(s, deps)
System.print("Top levels: %(g.topLevels)")
for (f in files) System.print("\nCompile order for %(f): %(g.compileOrder(f))")</
{{out}}
| |||