Class: ArtDecomp::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/art-decomp/graph.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(blanket, seps) ⇒ Graph

Returns a new instance of Graph.



5
6
7
8
9
10
11
12
 
# File 'lib/art-decomp/graph.rb', line 5

def initialize blanket, seps
  @vertices = blanket.ints.dup
  @vertices.delete_if { |this| @vertices.any? { |other| other != this and other & this == this } }
  relevant = Hash[@vertices.map { |v| [v, seps.select { |s| v&s != 0 and v&s != s }.to_set] }]
  @edges = @vertices.pairs.select do |a, b|
    (relevant[a] & relevant[b]).any? { |s| a&s != b&s }
  end.map(&:to_set).to_set
end

Instance Attribute Details

#edges ⇒ Object (readonly)

Returns the value of attribute edges.



3
4
5
 
# File 'lib/art-decomp/graph.rb', line 3

def edges
  @edges
end

#vertices ⇒ Object (readonly)

Returns the value of attribute vertices.



3
4
5
 
# File 'lib/art-decomp/graph.rb', line 3

def vertices
  @vertices
end

Instance Method Details

#adjacent(*vertices) ⇒ Object 



14
15
16
17
 
# File 'lib/art-decomp/graph.rb', line 14

def adjacent *vertices
  return Set[] if @edges.all? { |edge| (edge & vertices).empty? }
  @edges.reject { |edge| (edge & vertices).empty? }.inject(:|) - vertices
end

#blanket_from_colouring ⇒ Object 



19
20
21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/art-decomp/graph.rb', line 19

def blanket_from_colouring
  colours = {}
  @vertices.sort_by { |vert| [-degree(vert), vert] }.each do |vertex|
    forbidden = adjacent(vertex).map { |vert| colours[vert] }.to_set
    # FIXME: consider selecting colours on the least-popular-first basis
    colour = :a
    colour = colour.next while forbidden.include? colour
    colours[vertex] = colour
  end
  blocks = Hash.new 0
  colours.each { |vertex, colour| blocks[colour] |= vertex }
  Blanket.new blocks.values
end

#complete? ⇒ Boolean

Returns:

  • (Boolean) 


33
34
35
 
# File 'lib/art-decomp/graph.rb', line 33

def complete?
  2 * @edges.size == @vertices.size * (@vertices.size - 1)
end

#degree(vertex) ⇒ Object 



37
38
39
 
# File 'lib/art-decomp/graph.rb', line 37

def degree vertex
  @edges.count { |edge| edge.include? vertex }
end

#merge_by_edge_labels! ⇒ Object 



41
42
43
44
45
46
47
48
49
50
 
# File 'lib/art-decomp/graph.rb', line 41

def merge_by_edge_labels!
  return self if @vertices.size == 1
  pins = @vertices.size.log2_ceil
  until @vertices.size.log2_ceil < pins
    # FIXME: edge labels can/should be cached from previous computations
    a, b = *@edges.sort_by { |edge| yield *edge }.first
    merge! a, b
  end
  self
end

#merge_by_vertex_degrees! ⇒ Object 



52
53
54
55
56
57
58
59
 
# File 'lib/art-decomp/graph.rb', line 52

def merge_by_vertex_degrees!
  pins = @vertices.size.log2_ceil
  until @vertices.size.log2_ceil < pins or complete?
    a, b = *@vertices.sort_by { |v| -degree(v) }.pairs.find { |v1, v2| not @edges.include? Set[v1, v2] }
    merge! a, b
  end
  self
end

#merge_until_complete! ⇒ Object 



61
62
63
64
 
# File 'lib/art-decomp/graph.rb', line 61

def merge_until_complete!
  merge_by_vertex_degrees! until complete?
  self
end