Module: MPathGraph

Defined in:
lib/mpath_graph.rb,
lib/mpath_graph/version.rb

Defined Under Namespace

Modules: OddHole

Constant Summary collapse

VERSION = 
"0.0.7"

Class Method Summary collapse

Class Method Details

.compute_paths_graph(paths, output_stream, options = {}) ⇒ Object

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.

Parameters:

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

    Set of paths.

  • output_stream —

    Outputstream.

  • options (Hash) (defaults to: {}) —

    Options map.



164
165
166
167
168
169
170
171
172
173
174
175
176
 
# 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) ⇒ Object 



45
46
47
48
49
50
51
52
53
54
55
56
57
 
# 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) ⇒ Object 



138
139
140
141
142
143
144
145
146
147
148
149
150
 
# 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) ⇒ Object 



178
179
180
181
182
183
184
185
186
187
188
189
190
191
 
# 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) ⇒ Object 



201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
 
# 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 = {}) ⇒ Boolean

Given a cycle checks if it has induced cycles.

Parameters:

  • worm (Array<Integer>) —

    Sequence of vertices.

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

    Set of edges.

Returns:

  • (Boolean) 


25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
# 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) ⇒ Boolean

Given a set of edges, checks if there is an edged that relates two vertices of a graph.

Parameters:

  • i (Integer) —

    Vertex i in a graph.

  • j (Integer) —

    Vertex j in a graph.

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

    Set of edges of a graph.

Returns:

  • (Boolean) 


15
16
17
 
# 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 = {}) ⇒ Object 



59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
 
# 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) ⇒ Boolean

Returns:

  • (Boolean)

Raises:

  • (ArgumentError) 


193
194
195
196
197
198
199
 
# 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