Topological sort/Extracted top item: Difference between revisions
→{{header|jq}}
m (→{{header|Wren}}: Minor tidy) |
|||
Line 542:
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}}==
| |||