Module: MPathGraph::OddHole

Defined in:

lib/mpath_graph.rb

Class Method Summary

• .equivalents(hole) ⇒ Object
• .is_an_odd_hole?(path, edges, size = 5) ⇒ Boolean

  Given a path in a graph G, check if it is an odd-hole with an specific size.

• .order_uedge(v, u) ⇒ Object

  Order entries of a tuple.

• .rw_search(edges, options = {}) ⇒ Object
• .rw_search_first(edges, options = {}) ⇒ Object

Class Method Details

.equivalents(hole) ⇒ Object

# File 'lib/mpath_graph.rb', line 194

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) ⇒ Boolean

Given a path in a graph G, check if it is an odd-hole with an specific size.

Parameters:

• path (Array<Integer>) —

  Sequence of vertices to check.

• edges (Array<Array<Integer>>) —

  Set of edges of graph G.

• size (Array<Array<Integer>>) (defaults to: 5) —

  Odd-hole size to search.

Returns:

• (Boolean)

Raises:

• (ArgumentError)

# File 'lib/mpath_graph.rb', line 312

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) ⇒ Object

Order entries of a tuple.

# File 'lib/mpath_graph.rb', line 332

def self.order_uedge(v,u)
  v < u ? [v,u] : [u,v]
end

.rw_search(edges, options = {}) ⇒ Object

# File 'lib/mpath_graph.rb', line 207

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

  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])
          # 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
            holes_found << worm
            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 = {}) ⇒ Object

# File 'lib/mpath_graph.rb', line 271

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