module MPathGraph::OddHole
Public Class Methods
equivalents(hole)
click to toggle source
# File lib/mpath_graph.rb, line 223 def self.equivalents(hole) perms = [hole.reverse] tmp = Array.new hole (hole.size-1).times do tmp << tmp.shift perms << Array.new(tmp) perms << Array.new(tmp.reverse) end perms end
is_an_odd_hole?(path, edges, size = 5)
click to toggle source
Given a path in a graph G, check if it is an odd-hole with an specific size.
@param path [Array<Integer>] Sequence of vertices to check. @param edges [Array<Array<Integer>>] Set of edges of graph G. @param size [Array<Array<Integer>>] Odd-hole size to search.
# File lib/mpath_graph.rb, line 354 def self.is_an_odd_hole?(path, edges, size = 5) raise ArgumentError, "Hole size must be at least 5" if size<5 raise ArgumentError, "Hole size must be odd" if size % 2 == 0 raise ArgumentError, "Path must have odd-hole size" if path.size != size cycle_edge = order_uedge(path[0],path[-1]) return false unless edges.include?(cycle_edge) (0..size-3).each do |i| # First vertex (2..size-2).each do |j| # Offset from first vertex next if i+j > size-1 uedge = order_uedge(path[i],path[i+j]) return false if edges.include?(uedge) end end true end
order_uedge(v,u)
click to toggle source
Order entries of a tuple.
# File lib/mpath_graph.rb, line 374 def self.order_uedge(v,u) v < u ? [v,u] : [u,v] end
rw_search(edges, options = {})
click to toggle source
# File lib/mpath_graph.rb, line 236 def self.rw_search(edges, options = {}) options[:holes_limit] ||= 0 holes_found = [] options[:worm_size] ||= 5 return nil if edges.size < options[:worm_size] prng = Random.new rnd_idx = prng.rand(edges.size) options[:initial_vertex] ||= edges[rnd_idx][rnd_idx%2] worm = [options[:initial_vertex]] pbar = ProgressBar.create( title: "Steps walked", starting_at: 0, output: STDERR, format: "%t |%B| [%c]", total: nil) while worm.size < options[:worm_size] return nil if worm.empty? neighbors = MPathGraph::find_neighbors(worm.last, edges) neighbors = neighbors - worm if neighbors.empty? worm.pop next else rnd_idx = prng.rand(neighbors.size) worm << neighbors[rnd_idx] neighbors = nil if worm.size == options[:worm_size] pbar.increment if is_an_odd_hole?(worm, edges, options[:worm_size]) # Check if current hole is also found repeated = false holes_found.each do |h| if worm == h repeated = true break end equivalents(h).each do |e| if worm == e repeated = true break end end break if repeated end # Add to found list if not found yet unless repeated # Keep odd-hole found holes_found << worm pbar.log "#{worm.inspect}\n" # Check holes found limit if options[:holes_limit] > 0 && holes_found.size == options[:holes_limit] return holes_found end end # Leave only first element in worm worm = [worm.last] next else worm.shift next end end end end end
rw_search_first(edges, options = {})
click to toggle source
# File lib/mpath_graph.rb, line 313 def self.rw_search_first(edges, options = {}) options[:worm_size] ||= 5 return nil if edges.size < options[:worm_size] prng = Random.new rnd_idx = prng.rand(edges.size) options[:initial_vertex] ||= edges[rnd_idx][rnd_idx%2] worm = [options[:initial_vertex]] while worm.size < options[:worm_size] return nil if worm.empty? neighbors = MPathGraph::find_neighbors(worm.last, edges) neighbors = neighbors - worm if neighbors.empty? worm.pop next else rnd_idx = prng.rand(neighbors.size) worm << neighbors[rnd_idx] neighbors = nil if worm.size == options[:worm_size] if is_an_odd_hole?(worm, edges, options[:worm_size]) return worm else worm.shift next end end end end end