Anonymous user
Tarjan: Difference between revisions
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
{
{
}
}
class Graph
{
{
{
{
}
{
do
{
}
};
}
}</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);
}
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];
}
// 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
}
}
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:=
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) );
|