Ruby разбирает входной файл и помещает в хеш

Question

Я получил файл для представления списка смежности узлов в графе в виде текстового файла, который мне нужно проанализировать. Первая строка для общего количества узлов. Вторая строка - это node1 вместе со списком узлов, к которым она подключается (ненаправленный граф). Например

7
2 3 -1
1 3 4 5 7 -1
1 2 -1
2 6 -1
2 6 -1
4 5 -1
2 -1

line1: граф имеет всего 7 узлов.
line2: Node1 подключается к Node2, Node3.
линия 3: узел 2 подключается к узлу 1, узлу 3, узлу 4, узлу 5, узлу 7.

-1 - бесполезный вид.

Вот моя текущая реализация ruby. Я пытаюсь найти способ настроить его

def parse_file(filename)
  total_nodes = `wc -l "#{filename}"`.strip.split(' ')[0].to_i
  node_hash = Hash.new

  File.foreach(filename).with_index do |line, line_num|
    # convert each line into an array
    line = line.strip.split(" ")
    # take out weird -1 at the end of txt file in each line
    line = line[0...-1]
    #puts "#{line_num}: #{line}"

    # how come node_hash[Node.new(line_num)] = line does not work?
    node_hash[Node.new(line_num)] = line
  end
end

parse_file('test_data.txt')

Мой класс узла имеет массив adjacency_nodes, который я могу вставить в него node2 и node3. Например: node1.adjancency_nodes << node2 </p>

class Node
  attr_accessor :id, :state, :adjacent_nodes, :graph

  def initialize(id)
    @id = id
    @adjacent_nodes = []
  end

  def to_s
    "node #{@id}"
  end
end

Какой самый простой способ перебрать этот текстовый файл, создать новые узлы и сохранить его в хеше, а также принудительно передать все его смежные узлы?

Answer 1

Здесь все признаки проблемы с домашним заданием пошли наперекосяк, но я постараюсь помочь.

Мой класс узла имеет массив adjacency_nodes, который я могу вставить в него node2 и node3. Например: node1.adjancency_nodes << node2 </p>

Хотите вставить идентификатор узла в массив или ссылку на сам узел?

# how come node_hash[Node.new(line_num)] = line does not work?

Что вы подразумеваете под этим "не работает?" Разве это не добавляет строку в ваш хэш?

Вы создаете хеш, где ключи - это ссылки на узлы, а значения - это смежные узлы. Вы на самом деле не изменяете свойство adjacent_nodes каждого узла. Это то, что вы хотите сделать? Кроме того, если у вас есть две строки, которые ссылаются на один и тот же идентификатор узла, например, 2, вы собираетесь создать экземпляр этого узла дважды, например, Node.new(2) будет вызван дважды. Это то, что вы хотите сделать?

Взглянув на то, что вы написали, я заметил несколько вещей:

• Вы используете String#strip, когда вы действительно хотите String#chomp перевод строки в конец строки.
• Вы игнорируете ценную информацию в верхней части файла, т. Е. Общее количество узлов.
• Хуже того, вы вызываете команду оболочки, чтобы получить эту информацию (просто сделайте это в Ruby!) Вместо этого, и вы делаете это неправильно: вы считаете строку, содержащую количество узлов, как определение узла, поэтому ваша переменная total_nodes установлена ​​на восемь (не на семь).
• Вы игнорируете ценную информацию в конце каждой строки. Да, терминатор -1 довольно странный, но вы можете использовать его, чтобы определить, когда прекратить обработку строки. Я полагаю, ваш профессор планирует отправить неверные данные, например 2 3 4 -1 5, чтобы проверить, не сломался ли ваш код. В этом случае ваш код должен учитывать только смежные узлы 2, 3 и 4.
• Вы не конвертируете строки, содержащие числовые значения, в правильные целые числа во всех случаях.
• Что вы ожидаете от вашего метода parse_file? Вероятно, он не возвращает то, что вы думаете, он возвращает, как написано в настоящее время.

Имея это в виду, давайте внесем некоторые изменения:

• Давайте прочитаем первую строку ввода, чтобы определить общее количество узлов.
• Давайте предварительно распределим наши узлы, чтобы каждый экземпляр создавался только один раз.
• Давайте использовать массив (с индексами, начинающимися с нуля) для хранения ссылок на наши узлы. Мы должны помнить об этом при создании экземпляров узлов и выполнении поиска по массиву (с однозначными идентификаторами узлов).
• Давайте прекратим обработку соседних узлов, когда увидим недопустимый идентификатор узла.
• Давайте использовать String#chomp и String#to_i для всех входов.
• Давайте добавим смежные узлы ...
• Давайте вернем массив узлов в конце метода, чтобы вызывающая сторона получила что-то полезное.

---

def parse_file(filename)
  # open the file in read-only mode
  file = File.new(filename, 'r')
  # read the first line as an integer to determine the number of nodes
  num_nodes = file.readline.chomp.to_i
  # preallocate our nodes so we can store adjacent node references
  nodes = Array.new(num_nodes) { |i| Node.new(i + 1) }

  # read the remaining lines containing node definitions
  file.each_line.with_index do |line, i|
    # parse the adjacent node ids as integers
    line.chomp.split(' ').map(&:to_i).each do |node_id|
      # a sentinel node id of -1 means stop processing
      break if node_id < 0

      # TODO: What's supposed to happen when the node doesn't exist?
      #raise "Unknown node ID: #{node_id}" if node_id == 0 || node_id > num_nodes

      # add the node reference to the list of adjacent nodes
      nodes[i].adjacent_nodes << nodes[node_id - 1]
    end
  end

  nodes
end

Answer 2

Можно воспользоваться тем, что ruby ​​поддерживает технически бесконечное перекрестное вложение объектов:

class Node
  attr_accessor :id, :adjacents
  def initialize(id)
    @id = id
    @adjacents = []
  end
  def to_s
    "<#Node #{@adjacents.map(&:id).inspect}>"
  end
end

class Graph
  attr_accessor :nodes
  def initialize(count)
    @nodes = (1..count).map(&Node.method(:new))
  end
  def to_s
    "<#Graph nodes: {#{@nodes.map(&:to_s)}}>"
  end
end

input = "7\n2 3 -1\n1 3 4 5 7 -1\n1 2 -1\n2 6 -1\n2 6 -1\n4 5 -1\n2 -1"

graph, *nodes = input.split($/)
count = graph.to_i

result =
  nodes.
    each.
    with_index.
    with_object(Graph.new(count)) do |(line, idx), graph|
      graph.nodes[idx].adjacents |=
        line.split.map(&:to_i).
          select { |e| e >= 1 && e <= count }.
          map { |e| graph.nodes[e - 1] }
    end

---

Теперь у вас есть бесконечно-вложенный граф (вы можете вызывать adjacents на любом узле все глубже и глубже, чтобы получить правильный результат.)

Структура графа верхнего уровня может быть достигнута с помощью:

puts result.to_s
#⇒ <#Graph nodes: {["<#Node [2, 3]>",
#                   "<#Node [1, 3, 4, 5, 7]>",
#                   "<#Node [1, 2]>",
#                   "<#Node [2, 6]>",
#                   "<#Node [2, 6]>",
#                   "<#Node [4, 5]>",
#                   "<#Node [2]>"]}>

Answer 3

Это использование системного вызова странно; вам действительно не нужно это, чтобы получить первую строку в файле.

Первая строка представляет количество узлов.

Каждая строка после представляет соседние узлы для данного узла. строка n представляет узлы для node (n-1).

Так что вы можете просто перейти к строке:

def parse_file(path)

  # start
  f = File.open(path, 'r')

  # get node count. Convert to integer
  num_nodes = f.readline.to_i

  # create your nodes
  nodes = {}
  1.upto(num_nodes) do |id|
    node = Node.new(id)
    nodes[id] = node
  end

  # join them and stuff
  1.upto(num_nodes) do |id|
    node = nodes[id]

    # for each line, read it, strip it, then split it
    tokens = f.readline.strip.split(" ")
    tokens.each do |other_id|
      other_id = other_id.to_i
      break if other_id == -1

      # grab the node object, using the ID as key
      other_node = nodes[other_id]
      node.adjacent_nodes << other_node
    end
  end

  # done
  f.close
end