module RCPM
Constants
- VERSION
Public Class Methods
cpm(g, k)
click to toggle source
# File lib/rcpm.rb, line 41 def self.cpm(g, k) cliques_to_components = {} current_component = 0 cliques = g.bk.select{|cl| cl.size >= k} nodes_to_cliques = nodes_to_cliques(cliques) #Para cada uma das cliques cliques.each do |clique| #Se ela ainda não possui componente(não foi processada) if !cliques_to_components.key?(clique) current_component += 1 #Adiciona um novo componente para ela cliques_to_components[clique] = current_component #Coloca esta clique na fronteira frontier = [clique] #Enquanto fronteira não for vazia while current_clique = frontier.pop #Pega todas as cliques vizinhas de current_clique get_adjacent_cliques(current_clique, nodes_to_cliques).each do |neighbour| #Se neighbour tem uma interseção com current_clique de tamanho >= k - 1 if (current_clique & neighbour).size >= k - 1 #Então neighbour também faz parte de current_component cliques_to_components[neighbour] = current_component #Adiciona neighbour à frontier frontier << neighbour #E para cada node de neighbour neighbour.each do |node| #Remove ele da lista de nós não processados nodes_to_cliques[node].delete(neighbour) end end end end end end #Agora basta unir todos os nós que foram rotulados com o mesmo componente component_to_nodes = {} cliques_to_components.each_pair do |clique, component_clique_in| component_to_nodes[component_clique_in] ||= [] component_to_nodes[component_clique_in] += clique end return component_to_nodes.values end
graph_to_matrix(ary)
click to toggle source
# File lib/rcpm.rb, line 26 def self.graph_to_matrix(ary) max = ary.flatten.max matrix = Array.new(max + 1) { Array.new(max + 1, 0) } 0.upto(max - 1) { |i| matrix[i][i] = 1 } ary.each do |n1, n2| matrix[n1][n2] = 1 matrix[n2][n1] = 1 end return matrix end
read_file(filename)
click to toggle source
# File lib/rcpm.rb, line 5 def self.read_file(filename) current_id = {} code_to_id = {} graphs = {} CSV.open(filename, headers: [:id1, :id2, :year]).each do |line| year = line[:year] current_id[year] ||= -1 code_to_id[year] ||= {} graphs[year] ||= [] id1 = code_to_id[year][line[:id1]] ||= current_id[year] += 1 id2 = code_to_id[year][line[:id2]] ||= current_id[year] += 1 graphs[year] << [id1,id2] end return [code_to_id, graphs] end
Private Class Methods
get_adjacent_cliques(clique, nodes_to_cliques)
click to toggle source
Dado uma clique, retorna todas as outras adjacentes à ela. Duas cliques são adjacentes se elas compartilham ao menos um nó
# File lib/rcpm.rb, line 106 def self.get_adjacent_cliques(clique, nodes_to_cliques) adjacent_cliques = [] clique.each do |node| nodes_to_cliques[node].each do |adj_clique| if clique != adj_clique adjacent_cliques << adj_clique end end end return adjacent_cliques end
nodes_to_cliques(cliques)
click to toggle source
Cria um hash do tipo node -> [cliques que contém node]
# File lib/rcpm.rb, line 93 def self.nodes_to_cliques(cliques) output = Hash.new {|h,k| h[k] = []} cliques.each do |clique| clique.each do |node| output[node] << clique end end return output end