# 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

• Find the connected components of the graph.

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

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

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

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

• Split connected components of the graph into single-component RGFAs.

## 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:

• segment

segment name or instance

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```

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:

• segment

a segment name or instance

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

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```