Module: MPathGraph
- Defined in:
- lib/mpath_graph.rb,
lib/mpath_graph/version.rb
Defined Under Namespace
Modules: OddHole
Constant Summary collapse
- VERSION =
"0.0.7"
Class Method Summary collapse
-
.compute_paths_graph(paths, output_stream, options = {}) ⇒ Object
Given a set of paths it computes a graphs of paths.
- .find_cycles(worm, edges) ⇒ Object
- .find_neighbors(vertex, edges) ⇒ Object
- .from_csv(file) ⇒ Object
- .gen_mpath_graph_from_paths(paths) ⇒ Object
-
.has_cycles?(worm, edges, options = {}) ⇒ Boolean
Given a cycle checks if it has induced cycles.
-
.is_edge?(i, j, edges) ⇒ Boolean
Given a set of edges, checks if there is an edged that relates two vertices of a graph.
- .random_walk(edges, options = {}) ⇒ Object
- .share_inner_vertices?(path_a, path_b) ⇒ Boolean
Class Method Details
.compute_paths_graph(paths, output_stream, options = {}) ⇒ Object
Given a set of paths it computes a graphs of paths. For each path in set, it compares with all other paths in set and if both share inner then there is an edge that links these vertices.
This method is recommended for big paths arrays because it flush to outputstream instead of keep them in memory which is very space-expensive.
164 165 166 167 168 169 170 171 172 173 174 175 176 |
# File 'lib/mpath_graph.rb', line 164 def self.compute_paths_graph(paths, output_stream, = {}) len = paths.size - 1 (0..len).each do |i| (i+1..len).each do |j| unless (paths[i][1...-1] & paths[j]).empty? output_stream << [i,j] next end end [:progress_bar].increment unless [:progress_bar].nil? end end |
.find_cycles(worm, edges) ⇒ Object
45 46 47 48 49 50 51 52 53 54 55 56 57 |
# File 'lib/mpath_graph.rb', line 45 def self.find_cycles(worm, edges) if is_edge? worm[0], worm[-1], edges # Check edges (0..worm.length-2).each do |i| (i+2..worm.length-1).each do |j| unless i==0 && j==worm.length-1 # Avoid check endpoints return [worm[i],worm[j]] if is_edge? worm[i], worm[j], edges end end end end nil end |
.find_neighbors(vertex, edges) ⇒ Object
138 139 140 141 142 143 144 145 146 147 148 149 150 |
# File 'lib/mpath_graph.rb', line 138 def self.find_neighbors(vertex, edges) neighbors = [] edges.each do |e| if vertex == e[0] neighbors << e[1] elsif vertex == e[1] neighbors << e[0] end end neighbors end |
.from_csv(file) ⇒ Object
178 179 180 181 182 183 184 185 186 187 188 189 190 191 |
# File 'lib/mpath_graph.rb', line 178 def self.from_csv(file) = ProgressBar.create( title: "Reading paths graph", starting_at: 1, total: nil) paths = [] CSV.foreach(file) do |row| paths << JSON.parse(row[0]) .increment end paths end |
.gen_mpath_graph_from_paths(paths) ⇒ Object
201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 |
# File 'lib/mpath_graph.rb', line 201 def self.gen_mpath_graph_from_paths(paths) mp_graph_edges = [] = ProgressBar.create( title: "Computing mPath graph", output: STDERR, format: "%t [%B] [%c/%C - %P%%]", total: paths.size-1) (0..paths.size-2).each do |i| ((i+1)...paths.size).each do |j| share = MPathGraph::share_inner_vertices?(paths[i],paths[j]) mp_graph_edges << [i,j] if share end .increment end .finish mp_graph_edges end |
.has_cycles?(worm, edges, options = {}) ⇒ Boolean
Given a cycle checks if it has induced cycles.
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
# File 'lib/mpath_graph.rb', line 25 def self.has_cycles?(worm, edges, = {}) if is_edge? worm[0], worm[-1], edges # Check edges (0..worm.length-2).each do |i| (i+2..worm.length-1).each do |j| unless i==0 && j==worm.length-1 # Avoid check endpoints if is_edge? worm[i], worm[j], edges if [:verbose] # Verbose cycle puts "Cycle\t#{worm[i]},#{worm[j]}" end return true end end end end end false end |
.is_edge?(i, j, edges) ⇒ Boolean
Given a set of edges, checks if there is an edged that relates two vertices of a graph.
15 16 17 |
# File 'lib/mpath_graph.rb', line 15 def self.is_edge?(i, j, edges) edges.include?([i,j]) || edges.include?([j,i]) end |
.random_walk(edges, options = {}) ⇒ Object
59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 |
# File 'lib/mpath_graph.rb', line 59 def self.random_walk(edges, = {}) worm = [] neighbors = nil steps_walked = 0 [:initial_vertex] ||= 0 [:worm_size] ||= 5 [:walk_limit] ||= -1 [:pause] ||= false [:induced_cycles_limit] ||= -1 [:print_non_cycles] ||= false # Initialize worm with initial vertex worm << [:initial_vertex] # Initialize pseudo-random number generator prng = Random.new # Flush csv row headers to STDIN puts ["k-path","Induced cycle","Steps walked"].to_csv # Fill worm while worm.size < [:worm_size] # Find neighbors of last vertex neighbors = find_neighbors(worm.last, edges) unless neighbors rnd_idx = prng.rand(neighbors.size) # Compute random index # Avoid cycles in worm if worm.include?(neighbors[rnd_idx]) # Delete non-valid neighbors for current last vertex neighbors.delete(neighbors[rnd_idx]) # Useless last vertex in worm, drop it! if neighbors.empty? worm.pop # Drop last vertex neighbors = nil # Clean neighbors end else worm << neighbors[rnd_idx] # Append vertex neighbors = nil # Clean neighbors if worm.size == [:worm_size] # When worm is full steps_walked += 1 # Increment worm steps walked # Output well-formed worm # puts "Checking\t#{worm.inspect}" csv_row = [worm] # if has_cycles?(worm, edges, verbose: options[:verbose]) if (cycle = find_cycles(worm, edges)) # Flush csv row data to STDIN puts [worm, cycle, steps_walked].to_csv # if options[:verbose] # Verbose worm with cycle # puts "Worm\t#{worm.inspect}" # puts "Steps walked\t#{steps_walked}" # end # Pause when verbose # if options[:pause] # STDERR.puts "Press a key to continue..." # STDIN.getc # end # Check induced cycles counter limit return if [:induced_cycles_limit]==0 [:induced_cycles_limit]-=1 else # Flush csv row data to STDIN puts [worm, nil, steps_walked].to_csv if [:print_non_cycles] end worm.shift # Drop first vertex in worm (as queue) break if steps_walked > [:walk_limit] && [:walk_limit] > 0 # Stop walking end end end end |
.share_inner_vertices?(path_a, path_b) ⇒ Boolean
193 194 195 196 197 198 199 |
# File 'lib/mpath_graph.rb', line 193 def self.share_inner_vertices?(path_a, path_b) raise ArgumentError, "Path must have same lenght" if path_a.size != path_b.size path_a[1..-2].each { |a| path_b.each { |b| return true if a == b } } path_b[1..-2].each { |b| return true if b == path_a[0] || b == path_a[-1] } false end |