module MPathGraph
Constants
- VERSION
Public Class Methods
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.
@param paths [Array<Array<Integer>>] Set of paths. @param output_stream Outputstream. @param options [Hash] Options map.
# File lib/mpath_graph.rb, line 164 def self.compute_paths_graph(paths, output_stream, options = {}) 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 options[:progress_bar].increment unless options[:progress_bar].nil? end end
# 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
# 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
# File lib/mpath_graph.rb, line 178 def self.from_csv(file) pbar = ProgressBar.create( title: "Reading paths graph", starting_at: 1, total: nil) paths = [] CSV.foreach(file) do |row| paths << JSON.parse(row[0]) pbar.increment end paths end
# File lib/mpath_graph.rb, line 201 def self.gen_mpath_graph_from_paths(paths) mp_graph_edges = [] pbar = 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 pbar.increment end pbar.finish mp_graph_edges end
Given a cycle checks if it has induced cycles.
@param worm [Array<Integer>] Sequence of vertices. @param edges [Array<Array<Integer>>] Set of edges.
@return [Boolean]
# File lib/mpath_graph.rb, line 25 def self.has_cycles?(worm, edges, options = {}) 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 options[:verbose] # Verbose cycle puts "Cycle\t#{worm[i]},#{worm[j]}" end return true end end end end end false end
Given a set of edges, checks if there is an edged that relates two vertices of a graph.
@param i [Integer] Vertex i in a graph. @param j [Integer] Vertex j in a graph. @param edges [Array<Array<Integer>>] Set of edges of a graph.
@return [Boolean]
# File lib/mpath_graph.rb, line 15 def self.is_edge?(i, j, edges) edges.include?([i,j]) || edges.include?([j,i]) end
# File lib/mpath_graph.rb, line 59 def self.random_walk(edges, options = {}) worm = [] neighbors = nil steps_walked = 0 options[:initial_vertex] ||= 0 options[:worm_size] ||= 5 options[:walk_limit] ||= -1 options[:pause] ||= false options[:induced_cycles_limit] ||= -1 options[:print_non_cycles] ||= false # Initialize worm with initial vertex worm << options[: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 < options[: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 == options[: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 options[:induced_cycles_limit]==0 options[:induced_cycles_limit]-=1 else # Flush csv row data to STDIN puts [worm, nil, steps_walked].to_csv if options[:print_non_cycles] end worm.shift # Drop first vertex in worm (as queue) break if steps_walked > options[:walk_limit] && options[:walk_limit] > 0 # Stop walking end end end end