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

第1行:该图总共有7个节点。< br >线路2:节点1连接到节点2、节点3。< br >线路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')

我的节点类有一个邻接节点数组，我可以将节点2和节点3推入其中。例如：node1.adjancy_nodes

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

这具有家庭作业问题出错的所有特征，但我会尽力提供帮助。

我的节点类有一个邻接节点数组，我可以将节点2和节点3推入其中。例如：node1.adjancy_nodes

要将节点ID推送到数组上，还是将节点引用本身推送到数组中？

#为什么node_hash[Node.new（line_num）]=line不工作？

你说的“不起作用”是什么意思？它不会将该行添加到您的哈希值中吗？

您正在构建一个哈希，其中键是节点引用，值是相邻节点。您实际上并没有html" target="_blank">修改每个节点的adjacent_nodes属性。这就是你想做的吗？此外，如果你有两行引用相同的节点ID，例如2，你将实例化该节点两次，例如Node.new（2）将被调用两次。这就是你想做的吗？

看看你写的东西，我注意到一些事情:

• 当你真的只想把换行符从字符串的末尾移开时，你正在使用String#strip。
• 您忽略了文件顶部的有价值信息，即节点总数。
• 更糟糕的是，你调用了一个shell命令来获取该信息（只需在Ruby中执行此操作！），并且你做错了：你把包含节点数的行作为节点定义来计算，所以你total_nodes变量被设置为八（而不是七）。
• 您忽略了每行末尾的有价值信息。是的，-1 终止符有点奇怪，但您可以使用它来确定何时停止处理该行。我认为你的教授计划发送一些糟糕的输入，如2 3 4 -1 5，看看你的代码是否中断。在这种情况下，您的代码应仅考虑相邻节点 2、3 和 4。
• 您不会在所有情况下都将包含数值的字符串转换为正确的整数。
• 您期望您的parse_file方法返回什么？它可能不会返回您认为它正在返回的内容，因为它目前正在编写。

考虑到这一点，让我们做一些更改：

< li >让我们读取输入的第一行，以确定节点总数。 < li >让我们预先分配节点，这样每个节点只实例化一次。 < li >让我们使用一个数组(带有从零开始的索引)来保存我们的节点引用。在实例化节点和对数组执行查找时，我们必须记住这一点(使用基于一的节点id)。 < li >当我们看到无效的节点id时，让我们停止处理相邻节点。 < li >让我们对所有输入使用< code>String#chomp和< code>String#to_i。 < li >让我们实际追加相邻节点... < li >让我们在方法的末尾返回节点数组，这样调用者可以得到一些有用的信息。

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

现在你有了无限嵌套的图(你可以在任何节点上调用< code>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

使用系统调用很奇怪；您真的不需要它来获取文件中的第一行。

第一行表示节点数。

之后的每一行表示给定节点的相邻节点。linen表示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