Module: RCPM

Defined in:
lib/rcpm.rb,
lib/rcpm/version.rb

Constant Summary collapse

VERSION = 
"0.1.3"

Class Method Summary collapse

Class Method Details

.cpm(g, k) ⇒ Object 



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# 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) ⇒ Object 



26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# 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) ⇒ Object 



5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
# 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