Module: RGFA::Connectivity

Included in:
RGFA
Defined in:
lib/rgfa/connectivity.rb

Overview

Methods which analyse the connectivity of the graph.

Instance Method Summary collapse

Instance Method Details

#connected_components ⇒ Array<Array<String>>

Find the connected components of the graph

Returns:

  • (Array<Array<String>>) —

    array of components, each an array of segment names



86
87
88
89
90
91
92
93
94
 
# File 'lib/rgfa/connectivity.rb', line 86

def connected_components
  components = []
  visited = Set.new
  segment_names.each do |sn|
    next if visited.include?(sn)
    components << segment_connected_component(sn, visited)
  end
  return components
end

#connectivity(segment) ⇒ Array<conn_symbol,conn_symbol>

Computes the connectivity of a segment from its number of links.

Connectivity symbol: (conn_symbol)

  • Let n be the number of links to an end (:B or :E) of a segment. Then the connectivity symbol is :M if n > 1, otherwise n.

Parameters:

Returns:

  • (Array<conn_symbol,conn_symbol>) —

    conn. symbols respectively of the :B and :E ends of segment.



19
20
21
22
 
# File 'lib/rgfa/connectivity.rb', line 19

def connectivity(segment)
  connectivity_symbols(links_of([segment, :B]).size,
                       links_of([segment, :E]).size)
end

#cut_link?(link) ⇒ Boolean

Does the removal of the link alone divide a component of the graph into two?

Parameters:

Returns:

  • (Boolean) 


28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/rgfa/connectivity.rb', line 28

def cut_link?(link)
  return false if link.circular?
  return true if links_of(link.from_end.invert_end_type).size == 0
  return true if links_of(link.to_end.invert_end_type).size == 0
  c = {}
  [:from, :to].each do |et|
    c[et] = Set.new
    visited = Set.new
    segend = link.send(:"#{et}_end")
    visited << segend.name
    visited << link.other_end(segend).name
    traverse_component(segend, c[et], visited)
  end
  return c[:from] != c[:to]
end

#cut_segment?(segment) ⇒ Boolean

Does the removal of the segment and its links divide a component of the graph into two?

Parameters:

Returns:

  • (Boolean) 


48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/rgfa/connectivity.rb', line 48

def cut_segment?(segment)
  segment_name = segment.kind_of?(RGFA::Line) ? segment.name : segment
  cn = connectivity(segment_name)
  return false if [[0,0],[0,1],[1,0]].include?(cn)
  start_points = []
  [:B, :E].each do |et|
    start_points += links_of([segment_name, et]).map do |l|
      l.other_end([segment_name, et]).invert_end_type
    end
  end
  cc = []
  start_points.uniq.each do |start_point|
    cc << Set.new
    visited = Set.new
    visited << segment_name
    traverse_component(start_point, cc.last, visited)
  end
  return cc.any?{|c|c != cc[0]}
end

#segment_connected_component(segment, visited = Set.new) ⇒ Array<String>

Find the connected component of the graph in which a segment is included

Parameters:

  • segment (String, RGFA::Line::Segment) —

    a segment name or instance

  • visited (Set<String>) (defaults to: Set.new) —

    a set of segments to ignore during graph traversal; all segments in the found component will be added to it

Returns:



74
75
76
77
78
79
80
81
 
# File 'lib/rgfa/connectivity.rb', line 74

def segment_connected_component(segment, visited = Set.new)
  segment_name = segment.kind_of?(RGFA::Line) ? segment.name : segment
  visited << segment_name
  c = [segment_name]
  traverse_component([segment_name, :B], c, visited)
  traverse_component([segment_name, :E], c, visited)
  return c
end

#split_connected_components ⇒ Array<RGFA>

Split connected components of the graph into single-component RGFAs

Returns:



98
99
100
101
102
103
104
105
106
107
 
# File 'lib/rgfa/connectivity.rb', line 98

def split_connected_components
  retval = []
  ccs = connected_components
  ccs.each do |cc|
    gfa2 = self.clone
    gfa2.rm(gfa2.segment_names - cc)
    retval << gfa2
  end
  return retval
end