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