Class: Yargraph::UndirectedGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/yargraph.rb

Defined Under Namespace

Classes: EdgeSearchResult, EdgeSet, Path

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ UndirectedGraph

Returns a new instance of UndirectedGraph.



105
106
107
108
 
# File 'lib/yargraph.rb', line 105

def initialize
  @vertices = Set.new
  @edges = EdgeSet.new
end

Instance Attribute Details

#edges ⇒ Object

edges is an EdgeSet



12
13
14
 
# File 'lib/yargraph.rb', line 12

def edges
  @edges
end

#vertices ⇒ Object

vertices is a Set



9
10
11
 
# File 'lib/yargraph.rb', line 9

def vertices
  @vertices
end

Instance Method Details

#add_edge(vertex1, vertex2) ⇒ Object

Add an edge between two vertices, adding the vertices in the edge to the graph if they aren’t already contained within it.



112
113
114
115
116
117
 
# File 'lib/yargraph.rb', line 112

def add_edge(vertex1, vertex2)
  @vertices << vertex1
  @vertices << vertex2
  @edges.add_edge vertex1, vertex2
  return
end

#add_vertex(vertex) ⇒ Object

Add a vertex to the graph



120
121
122
 
# File 'lib/yargraph.rb', line 120

def add_vertex(vertex)
  @vertices << vertex
end

#copy ⇒ Object 



146
147
148
149
150
151
152
153
154
155
 
# File 'lib/yargraph.rb', line 146

def copy
  another = UndirectedGraph.new
  @vertices.each do |v|
    another.add_vertex v
  end
  each_edge do |v1, v2|
    another.add_edge v1, v2
  end
  return another
end

#delete_edge(v1, v2) ⇒ Object 



130
131
132
133
 
# File 'lib/yargraph.rb', line 130

def delete_edge(v1,v2)
  @edges[v1].delete v2
  @edges[v2].delete v1
end

#each_edge ⇒ Object

Yield a pair of vertices for each edge



136
137
138
139
140
 
# File 'lib/yargraph.rb', line 136

def each_edge
  @edges.each do |v1, v2|
    yield v1, v2
  end
end

#edge?(v1, v2) ⇒ Boolean

Returns:

  • (Boolean) 


142
143
144
 
# File 'lib/yargraph.rb', line 142

def edge?(v1,v2)
  @edges.edge?(v1,v2)
end

#edges_in_all_hamiltonian_cycles(operational_limit = nil) ⇒ Object

Return an array of edges (edges being an array of 2 vertices) that correspond to edges that are found in all Hamiltonian paths. This method might be quite slow because it requires finding all Hamiltonian paths, which implies solving the (NP-complete) Hamiltonian path problem.

There is probably no polynomial time way to implement this method anyway, see cstheory.stackexchange.com/questions/20413/is-there-an-efficient-algorithm-for-finding-edges-that-are-part-of-all-hamiltoni

The operational limit is used to make sure this algorithm doesn’t get out of hand - only this many ‘operations’ are used when traversing the graph, as in #hamiltonian_cycles_brute_force



340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
 
# File 'lib/yargraph.rb', line 340

def edges_in_all_hamiltonian_cycles(operational_limit=nil)
  hedges = nil
  hamiltonian_cycles do |path|
    # Convert the path to a hash v1->v2, v2->v3. Can't have collisions because the path is Hamiltonian
    edge_hash = {}
    path.each_with_index do |v, i|
      unless i == path.length-1
        edge_hash[v] = path[i+1]
      end
    end
    edge_hash[path[path.length-1]] = path[0] #Add the final wrap around edge

    if hedges.nil?
      # First Hpath found
      hedges = edge_hash
    else
      # Use a process of elimination, removing all edges that
      # aren't in hedges or this new Hpath
      hedges.select! do |v1, v2|
        edge_hash[v1] == v2 or edge_hash[v2] = v1
      end
      # If no edges fit the bill, then we are done
      return [] if hedges.empty?
    end
  end
  return [] if hedges.nil? #no Hpaths found in the graph
  return hedges.to_a
end

#hamiltonian_cycles_brute_force(operational_limit = nil) ⇒ Object

Run depth first search, returning an array of Hamiltonian paths. Or, if a block is given, yield each Hamiltonian path that comes along (in no defined order), and don’t return the array (to potentially save RAM).

The operational limit is used to make sure this algorithm doesn’t get out of hand - only this many ‘operations’ are used when traversing the graph, as in #hamiltonian_paths_brute_force. When nil, there is no operational limit



166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
 
# File 'lib/yargraph.rb', line 166

def hamiltonian_cycles_brute_force(operational_limit=nil)
  stack = DS::Stack.new
  return [] if @vertices.empty?

  origin_vertex = @vertices.to_a[0]
  hamiltonians = []
  num_operations = 0

  path = Path.new
  path << origin_vertex
  stack.push path
  while path = stack.pop
    last_vertex = path[path.length-1]
    if last_vertex == origin_vertex and path.length > 1
      # Cycle of some sort detected. Is it Hamiltonian?
      if path.length == vertices.length + 1
        # Found a Hamiltonian path. Yield or save it for later
        hpath = path.copy[0...(path.length-1)]
        if block_given?
          yield hpath
        else
          hamiltonians << hpath
        end
      else
        # non-Hamiltonian path found. Ignore
      end

    elsif path.find_index(last_vertex) != path.length - 1
      # Found a loop, go no further

    else
      # No loop, just another regular thing.
      neighbours(last_vertex).each do |neighbour|
        unless operational_limit.nil?
          num_operations += 1
          if num_operations > operational_limit
            raise OperationalLimitReachedException
          end
        end
        new_path = Path.new(path.copy+[neighbour])
        stack.push new_path
      end
    end
  end

  return hamiltonians
end

#hamiltonian_cycles_dynamic_programming(operational_limit = nil) ⇒ Object Also known as: hamiltonian_cycles

Use dynamic programming to find all the Hamiltonian cycles in this graph



215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
 
# File 'lib/yargraph.rb', line 215

def hamiltonian_cycles_dynamic_programming(operational_limit=nil)
  stack = DS::Stack.new
  return [] if @vertices.empty?

  origin_vertex = @vertices.to_a[0]
  hamiltonians = []
  num_operations = 0

  # This hash keeps track of subproblems that have already been
  # solved. ie is there a path through vertices that ends in the
  # endpoint
  # Hash of [vertex_set,endpoint] => Array of Path objects.
  # If no path is found, then the key is false
  # The endpoint is not stored in the vertex set to make the programming
  # easier.
  dp_cache = {}

  # First problem is the whole problem. We get the Hamiltonian paths,
  # and then after reject those paths that are not cycles.
  initial_vertex_set = Set.new(@vertices.reject{|v| v==origin_vertex})
  initial_problem = [initial_vertex_set, origin_vertex]
  stack.push initial_problem

  while next_problem = stack.pop
    vertices = next_problem[0]
    destination = next_problem[1]

    if dp_cache[next_problem]
      # No need to do anything - problem already solved

    elsif vertices.empty?
      # The bottom of the problem. Only return a path
      # if there is an edge between the destination and the origin
      # node
      if edge?(destination, origin_vertex)
        path = Path.new [destination]
        dp_cache[next_problem] = [path]
      else
        # Reached dead end
        dp_cache[next_problem] = false
      end

    else
      # This is an unsolved problem and there are at least 2 vertices in the vertex set.
      # Work out which vertices in the set are neighbours
      neighs = Set.new neighbours(destination)
      possibilities = neighs.intersection(vertices)
      if possibilities.length > 0
        # There is still the possibility to go further into this unsolved problem
        subproblems_unsolved = []
        subproblems = []

        possibilities.each do |new_destination|
          new_vertex_set = Set.new(vertices.to_a.reject{|v| v==new_destination})
          subproblem = [new_vertex_set, new_destination]

          subproblems.push subproblem
          if !dp_cache.key?(subproblem)
            subproblems_unsolved.push subproblem
          end
        end

        # if solved all the subproblems, then we can make a decision about this problem
        if subproblems_unsolved.empty?
          answers = []
          subproblems.each do |problem|
            paths = dp_cache[problem]
            if paths == false
              # Nothing to see here
            else
              # Add the found sub-paths to the set of answers
              paths.each do |path|
                answers.push Path.new(path+[destination])
              end
            end
          end

          if answers.empty?
            # No paths have been found here
            dp_cache[next_problem] = false
          else
            dp_cache[next_problem] = answers
          end
        else
          # More problems to be solved before a decision can be made
          stack.push next_problem #We have only delayed solving this problem, need to keep going in the future
          subproblems_unsolved.each do |prob|
            unless operational_limit.nil?
              num_operations += 1
              raise OperationalLimitReachedException if num_operations > operational_limit
            end
            stack.push prob
          end
        end

      else
        # No neighbours in the set, so reached a dead end, can go no further
        dp_cache[next_problem] = false
      end
    end
  end

  if block_given?
    dp_cache[initial_problem].each do |hpath|
      yield hpath
    end
    return
  else
    return dp_cache[initial_problem]
  end
end

#neighbours(vertex) ⇒ Object

Return an Enumerable collection of vertices that are directly connected to the given vertex



126
127
128
 
# File 'lib/yargraph.rb', line 126

def neighbours(vertex)
  @edges.neighbours(vertex)
end

#some_edges_in_all_hamiltonian_cycles ⇒ Object

If #edges_in_all_hamiltonian_cycles is too slow, the method here is faster, but is not guaranteed to find every edge that is part of Hamiltonian cycles. This method proceeds under the assumption that the graph has at least 1 Hamiltonian cycle, but may stumble across evidence to the contrary.

Returns an instance of EdgeSearchResult where #edges_in_all are those edges that are in all hamiltonian cycles, and #edges_in_none are those edges that are not in any hamiltonian cycles. While



378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
 
# File 'lib/yargraph.rb', line 378

def some_edges_in_all_hamiltonian_cycles
  stack = DS::Stack.new
  result = EdgeSearchResult.new

  # As we are deleting edges, make a deep copy to start with
  g = copy

  # Fill up the stack, in reverse to ease testing
  g.vertices.to_a.reverse.each do |v|
    stack.push v
  end

  while v = stack.pop
    all_neighbours = g.neighbours(v)
    ham_neighbours = result.hamiltonian_neighbours(v)
#        p v
#        p all_neighbours
#        p ham_neighbours

    # If a vertex contains 1 or 0 total neighbours, then the graph cannot contain
    # any hamcycles (in contrast, degree 1 doesn't preclude hampaths).
    if all_neighbours.length < 2
      result.contains_hamcycle = false

    elsif all_neighbours.length == 2
      # If a vertex has degree 2 then both edges must be a part of the hamcycle
      all_neighbours.each do |n|
        unless result.edges_in_all.edge?(v,n)
          result.edges_in_all.add_edge(v,n)
          stack.push n #now need to re-evalute the neighbour, as its neighbourhood is changed
        end

        # if an edge be and must not be in all hamcycles, then the graph is not Hamiltonian.
        # Are there any concrete examples of this? Possibly.
        if result.edges_in_all[v].include?(n) and result.edges_in_none[v].include?(n)
          result.contains_hamcycle = false
        end
      end

    elsif ham_neighbours.length >= 2
      # There cannot be any further hamcycle edges from this vertex, so the rest of the edges
      # cannot be a part of _any_ hamcycle
      all_neighbours.each do |n|
        next if ham_neighbours.include?(n)

        result.edges_in_none.add_edge(v,n)
        g.delete_edge(v,n)
        stack.push n #reconsider the neighbour
      end

    else
      # Anything else that can be done cheaply?
      # Maybe edges that create non-Hamiltonian cycles when only considering edges
      # that are in all Hamiltonian cycles -> these cannot be in any hamcycle

    end
    #p stack
  end
  #p result

  return result
end