from collections import defaultdict
from graphviz import Digraph
def create_graph(node_relations):
graph = defaultdict(list)
for u, v in node_relations:
graph[u].append(v)
return graph
def topological_sort(graph):
visited = {}
for key, values in graph.items():
visited[key] = False
for val in values:
visited[val] = False
stack = []
def topological_sort_util(v):
visited[v] = True
for node in graph[v]:
if not visited[node]:
topological_sort_util(node)
stack.insert(0, v)
for node in visited.keys():
if not visited[node]:
topological_sort_util(node)
return stack
def draw_graph(node_relations):
dot = Digraph(comment='node graph', filename='blueprintNodeGraph-neato', format='png', engine='neato')
dot.attr(
'node',
shape='box', style='rounded,filled',
fixedsize='false',
fontname='Microsoft YaHei', fontsize='12')
node_size = 0
for relation in node_relations:
node_size += 1
dot.edge(relation[0], relation[1], len='3')
print(f"{relation[0]} -> {relation[1]}")
dot.render(directory='doctest-output', view=True).replace('\\', '/')
if __name__ == '__main__':
# 节点关系
node_relations = (('MA140', 'MA141'),('MA141', 'MA140'),('MA141', 'CS225'),
('MA141', 'CS150'),('CS150', 'MA141'),('CS150', 'CS155'),
('CS225', 'MA141'),('CS225', 'CS155'),('CS225', 'CS300'),
('CS225', 'CS250'),('CS225', 'CS230'),('CS155', 'CS225'),
('CS155', 'CS200'),('CS155', 'CS150'),('CS200', 'CS155'),
('CS250', 'CS350'),('CS250', 'CS360'),('CS250', 'CS225'),
('CS350', 'CS250'),('CS230', 'CS225'),('CS300', 'CS340'),
('CS300', 'CS301'),('CS300', 'CS225'),('CS301', 'CS300'),
('CS340', 'CS360'),('CS340', 'CS300'),('CS340', 'CS345'),
('CS345', 'CS340'),('CS360', 'CS390'),('CS360', 'CS250'),
('CS360', 'CS340'),('CS390', 'CS360'))
# 创建图
graph = create_graph(node_relations)
# 拓扑排序
topo_list = topological_sort(graph)
print(topo_list)
# 绘图
draw_graph(node_relations)
如何将节点关系node_relations改为用户输入模式,有用户输入节点关系,使其达到用户可以通过该界面输入关系,显示关系图,并运行后给出尽可能多的拓扑排序结果的效果,谢谢