Generating path over the graph Ruby

Question

I have an undirected graph with 12 nodes and I generate an array like this:

arr = [[3, 12], [8, 12], [0, 3], [0, 5], [0, 10], [7, 9], [5, 5], [4, 9], [5, 12], [0, 1]] 

which represents the graph edges.

I would like to find the longest possible path through the graph, such as each edge is used at most once. For given example it would be something like:

arr = [[1, 0], [0, 5], [5, 5], [5, 12], [12, 3], [3, 0], [0, 10]]

I have seen on a number of sources solutions to this problem by searching the Euler path but written in other programming languages​​. How would I proceed with it in Ruby?

Answer 1

An euler path visits every edge exactly once, so I guess you do not need that. What I can offer is something like this:

def find_path(arr, first_chain = nil, path = [], available = arr.dup)
  edge_idx = available.index do |first, _| 
    first_chain.nil? || first == first_chain
  end
  unless edge_idx
    return path
  end
  edge = available.delete_at(edge_idx)
  path << edge
  find_path(arr, edge.last, path, available)
end

arr = [[0, 5], [3, 0], [5, 5], [1, 0], [0, 10], [5, 12], [12, 3]]

find_path arr
# => [[0, 5], [5, 5], [5, 12], [12, 3], [3, 0], [0, 10]] 

find_path arr, 1
# => [[1, 0], [0, 5], [5, 5], [5, 12], [12, 3], [3, 0], [0, 10]] 

This algorithm finds some path starting with the first element, or any other integer given. It is not guaranteed that it uses all elements, or that it is even the longest possible, but it is a path...

---

For a non-directional graph, you need to account that the edge might be reversed:

def find_path(arr, first_chain = nil, path = [], available = arr.dup)
  edge_idx = available.index do |edge| 
    first_chain.nil? || edge.include?(first_chain)
  end
  unless edge_idx
    return path
  end
  edge = available.delete_at(edge_idx)
  edge = edge.reverse if first_chain && edge.first != first_chain
  path << edge
  find_path(arr, edge.last, path, available)
end

find_path arr
# => [[0, 5], [5, 5], [5, 12], [12, 3], [3, 0], [0, 1]] 

find_path arr, 1
# => [[1, 0], [0, 5], [5, 5], [5, 12], [12, 3], [3, 0], [0, 10]] 

---

To find the longest path, you need to build all possible paths, and select the longest:

def find_longest_path(arr, first_chain = nil, available = arr.dup)
  paths = available.each_index.select do |edge_idx| 
    first_chain.nil? || available[edge_idx].include?(first_chain)
  end.map do |edge_idx|
    edge = available[edge_idx]
    edge = edge.reverse if first_chain && edge.first != first_chain
    [edge, *find_longest_path(arr, edge.last, 
                         available[0...edge_idx] + available[edge_idx+1..-1])]
  end
  # a hack to find longest in all reverse paths
  if first_chain.nil? && arr == available
    paths << find_longest_path(arr, nil, arr.map(&:reverse))
  end
  paths.max_by { |path| path.length }
end

arr = [[3, 12], [8, 12], [0, 3], [0, 5], [0, 10], [7, 9], [5, 5], [4, 9], [5, 12], [0, 1]]

find_longest_path arr
# => [[10, 0], [0, 3], [3, 12], [12, 5], [5, 5], [5, 0], [0, 1]] 

find_longest_path arr, 1
# => [[1, 0], [0, 3], [3, 12], [12, 5], [5, 5], [5, 0], [0, 10]]

What this code does?
Instead of taking the first edge that can be used in our path, this algorithm takes all the edges that can be used in our path.

For each such edge, it builds a new path which:

1. starts with the selected edge
2. removes the edge from the available array
3. continues with the longest path available starting from the edge's out vertex (recursion)

This builds a list of all possible paths. From this the method returns the longest (max by length).

The three lines I marked as # hack are because when the first_chain is nil the algorithm finds the longest path starting with any non reversed edge. To support reversed edges I run it twice - the second time with all edges reversed.

This is not an implementation of a known algorithm but a simple brute-force implementation, which might not very well be most efficient, simple or beautiful, but it should put you in the right direction. You might find more information about working with Graphs in ruby here

Answer 2

Something like this might work for you although there might be better methods

def generate_array
  a = []
  b2 = nil
  10.times do 
    b1,b2 = [b2 || rand(12),rand(12)]
    a << [b1,b2]
  end
  a
end
generate_array
#=> [[0, 4], [4, 4], [4, 11], [11, 4], [4, 8], [8, 11], [11, 4], [4, 2], [2, 6], [6, 0]]

Also just a note based on your given output rand(12) will never return 12 because the upper limit is set using a 0 index so the largest number to be returned is 11