convert adjacency matrix to adjacency list to represent a graph

user_2095793 0
Viewed 353

I am trying to write a code in Ruby to convert a given graph's adjacency matrix to adjacency list. When I verified my solution for the given input mentioned here my output was slightly different. I need some direction in understanding where exactly is the issue. Below is my code:

def convert_adj_matrix_to_list(arr)
  
  list = {}

  start = 0
  last = 0
  
  arr.each_index do |row|
    # row = [0, 0, 1]
    puts "row = #{arr[row]}"
      
    for col in 0..arr[row].size-1
      puts "row = #{row}, col = #{col}"
      puts "arr[#{row}][#{col}] = #{arr[row][col]}"
      list[row] = col if arr[row][col] == 1
    end
    puts
  end

  list
  
end
arr = [ [0, 0, 1], [0, 0, 1], [1, 1, 0] ]

puts convert_adj_matrix_to_list(arr)

Output:

row = [0, 0, 1]
row = 0, col = 0
arr[0][0] = 0
row = 0, col = 1
arr[0][1] = 0
row = 0, col = 2
arr[0][2] = 1

row = [0, 0, 1]
row = 1, col = 0
arr[1][0] = 0
row = 1, col = 1
arr[1][1] = 0
row = 1, col = 2
arr[1][2] = 1

row = [1, 1, 0]
row = 2, col = 0
arr[2][0] = 1
row = 2, col = 1
arr[2][1] = 1
row = 2, col = 2
arr[2][2] = 0

{0=>2, 1=>2, 2=>1}
ruby
1 Answers

Printing inside a function like this is a side effect and should only be done for debugging. Better to print in the caller.

Logically, your code is only keeping track of the last link seen in the matrix and returns a hash that maps ints to ints rather than a hash that maps ints to int arrays.

You can get the hash by mapping each row, then filtering the row's indexes based on whether the cell has the value 1. Once you've built a 2d array of pairs with the first item in a pair being the source node integer and the second item in a pair being the array of its edges to other nodes, call .to_h on it to produce a hash.

def adj_matrix_to_list(matrix)
  matrix.each_with_index.map do |row, i|
    [i, row.each_index.select {|j| row[j] == 1}]
  end.to_h
end

matrix = [[0, 0, 1], 
          [0, 0, 1], 
          [1, 1, 0]]
p adj_matrix_to_list(matrix) # {0=>[2], 1=>[2], 2=>[0, 1]}

Having said that, using a hash with keys 0, 1, 2 ... n is an antipattern, since arrays are a faster and more natural way to represent a sequentially-indexed list of things. I'd do:

def adj_matrix_to_list(matrix)
  matrix.map do |row|
    row.each_index.select {|i| row[i] == 1}
  end
end

matrix = [[0, 0, 1], 
          [0, 0, 1], 
          [1, 1, 0]]
p adj_matrix_to_list(matrix) # [[2], [2], [0, 1]]

and usage is the same as the hash version.

user_62433520
Related