module RGFA::Connectivity

Methods which analyse the connectivity of the graph.

Public Instance Methods

connected_components() click to toggle source

Find the connected components of the graph @return [Array<Array<String>>]

array of components, each an array of segment names
# 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) click to toggle source

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

@param segment [String|RGFA::Line::Segment] segment name or instance

@return [Array<conn_symbol,conn_symbol>]

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

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.

# File lib/rgfa/connectivity.rb, line 19
def connectivity(segment)
  connectivity_symbols(links_of([segment, :B]).size,
                       links_of([segment, :E]).size)
end
cut_segment?(segment) click to toggle source

Does the removal of the segment and its links divide a component of the graph into two? @param segment [String, RGFA::Line::Segment] a segment name or instance @return [Boolean]

# 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) click to toggle source

Find the connected component of the graph in which a segment is included @return [Array<String>]

array of segment names

@param segment [String, RGFA::Line::Segment] a segment name or instance @param visited [Set<String>] a set of segments to ignore during graph

traversal; all segments in the found component will be added to it
# 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() click to toggle source

Split connected components of the graph into single-component RGFAs @return [Array<RGFA>]

# 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

Private Instance Methods

connectivity_symbol(n) click to toggle source
# File lib/rgfa/connectivity.rb, line 127
def connectivity_symbol(n)
  n > 1 ? :M : n
end
connectivity_symbols(n,m) click to toggle source
# File lib/rgfa/connectivity.rb, line 123
def connectivity_symbols(n,m)
  [connectivity_symbol(n), connectivity_symbol(m)]
end
traverse_component(segment_end, c, visited) click to toggle source
# File lib/rgfa/connectivity.rb, line 111
def traverse_component(segment_end, c, visited)
  links_of(segment_end).each do |l|
    oe = l.other_end(segment_end)
    sn = oe.name
    next if visited.include?(sn)
    visited << sn
    c << sn
    traverse_component([sn, :B], c, visited)
    traverse_component([sn, :E], c, visited)
  end
end