Rosetta Code

Tarjan: Difference between revisions

Page Discussion

Tarjan (view source)

Revision as of 21:41, 23 September 2020

4,813 bytes added ,  3 years ago
Add source for Rust
m (→‎{{header|REXX}}: corrected the language name (of REXXl ---> REXX) in the section header for the REXX language entry.)
(Add source for Rust)
Line 14:
class Node
{
public int LowLink { get; set; }
public int Index { get; set; }
public int N { get; }
 
public Node(int n)
{
{
N = n;
Index = -1;
LowLink = 0;
}
}
}
 
class Graph
{
public HashSet<Node> V { get; }
public Dictionary<Node, HashSet<Node>> Adj { get; }
 
/// <summary>
/// Tarjan's strongly connected components algorithm
/// </summary>
public void Tarjan()
{
{
var index = 0; // number of nodes
var S = new Stack<Node>();
 
Action<Node> StrongConnect = null;
StrongConnect = (v) =>
{
{
// Set the depth index for v to the smallest unused index
v.Index = index;
v.LowLink = index;
 
index++;
S.Push(v);
 
// Consider successors of v
foreach (var w in Adj[v])
if (w.Index < 0)
{
{
// Successor w has not yet been visited; recurse on it
StrongConnect(w);
v.LowLink = Math.Min(v.LowLink, w.LowLink);
}
}
else if (S.Contains(w))
// Successor w is in stack S and hence in the current SCC
v.LowLink = Math.Min(v.LowLink, w.Index);
 
// If v is a root node, pop the stack and generate an SCC
if (v.LowLink == v.Index)
{
{
Console.Write("SCC: ");
 
Node w;
do
do
{
{
w = S.Pop();
Console.Write(w.N + " ");
} while (w != v);
 
Console.WriteLine();
}
}
};
};
 
foreach (var v in V)
if (v.Index < 0)
StrongConnect(v);
}
}
}</lang>
 
Line 206:
auto gary = g.add_vertex("Gary");
auto hank = g.add_vertex("Hank");
 
andy->add_neighbour(bart);
bart->add_neighbour(carl);
Line 215:
gary->add_neighbour(fred);
hank->add_neighbours({earl, gary, hank});
 
tarjan<std::string> t;
for (auto&& s : t.run(g))
Line 339:
typealias Nodes = List<Node>
 
class Node(val n: Int) {
var index = -1 // -1 signifies undefined
var lowLink = -1
Line 353:
var index = 0
val s = Stack<Node>()
 
fun strongConnect(v: Node) {
// Set the depth index for v to the smallest unused index
v.index = index
v.lowLink = index
index++
s.push(v)
v.onStack = true
 
// consider successors of v
for (w in g.es[v]!!) {
Line 382:
w.onStack = false
scc.add(w)
}
while (w != v)
sccs.add(scc)
Line 390:
for (v in g.vs) if (v.index < 0) strongConnect(v)
return sccs
}
 
fun main(args: Array<String>) {
val vs = (0..7).map { Node(it) }
val es = mapOf(
vs[0] to listOf(vs[1]),
Line 406:
val g = DirectedGraph(vs, es)
val sccs = tarjan(g)
println(sccs.joinToString("\n"))
}</lang>
 
Line 917:
(define store (make-hash))
(define (make-node v) (hash-ref! store v (thunk (node v #f #f #f))))
 
;; it's important that we use hasheq instead of hash so that we compare
;; reference instead of actual value. Had we use the actual value,
Line 1,118:
[3 4]
[7]</pre>
 
=={{header|Rust}}==
<lang Rust>use std::collections::{BTreeMap, BTreeSet};
 
// Using a naked BTreeMap would not be very nice, so let's make a simple graph representation
#[derive(Clone, Debug)]
pub struct Graph {
neighbors: BTreeMap<usize, BTreeSet<usize>>,
}
 
impl Graph {
pub fn new(size: usize) -> Self {
Self {
neighbors: (0..size).fold(BTreeMap::new(), |mut acc, x| {
acc.insert(x, BTreeSet::new());
acc
}),
}
}
 
pub fn edges<'a>(&'a self, vertex: usize) -> impl Iterator<Item = usize> + 'a {
self.neighbors[&vertex].iter().cloned()
}
 
pub fn add_edge(&mut self, from: usize, to: usize) {
assert!(to < self.len());
self.neighbors.get_mut(&from).unwrap().insert(to);
}
 
pub fn add_edges(&mut self, from: usize, to: impl IntoIterator<Item = usize>) {
let limit = self.len();
 
self.neighbors
.get_mut(&from)
.unwrap()
.extend(to.into_iter().filter(|x| {
assert!(*x < limit);
true
}));
}
 
pub fn is_empty(&self) -> bool {
self.neighbors.is_empty()
}
 
pub fn len(&self) -> usize {
self.neighbors.len()
}
}
 
#[derive(Clone)]
struct VertexState {
index: usize,
low_link: usize,
on_stack: bool,
}
 
// The easy way not to fight with Rust's borrow checker is moving the state in
// a structure and simply invoke methods on that structure.
 
pub struct Tarjan<'a> {
graph: &'a Graph,
index: usize,
stack: Vec<usize>,
state: Vec<VertexState>,
components: Vec<BTreeSet<usize>>,
}
 
impl<'a> Tarjan<'a> {
// Having index: Option<usize> would look nicer, but requires just
// some unwraps and Vec has actual len limit isize::MAX anyway, so
// we can reserve this large value as the invalid one.
const INVALID_INDEX: usize = usize::MAX;
 
pub fn walk(graph: &'a Graph) -> Vec<BTreeSet<usize>> {
Self {
graph,
index: 0,
stack: Vec::new(),
state: vec![
VertexState {
index: Self::INVALID_INDEX,
low_link: Self::INVALID_INDEX,
on_stack: false
};
graph.len()
],
components: Vec::new(),
}
.visit_all()
}
 
fn visit_all(mut self) -> Vec<BTreeSet<usize>> {
for vertex in 0..self.graph.len() {
if self.state[vertex].index == Self::INVALID_INDEX {
self.visit(vertex);
}
}
 
self.components
}
 
fn visit(&mut self, v: usize) {
let v_ref = &mut self.state[v];
v_ref.index = self.index;
v_ref.low_link = self.index;
self.index += 1;
self.stack.push(v);
v_ref.on_stack = true;
 
for w in self.graph.edges(v) {
let w_ref = &self.state[w];
if w_ref.index == Self::INVALID_INDEX {
self.visit(w);
let w_low_link = self.state[w].low_link;
let v_ref = &mut self.state[v];
v_ref.low_link = v_ref.low_link.min(w_low_link);
} else if w_ref.on_stack {
let w_index = self.state[w].index;
let v_ref = &mut self.state[v];
v_ref.low_link = v_ref.low_link.min(w_index);
}
}
 
let v_ref = &self.state[v];
if v_ref.low_link == v_ref.index {
let mut component = BTreeSet::new();
 
loop {
let w = self.stack.pop().unwrap();
self.state[w].on_stack = false;
component.insert(w);
if w == v {
break;
}
}
 
self.components.push(component);
}
}
}
 
fn main() {
let graph = {
let mut g = Graph::new(8);
g.add_edge(0, 1);
g.add_edge(2, 0);
g.add_edges(5, vec![2, 6]);
g.add_edge(6, 5);
g.add_edge(1, 2);
g.add_edges(3, vec![1, 2, 4]);
g.add_edges(4, vec![5, 3]);
g.add_edges(7, vec![4, 7, 6]);
g
};
 
for component in Tarjan::walk(&graph) {
println!("{:?}", component);
}
}</lang>
 
{{out}}
<pre>
{0, 1, 2}
{5, 6}
{3, 4}
{7}
</pre>
 
=={{header|Sidef}}==
Line 1,196 ⟶ 1,364:
const INDEX=0, LOW_LINK=1, ON_STACK=2;
fcn init(graph){
var index=0, stack=List(), components=List(),
G=List.createLong(graph.len(),0);
 
Line 1,208 ⟶ 1,376:
foreach c in (components){ println(c.reverse().concat(",")) }
 
returnClass(components); // over-ride return of class instance
}
fcn strongConnect(v){ // v is ( (index,lowlink,onStack), (id,links) )
Line 1,219 ⟶ 1,387:
// Consider successors of v
foreach idx in (v[1][1,*]){ // links of v to other vs
w,w0 := G[idx],w[0]; // well, that is pretty vile
if(w[0][INDEX]==Void){
strongConnect(w); // Successor w not yet visited; recurse on it
v0[LOW_LINK]=v0[LOW_LINK].min(w0[LOW_LINK]);
}
else if(w0[ON_STACK])
// Successor w is in stack S and hence in the current SCC
v0[LOW_LINK]=v0[LOW_LINK].min(w0[INDEX]);
}
// If v is a root node, pop the stack and generate an SCC
if(v0[LOW_LINK]==v0[INDEX]){
strong:=List(); // start a new strongly connected component
do{
w,w0 := stack.pop(), w[0];
w0[ON_STACK]=False;
strong.append(w[1][0]); // add w to strongly connected component
}while(w.id!=v.id);
components.append(strong); // output strongly connected component
}
}
Line 1,243 ⟶ 1,411:
// with vertices id zero based (vs 1 based in article)
// ids start at zero and are consecutive (no holes), graph is unsorted
graph:= // ( (id, links/Edges), ...)
T( T(0,1), T(2,0), T(5,2,6), T(6,5),
T(1,2), T(3,1,2,4), T(4,5,3), T(7,4,7,6) );
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/274241"