将文本文件转换为图形

Question

我目前正在尝试从项目 euler 中解决问题 81。如何将带有数字流的 txt 文件转换为存储图形的字典？

现在，我的计划是将文本文件中的数字用逗号分隔（它们不是“预网格”，所以它不是 80 x 80 结构）并将它们转换成字典，我可以将它们存储为图形

其中所有顶点垂直和水平连接

所以取 txt 文件中的项目（使用 4 x 4 网格作为演示）：

"a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p"

将它们转换为存储图形的字典

graph = {

    a: b, e

    b: a, c, f

    c: b, d, g 

    etc etc ...

}  

我将使用 djkstra 的算法从中找到最小路径，因为 txt 文件中的值实际上是整数并具有权重值

PS这是解决问题的好方法吗？

Answer 1

在问题 81 中，你只能向右或向下移动。所以你的 Dijkstra 算法需要一个有向图。如果您使用字典作为图形，则此 dict 中的每个值（列表）不得超过 2 个节点（您只能在 2 个方向上移动 -> 2 个邻居）。您可以删除if@AustinHastings 的最后一段代码中的前两个块。否则，您将向 4 个方向移动并得到不同的结果。这是问题 81 中示例的解决方案。我使用了包networkx和jupyter notebook：import networkx as nximport numpy as npimport collectionsa = np.matrix("""131 673 234 103 18;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;201 96 342 965 150;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;630 803 746 422 111;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;537 699 497 121 956;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;805 732 524 37 331""")rows, columns = a.shape# Part of @AustinHastings solutiongraph = collections.defaultdict(list)for r in range(rows):&nbsp; &nbsp; for c in range(columns):&nbsp; &nbsp; &nbsp; &nbsp; if c < columns - 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;# get the right neighbor&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;graph[(r, c)].append((r, c+1))&nbsp; &nbsp; &nbsp; &nbsp; if r < rows - 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;# get the bottom neighbor&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;graph[(r, c)].append((r+1, c))G = nx.from_dict_of_lists(graph, create_using=nx.DiGraph)weights = {(row, col): {'weight': num} for row, r in enumerate(a.tolist()) for col, num in enumerate(r)}nx.set_node_attributes(G, values=weights)def weight(u, v, d):&nbsp; &nbsp; return G.nodes[u].get('weight')/2 + G.nodes[v].get('weight')/2target = tuple(i - 1 for i in a.shape)path = nx.dijkstra_path(G, source=(0, 0), target=target, weight=weight)print('Path: ', [a.item(i) for i in path])%matplotlib inlinecolor_map = ['green' if n in path else 'red' for n in G.nodes()]labels = nx.get_node_attributes(G, 'weight')pos = {(r, c): (c, -r) for r, c in G.nodes()}nx.draw(G, pos=pos, with_labels=True, node_size=1500, labels = labels, node_color=color_map)输出：Path:&nbsp; [131, 201, 96, 342, 746, 422, 121, 37, 331]

Answer 2

在问题 81 中，你只能向右或向下移动。所以你的 Dijkstra 算法需要一个有向图。如果您使用字典作为图形，则此 dict 中的每个值（列表）不得超过 2 个节点（您只能在 2 个方向上移动 -> 2 个邻居）。您可以删除if@AustinHastings 的最后一段代码中的前两个块。否则，您将向 4 个方向移动并得到不同的结果。这是问题 81 中示例的解决方案。我使用了包networkx和jupyter notebook：import networkx as nximport numpy as npimport collectionsa = np.matrix("""131 673 234 103 18;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;201 96 342 965 150;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;630 803 746 422 111;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;537 699 497 121 956;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;805 732 524 37 331""")rows, columns = a.shape# Part of @AustinHastings solutiongraph = collections.defaultdict(list)for r in range(rows):&nbsp; &nbsp; for c in range(columns):&nbsp; &nbsp; &nbsp; &nbsp; if c < columns - 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;# get the right neighbor&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;graph[(r, c)].append((r, c+1))&nbsp; &nbsp; &nbsp; &nbsp; if r < rows - 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;# get the bottom neighbor&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;graph[(r, c)].append((r+1, c))G = nx.from_dict_of_lists(graph, create_using=nx.DiGraph)weights = {(row, col): {'weight': num} for row, r in enumerate(a.tolist()) for col, num in enumerate(r)}nx.set_node_attributes(G, values=weights)def weight(u, v, d):&nbsp; &nbsp; return G.nodes[u].get('weight')/2 + G.nodes[v].get('weight')/2target = tuple(i - 1 for i in a.shape)path = nx.dijkstra_path(G, source=(0, 0), target=target, weight=weight)print('Path: ', [a.item(i) for i in path])%matplotlib inlinecolor_map = ['green' if n in path else 'red' for n in G.nodes()]labels = nx.get_node_attributes(G, 'weight')pos = {(r, c): (c, -r) for r, c in G.nodes()}nx.draw(G, pos=pos, with_labels=True, node_size=1500, labels = labels, node_color=color_map)输出：Path:&nbsp; [131, 201, 96, 342, 746, 422, 121, 37, 331]