Tarjan: Difference between revisions
Content added Content deleted
(→{{header|Wren}}: Now uses new core library method.) |
|||
Line 622: | Line 622: | ||
[7] |
[7] |
||
</pre> |
</pre> |
||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
In this adaptation of the [[#Kotlin]]/[[#Wren]] implementations: |
|||
* a Node is represented by JSON object with .n being its id; |
|||
* a DirectedGraph is represented by a JSON object {vs, es} where vs is an array of Nodes and es is an array of integer ids; |
|||
* a Stack is reprsented by an array, with .[-1] as the active point; |
|||
* the output of `tarjan` is an array each item of which is an array of Node ids. |
|||
<br> |
|||
<lang jq># Input: an integer |
|||
def Node: |
|||
{ n: ., |
|||
index: -1, # -1 signifies undefined |
|||
lowLink: -1, |
|||
onStack: false |
|||
} ; |
|||
# Input: a DirectedGraph |
|||
# Output: a stream of Node ids |
|||
def successors($vn): .es[$vn][]; |
|||
# Input: a DirectedGraph |
|||
# Output: an array of integer arrays |
|||
def tarjan: |
|||
. + { sccs: [], # strongly connected components |
|||
index: 0, |
|||
s: [] # Stack |
|||
} |
|||
# input: {es, vs, sccs, index, s} |
|||
| def strongConnect($vn): |
|||
# Set the depth index for v to the smallest unused index |
|||
.vs[$vn].index = .index |
|||
| .vs[$vn].lowLink = .index |
|||
| .index += 1 |
|||
| .s += [ $vn ] |
|||
| .vs[$vn].onStack = true |
|||
# consider successors of v |
|||
| reduce successors($vn) as $wn (.; |
|||
if .vs[$wn].index < 0 |
|||
then |
|||
# Successor w has not yet been visited; recurse on it |
|||
strongConnect($wn) |
|||
| .vs[$vn].lowLink = ([.vs[$vn].lowLink, .vs[$wn].lowLink] | min ) |
|||
elif .vs[$wn].onStack |
|||
then |
|||
# Successor w is in stack s and hence in the current SCC |
|||
.vs[$vn].lowLink = ([.vs[$vn].lowLink, .vs[$wn].index] | min ) |
|||
else . |
|||
end |
|||
) |
|||
# If v is a root node, pop the stack and generate an SCC |
|||
| if .vs[$vn] | (.lowLink == .index) |
|||
then .scc = [] |
|||
| .stop = false |
|||
| until(.stop; |
|||
.s[-1] as $wn |
|||
| .s |= .[:-1] # pop |
|||
| .vs[$wn].onStack = false |
|||
| .scc += [$wn] |
|||
| if $wn == $vn then .stop = true else . end ) |
|||
| .sccs += [.scc] |
|||
else .scc = [] |
|||
end |
|||
; |
|||
reduce .vs[].n as $vn (.; |
|||
if .vs[$vn].index < 0 |
|||
then strongConnect($vn) |
|||
else . end |
|||
) |
|||
| .sccs |
|||
; |
|||
# Vertices |
|||
def vs: [range(0;8) | Node ]; |
|||
# Edges |
|||
def es: |
|||
[ [1], |
|||
[2], |
|||
[0], |
|||
[1, 2, 4], |
|||
[5, 3], |
|||
[2, 6], |
|||
[5], |
|||
[4, 7, 6] |
|||
] |
|||
; |
|||
{ vs: vs, es: es } |
|||
| tarjan</lang> |
|||
{{out}} |
|||
<pre> |
|||
[[2,1,0],[6,5],[4,3],[7]] |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |