Module: Graph

Included in:
Chem::Molecule
Defined in:
lib/graph.rb,
lib/graph/morgan.rb,
lib/graph/cluster.rb,
lib/chem/utils/ullmann.rb,
lib/chem/utils/graph_db.rb

Defined Under Namespace

Classes: SubGraphDB

Instance Attribute Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#adjacencies(atom) ⇒ Object

Returns the value of attribute adjacencies.



15
16
17
 
# File 'lib/graph.rb', line 15

def adjacencies
  @adjacencies
end

#edges ⇒ Object

Returns the value of attribute edges.



15
16
17
 
# File 'lib/graph.rb', line 15

def edges
  @edges
end

#nodes ⇒ Object

Returns the value of attribute nodes.



15
16
17
 
# File 'lib/graph.rb', line 15

def nodes
  @nodes
end

Instance Method Details

#adj_matrix ⇒ Object 



17
18
19
20
21
22
23
24
25
26
27
 
# File 'lib/chem/utils/ullmann.rb', line 17

def adj_matrix
  n_long = (nodes.length - 1) / 32 + 1
  mat = Array.new(n_long * @nodes.length, 0)
  nodes.each_with_index do |node, idx|
    adjacent_to(node).each do |bond, node|
      keta = nodes.index(node) / 32
      mat[idx * n_long + keta] += 1 << (nodes.index(node) - keta * 32)
    end
  end
  mat.pack("L*")
end

#adjacency_list ⇒ Object 



102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/chem/utils/ullmann.rb', line 102

def adjacency_list
  ret = []
  @nodes.each do |node|
    r = []
    self.adjacent_to(node).each do |bond, to|
      r << @nodes.index(to)
    end
    ret << r
  end
  ret
end

#adjacent_to(atom) ⇒ Object 



23
24
25
26
27
28
29
30
31
32
33
34
35
 
# File 'lib/graph.rb', line 23

def adjacent_to(atom)
  #       instance_eval "alias :tmp_adjacent_to :adjacent_to"
  #       instance_eval "alias :adjacent_to :adjacencies"
  if @adjacencies == nil
    @adjacencies = {}
    @edges.each do |bond, atom_a, atom_b|
      (@adjacencies[atom_a] ||= []).push([bond, atom_b])
      (@adjacencies[atom_b] ||= []).push([bond, atom_a])
    end
  end
  @adjacencies[atom] ||= []
  @adjacencies[atom]
end

#clustering_coefficient ⇒ Object 



4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
# File 'lib/graph/cluster.rb', line 4

def clustering_coefficient
  cc = {} # clustering coefficient
  @nodes.each do |node|
    c = 0
    adj = adjacent_to(node)
    adj_nodes = adj.collect{|e, n| n}
    adj.each do |ed, nd|
      adjacent_to(nd).each do |e, n|
        c += 1 if adj_nodes.include?(n)
      end
    end
    cc[node] = c
  end
  cc
end

#connection ⇒ Object

Obsolete!?



115
116
117
118
119
120
121
122
123
124
125
 
# File 'lib/chem/utils/ullmann.rb', line 115

def connection
  self_adj = []
  @nodes.each do |node|
    i = 0
    self.adjacent_to(node).each do |bond, to|
      i += 1<< @nodes.index(to)
    end
    self_adj << i
  end
  self_adj
end

#each ⇒ Object 



17
18
19
20
21
 
# File 'lib/graph.rb', line 17

def each
  @nodes.each do |atom|
    yield atom
  end
end

#match_by_adj_mat(mat, len) ⇒ Object 



29
30
31
32
 
# File 'lib/chem/utils/ullmann.rb', line 29

def match_by_adj_mat mat, len
  m = Array.new("0xff", 100).pack("c*")
  subcomp_match_by_ullmann(mat, len, self.adjacency_list, self.nodes.length, m)
end

#match_by_ullmann(other, &block) ⇒ Object Also known as: match 



34
35
36
37
38
39
 
# File 'lib/chem/utils/ullmann.rb', line 34

def match_by_ullmann other, &block
  if other.nodes.length == 1
    self.nodes.find{|node| node.element == other.nodes[0].element}
  end
  subcomp_match_by_ullmann(adj_matrix, nodes.length, other.adjacency_list, other.nodes.length, other.matchable(self, &block))
end

#match_exhaustively(other) ⇒ Object

returns match correspondences without duplicate



43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
# File 'lib/chem/utils/ullmann.rb', line 43

def match_exhaustively other
  correspond = {}
  result = []
  while true
    match = self.match_by_ullmann(other) do |a, b|
      a.element == b.element and not (correspond[a] and correspond[a].include? b)
    end
    break if not match
    result.push(match)
    match.each_with_index do |n, m|
      (correspond[other.nodes[n]] ||=[]).push @nodes[m]
    end
  end
  result
end

#matchable(other, exlucde = {}) ⇒ Object 



59
60
61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/chem/utils/ullmann.rb', line 59

def matchable other, exlucde = {}
  n_long = (other.nodes.length - 1) / 32 + 1
  mat = Array.new(n_long * @nodes.length, 0)
  @nodes.each_with_index do |node, index|
    other.nodes.each_with_index do |n, idx|
      if node.element == n.element
        keta = idx / 32
        mat[index * n_long + keta] += 1 << (idx - keta * 32)
      end
    end
  end
  mat.pack("L*")
end

#matchable_old(other, exlucde = {}) ⇒ Object

obsolete



74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/chem/utils/ullmann.rb', line 74

def matchable_old other, exlucde = {}
  n_long = (other.nodes.length - 1) / 32 + 1
  row_unit = n_long * ( 32 / 8)
  r = "\0" * 10000
  if block_given?
    @nodes.each_with_index do |node, index|
      other.nodes.each_with_index do |o_node, idx|
        if yield(node, o_node)
          col_byte = idx / 8
          col_bit  = idx - col_byte * 8
          r[index * row_unit + col_byte] += (1 << col_bit)
        end
      end
    end
  else
    @nodes.each_with_index do |node, index|
      other.nodes.each_with_index do |o_node, idx|
        if node.element == o_node.element or node.element == :R or o_node.element == :R
          col_byte = idx / 8
          col_bit  = idx - col_byte * 8
          r[index * row_unit + col_byte] += (1 << col_bit)
        end
      end
    end
  end
  r
end

#morgan ⇒ Object 



3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/graph/morgan.rb', line 3

def morgan
  ec = {}  # extended connectivity
  tec = {} # trial extended connectivity

  @nodes.each{ |a| tec[a] = 1 }

  k = 0
  k2 = k + 1

  while k2 > k
    k = k2
    @nodes.each{ |a| ec[a] = tec[a] }

    @nodes.each do |a|
      tec[a] = adjacent_to(a).inject(0){|ret, (b, n)| ret + ec[n]}
    end
    k2 = @nodes.collect{|a| tec[a]}.uniq.length
  end

  #      calc morgan tree
  max = @nodes.max{|a, b| tec[a] <=> tec[b]}

  queue = [ max ]
  traversed = [ max ]

  while from = queue.shift
    adjacent_to(from).sort{|(b1, n), (b2, m)| tec[m] <=> tec[n]}.each do |bond, atom|
      unless traversed.include?(atom)
        queue.push(atom)
        traversed.push(atom)
      end
    end
  end
  [ec, tec, traversed]
end