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