Strongly Connected Components in JavaScript and Ruby

Source.js

// requires prototype for some of its synctactic sugar

var Undiscovered = 0;
var Discovered = 1;
var Processed = 2;
var time = 0;
var scc_count = 0;
var states = {};
var et = {};
var low = {};
var scc = {};
var active = [];
var graph = {};

function dfs( node, parent ) {
    states[node] = Discovered;

    time += 1;
    et[node] = time;

    active.push( node );

    graph.edges[node].each( function(n){
                                  if( states[n] == Undiscovered ) {
                                      dfs( n, node );
                                  }
                                  else if (states[n] == Discovered ) {
                                      if( et[n] < et[low[node]] )
                                            low[node] = n;
                                  }
                                  else if ( states[n] == Processed && et[n] < et[node] ) {
                                      if( scc[n] == -1 && et[low[n]] < et[low[node]] )
                                            low[node] = low[node];
                                  }
                            });

    if( low[node] == node ) {
          scc_count += 1;
          scc[node] = scc_count;
          var n = active.pop();
          while( n != node ) {
              scc[n] = scc_count;
              n = active.pop();
          }
    }

    if( parent && et[low[node]] < et[low[parent]])
          low[parent] = low[node];

    states[node] = Processed;
}

function scc_sets() {
    scc_sets = [];

    for( var i = 1; i <= scc_count; i++ ) {
          var scc_set = [];
          for( var k in scc ) {
              if (scc[k] == i)
                    scc_set.push( k );
          }
          scc_sets.push( scc_set );
    }
    return scc_sets;
}

function clear_state() {
    time = 0;
    active = [];
    scc_count = 0;
    states = {};
    et = {};
    low = {};
    scc = {};

    graph.vertices.each( function(n){
                               states[n] = Undiscovered;
                               et[n] = -1;
                               scc[n] = -1;
                               low[n] = n;
                         });
}

function out(s) {
    document.write(s + "\n");
}

function strongly_connected_components() {
    clear_state();
    graph.vertices.each( function(n){
                               if( states[n] == Undiscovered )
                                   dfs(n,null);
                         });
    scc_sets().each( function(set){
                           out("{" + set.join(", ") + "}");
                     });
}

function main() {
    graph = {
          vertices: [ 'A', 'B', 'C', 'D', 'E' ],
          edges: {
              'A': ['B'],
              'B': ['A','C'],
              'C': ['A','D'],
              'D': ['E'],
              'E': ['D']
          }
    }

    strongly_connected_components();
}
// Output
// {D, E}
// {A, B, C}

Source.rb

#!/usr/bin/ruby

class Graph
  def initialize(input)
    @state = {}
    @et = {}
    @low = {}
    @scc = {}
    @active = []
    @time = 0
    @scc_count = 0
    @graph = {}
    input.each_line do |line|
      line.strip!
      next if line.empty?
      line =~ /([A-Z]): ?([A-Z](, [A-Z])*)?/
      @graph[$1] = $2.split(", ")
    end
  end
  def to_s
    @graph.inject("") do |s,k| 
      elems = k.last.join(", ")
      s << "#{k.first} => #{elems}\n"
    end
  end
  def dfs(node, parent = nil)
    @state[node] = :discovered
    @time = @time + 1
    @et[node] = @time
    @active.unshift( node )
    @graph[node].each do |n|
      if @state[n] == :undiscovered
        dfs(n, node)
      elsif @state[n] == :discovered and @et[n] < @et[@low[node]]
          @low[node] = n
      elsif @state[n] == :processed and
        not @scc[n] and @et[@low[n]] < @et[@low[node]]
        @low[node] = @low[n]
      end
    end
    if @low[node] == node
      @scc_count += 1
      @scc[node] = @scc_count
      n = @active.shift
      while( n != node ) do
        @scc[n] = @scc_count
        n = @active.shift
      end
    end
    @low[parent] = @low[node] if parent and @et[@low[node]] < @et[@low[parent]]
    @state[node] = :processed
  end
  def strongly_connected_components
    @scc_count = 0
    @time = 0
    @state = {}
    @et = {}
    @low = {}
    @scc = {}
    @graph.keys.each do |k|
      @state[k] = :undiscovered
      @low[k] = k
      @scc[k] = nil
    end
    @graph.keys.each do |k|
      dfs(k) if @state[k] == :undiscovered
    end
    scc_sets = {}
    (1..@scc_count).each do |i|
      scc_sets[i] = []
      @scc.each_pair do |k,v| scc_sets[i] << k if v == i; end
    end
    scc_sets.inject("") do |s,e|
      body = e.last.join(", ")
      s << "{#{body}}\n"
    end
  end
end
g = Graph.new( STDIN )
puts g.to_s
puts g.strongly_connected_components

## Test Case 1:
# A: B
# B: C
# C: A
## Result 1:
# { A, B, C }