python - 读取带有图边列表的文件并在 Python 中创建邻接列表
问题描述
我的程序创建一个完整的图形,打印边缘,然后创建一个邻接列表。但是,它效率不高。我希望该程序:
- 将边缘列表打印到文本文件中,然后
- 让程序的创建邻接列表部分读取该边缘列表文件并打印邻接列表。目前,我将边缘列表硬编码到效率不高的程序中,因为我需要能够更改 V 来测试不同的运行时。
import networkx as nx
import matplotlib.pyplot as plt
#Create complete graph
complete_graph = nx.complete_graph(10)
plt.subplot(121)
nx.draw(complete_graph, with_labels=True, font_weight='bold')
#list edges -----I want this to output to a file instead
list(complete_graph.edges)
# A class to represent the adjacency list of the node
class AdjNode:
def __init__(self, data):
self.vertex = data
self.next = None
# A class to represent a graph. A graph
# is the list of the adjacency lists.
# Size of the array will be the no. of the
# vertices "V"
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [None] * self.V
# Function to add an edge in an undirected graph
def add_edge(self, src, dest):
# Adding the node to the source node
node = AdjNode(dest)
node.next = self.graph[src]
self.graph[src] = node
# Adding the source node to the destination as
# it is the undirected graph
node = AdjNode(src)
node.next = self.graph[dest]
self.graph[dest] = node
# Function to print the graph
def print_graph(self):
for i in range(self.V):
print("Adjacency list of vertex {}\n head".format(i), end="")
temp = self.graph[i]
while temp:
print(" -> {}".format(temp.vertex), end="")
temp = temp.next
print(" \n")
# Driver program to the above graph class. -----> instead of coding each edge, I'd like for main to
# read the edge text file created earlier to create the Adjacency List.
if __name__ == "__main__":
V = 10
graph = Graph(V)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(0, 3)
graph.add_edge(0, 4)
graph.add_edge(0, 5)
graph.add_edge(0, 6)
graph.add_edge(0, 7)
graph.add_edge(0, 8)
graph.add_edge(0, 9)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(1, 5)
graph.add_edge(1, 6)
graph.add_edge(1, 7)
graph.add_edge(1, 8)
graph.add_edge(1, 9)
graph.add_edge(2, 3)
graph.add_edge(2, 4)
graph.add_edge(2, 5)
graph.add_edge(2, 6)
graph.add_edge(2, 7)
graph.add_edge(2, 8)
graph.add_edge(2, 9)
graph.add_edge(3, 4)
graph.add_edge(3, 5)
graph.add_edge(3, 6)
graph.add_edge(3, 7)
graph.add_edge(3, 8)
graph.add_edge(3, 9)
graph.add_edge(4, 5)
graph.add_edge(4, 6)
graph.add_edge(4, 7)
graph.add_edge(4, 8)
graph.add_edge(4, 9)
graph.add_edge(5, 6)
graph.add_edge(5, 7)
graph.add_edge(5, 8)
graph.add_edge(5, 9)
graph.add_edge(6, 7)
graph.add_edge(6, 8)
graph.add_edge(6, 9)
graph.add_edge(7, 8)
graph.add_edge(7, 9)
graph.add_edge(8, 9)
graph.print_graph()
输出:
Adjacency list of vertex 0
head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1
Adjacency list of vertex 1
head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 0
Adjacency list of vertex 2
head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 1 -> 0
Adjacency list of vertex 3
head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 2 -> 1 -> 0
Adjacency list of vertex 4
head -> 9 -> 8 -> 7 -> 6 -> 5 -> 3 -> 2 -> 1 -> 0
Adjacency list of vertex 5
head -> 9 -> 8 -> 7 -> 6 -> 4 -> 3 -> 2 -> 1 -> 0
Adjacency list of vertex 6
head -> 9 -> 8 -> 7 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
Adjacency list of vertex 7
head -> 9 -> 8 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
Adjacency list of vertex 8
head -> 9 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
Adjacency list of vertex 9
head -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
解决方案
完成所需内容的最简单方法是使用 json 对其进行序列化和反序列化。
你将有一个Graph
这样的方法:
import json
def serialize(self) -> str:
graph = {}
for i in range(self.V):
temp = self.graph[i]
tmp_list = []
while temp:
tmp_list.append(temp)
temp = temp.next
graph[i] = json.dumps(tmp_list).replace(",", "->")
return json.dumps(graph, indent=4)
它将返回格式如下的字符串:
{
"3": "[1->2->3]",
"5": "[1->2->3]"
}
您可以将其保存到文件中或做任何您想做的事情。
对于反序列化,我们将需要另一种方法:
@staticmethod
def deserialize(serialized: str) -> "Graph":
serialized = serialized.replace("->", ",")
graph_dict = json.loads(serialized)
V = len(graph_dict)
graph = Graph(V)
for src in graph_dict.keys():
for dest in graph_dict[src]:
graph.add_edge(src, dest)
return graph
推荐阅读
- jenkins - 如何在 jenkins ssh 代理中接受 ssh 主机验证
- xml - 使用交互式代理从 python 3 中的特定标签中提取基本数据
- javascript - 进度百分比可以在控制台中看到,但不能在 html 中看到
- java - 使用 java.time 确定一天中的小时数
- openstack - 无法使用打包器制作 openstack 映像
- python - Python 二等分搜索未运行且没有错误消息。麻省理工学院
- button - 居中按钮和响应式设计
- git - BitBucket 创建本地仓库并通过 gitCMD 将其克隆到 BitBucket
- javascript - 使 For 循环成为函数
- r - 仅使用 dplyr 对数字列和数据框的第一行和最后一行进行变异值