Tarjan: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
| (14 intermediate revisions by 2 users not shown) | |||
Line 13:
;References:
* The article on [[wp:Tarjan's_strongly_connected_components_algorithm|Wikipedia]].
See also: [[Kosaraju]]
<br><br>
Line 622 ⟶ 624:
[7]
</pre>
=={{header|J}}==
Brute force implementation from wikipedia pseudocode:
<syntaxhighlight lang=J>tarjan=: {{
coerase ([ cocurrent) cocreate'' NB. following =: declarations are temporary, expiring when we finish
graph=: y NB. connection matrix of a directed graph
result=: stack=: i.index=: 0
undef=: #graph
lolinks=: indices=: undef"_1 graph
onstack=: 0"_1 graph
strongconnect=: {{
indices=: index y} indices
lolinks=: index y} lolinks
onstack=: 1 y} onstack
stack=: stack,y
index=: index+1
for_w. y{::graph do.
if. undef = w{indices do.
strongconnect w
lolinks=: (<./lolinks{~y,w) y} lolinks
elseif. w{onstack do.
lolinks=: (<./lolinks{~y,w) y} lolinks
end.
end.
if. lolinks =&(y&{) indices do.
loc=. stack i. y
component=. loc }. stack
onstack=: 0 component} onstack
result=: result,<component
stack=: loc {. stack
end.
}}
for_Y. i.#graph do.
if. undef=Y{indices do.
strongconnect Y
end.
end.
result
}}</syntaxhighlight>
Example use, with graph from wikipedia animated example:
<syntaxhighlight lang=J> tarjan 1;2;0;1 2 4;3 5;2 6;5;4 6 7
┌─────┬───┬───┬─┐
│0 1 2│5 6│3 4│7│
└─────┴───┴───┴─┘</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
public final class TarjanSCC {
public static void main(String[] aArgs) {
Graph graph = new Graph(8);
graph.addDirectedEdge(0, 1);
graph.addDirectedEdge(1, 2); graph.addDirectedEdge(1, 7);
graph.addDirectedEdge(2, 3); graph.addDirectedEdge(2, 6);
graph.addDirectedEdge(3, 4);
graph.addDirectedEdge(4, 2); graph.addDirectedEdge(4, 5);
graph.addDirectedEdge(6, 3); graph.addDirectedEdge(6, 5);
graph.addDirectedEdge(7, 0); graph.addDirectedEdge(7, 6);
System.out.println("The strongly connected components are: ");
for ( Set<Integer> component : graph.getSCC() ) {
System.out.println(component);
}
}
}
final class Graph {
public Graph(int aSize) {
adjacencyLists = new ArrayList<Set<Integer>>(aSize);
for ( int i = 0; i < aSize; i++ ) {
vertices.add(i);
adjacencyLists.add( new HashSet<Integer>() );
}
}
public void addDirectedEdge(int aFrom, int aTo) {
adjacencyLists.get(aFrom).add(aTo);
}
public List<Set<Integer>> getSCC() {
for ( int vertex : vertices ) {
if ( ! numbers.keySet().contains(vertex) ) {
stronglyConnect(vertex);
}
}
return stronglyConnectedComponents;
}
private void stronglyConnect(int aVertex) {
numbers.put(aVertex, index);
lowlinks.put(aVertex, index);
index += 1;
stack.push(aVertex);
for ( int adjacent : adjacencyLists.get(aVertex) ) {
if ( ! numbers.keySet().contains(adjacent) ) {
stronglyConnect(adjacent);
lowlinks.put(aVertex, Math.min(lowlinks.get(aVertex), lowlinks.get(adjacent)));
} else if ( stack.contains(adjacent) ) {
lowlinks.put(aVertex, Math.min(lowlinks.get(aVertex), numbers.get(adjacent)));
}
}
if ( lowlinks.get(aVertex) == numbers.get(aVertex) ) {
Set<Integer> stonglyConnectedComponent = new HashSet<Integer>();
int top;
do {
top = stack.pop();
stonglyConnectedComponent.add(top);
} while ( top != aVertex );
stronglyConnectedComponents.add(stonglyConnectedComponent);
}
}
private List<Set<Integer>> adjacencyLists;
private List<Integer> vertices = new ArrayList<Integer>();
private int index = 0;
private Stack<Integer> stack = new Stack<Integer>();
private Map<Integer, Integer> numbers = new HashMap<Integer, Integer>();
private Map<Integer, Integer> lowlinks = new HashMap<Integer, Integer>();
private List<Set<Integer>> stronglyConnectedComponents = new ArrayList<Set<Integer>>();
}
</syntaxhighlight>
{{ out }}
<pre>
The strongly connected components are:
[5]
[2, 3, 4, 6]
[0, 1, 7]
</pre>
Line 748 ⟶ 888:
Results in the zero-base scheme: Array{Int64,1}[[2, 1, 0], [6, 5], [4, 3], [7]]
</pre>
=={{header|K}}==
Implementation:
<syntaxhighlight lang=K>F:{[g]
r::s::!i::0
t::+`o`j`k!(#g)#'0,2##g
L::{[g;v]
t[v]:1,i,i; s,:v; i+:1
{[g;v;w]
$[t[`k;w]=#g; L w; ~t[`o;w]; :0N]
t[`j;v]&:t[`j;w]}[g;v]'g v
$[=/t[`j`k;v]
[a:*&v=s; c:a_s; t[`o;c]:0; s::a#s; r,:,c]
]}[g]
{[g;v] $[t[`k;v]=#g; L v; ]}[g]'!#g
r}</syntaxhighlight>
Example:
<syntaxhighlight lang=K>F (1;2;0;1 2 4;3 5;2 6;5;4 6 7)
(0 1 2
5 6
3 4
,7)</syntaxhighlight>
tested with ngn/k
=={{header|Kotlin}}==
Line 1,869 ⟶ 2,035:
{{libheader|Wren-seq}}
{{libheader|Wren-dynamic}}
<syntaxhighlight lang="
import "./dynamic" for Tuple
class Node {
| |||