Class: ArtDecomp::Graph

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

Instance Method Summary collapse

Constructor Details

#initialize(blanket, seps) ⇒ Graph

Returns a new instance of Graph.



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

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

Instance Method Details

#adjacent(*vertices) ⇒ Object 



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

def adjacent *vertices
  vertices.map { |vertex| @neighbours[vertex] }.inject(:|) - vertices
end

#blanket_from_colouring ⇒ Object 



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

def blanket_from_colouring
  colours = {}
  @neighbours.keys.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) 


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

def complete?
  @neighbours.values.map(&:size).inject(:+) == @neighbours.size * (@neighbours.size - 1)
end

#degree(vertex) ⇒ Object 



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

def degree vertex
  @neighbours[vertex].size
end

#edges ⇒ Object 



42
43
44
 
# File 'lib/art-decomp/graph.rb', line 42

def edges
  @neighbours.map { |v, adjacents| adjacents.map { |adj| Set[v, adj] } }.flatten.to_set
end

#merge_by_edge_labels! ⇒ Object 



46
47
48
49
50
51
52
53
54
55
 
# File 'lib/art-decomp/graph.rb', line 46

def merge_by_edge_labels!
  return self if @neighbours.size == 1
  pins = @neighbours.size.log2_ceil
  until @neighbours.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 



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

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

#merge_until_complete! ⇒ Object 



66
67
68
69
 
# File 'lib/art-decomp/graph.rb', line 66

def merge_until_complete!
  merge_by_vertex_degrees! until complete?
  self
end

#vertices ⇒ Object 



71
72
73
 
# File 'lib/art-decomp/graph.rb', line 71

def vertices
  @neighbours.keys.to_set
end