Last active
August 29, 2015 14:27
-
-
Save mykoweb/e548236770af27147069 to your computer and use it in GitHub Desktop.
Strongly connected components solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Lecture04 | |
attr_accessor :graph_reverse, :explored, :number_nodes_processed, :current_source_vertex, :finishing_times, :leaders, :new_graph, :directory | |
def initialize(dir) | |
@directory = dir | |
@graph_reverse = {} | |
File.foreach(@directory) do |line| | |
current_edge = line.strip.split.reverse.map(&:to_i) | |
@graph_reverse[current_edge[0].to_s] = [] if @graph_reverse[current_edge[0].to_s].nil? | |
@graph_reverse[current_edge[0].to_s] << current_edge[1] | |
end;nil | |
@new_graph = {} | |
@explored = [] | |
@finishing_times = [] | |
@leaders = [] | |
@number_nodes_processed = 0 | |
@current_source_vertex = nil | |
end | |
def generate_new_graph | |
File.foreach(@directory) do |line| | |
current_edge = line.strip.split.map(&:to_i) | |
new_tail_vertex = @finishing_times[current_edge[0]-1] | |
@new_graph[new_tail_vertex.to_s] = [] if @new_graph[new_tail_vertex.to_s].nil? | |
@new_graph[new_tail_vertex.to_s] << @finishing_times[current_edge[1]-1] | |
end;nil | |
end | |
def dfs_loop(number_of_vertices) | |
number_of_vertices.downto(1) do |vertex| | |
unless @explored[vertex-1] | |
@current_source_vertex = vertex | |
dfs(vertex) | |
end | |
end | |
end | |
def dfs(vertex) | |
@explored[vertex-1] = true | |
unless @graph_reverse[vertex.to_s].nil? | |
@graph_reverse[vertex.to_s].each do |v| | |
dfs(v) unless @explored[v-1] | |
end | |
end | |
@number_nodes_processed += 1 | |
@finishing_times[vertex-1] = @number_nodes_processed | |
end | |
def dfs_loop_2nd_pass(number_of_vertices) | |
@explored = [] | |
@current_source_vertex = nil | |
number_of_vertices.downto(1) do |vertex| | |
unless @explored[vertex-1] | |
@current_source_vertex = vertex | |
dfs_2nd_pass(vertex) | |
end | |
end | |
end | |
def dfs_2nd_pass(vertex) | |
@explored[vertex-1] = true | |
@leaders[vertex-1] = @current_source_vertex | |
unless @new_graph[vertex.to_s].nil? | |
@new_graph[vertex.to_s].each do |v| | |
dfs_2nd_pass(v) unless @explored[v-1] | |
end | |
end | |
end | |
end | |
directory = '' | |
lecture = Lecture04.new directory | |
lecture.dfs_loop 875714 | |
lecture.generate_new_graph | |
lecture.dfs_loop_2nd_pass 875714 | |
answer = lecture.leaders.group_by {|x| x}.values.map(&:count).sort.reverse.take(5).inspect | |
puts answer |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment