module MPathGraph

Constants

VERSION

Public Class Methods

compute_paths_graph(paths, output_stream, options = {}) click to toggle source

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
find_cycles(worm, edges) click to toggle source
# 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) click to toggle source
# 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) click to toggle source
# 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
gen_mpath_graph_from_paths(paths) click to toggle source
# 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
has_cycles?(worm, edges, options = {}) click to toggle source

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
is_edge?(i, j, edges) click to toggle source

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
random_walk(edges, options = {}) click to toggle source
# 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
share_inner_vertices?(path_a, path_b) click to toggle source
# 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