зуйвий.py

import re
import queue
from graphviz import Digraph
from PIL import Image
import copy


# Чтение входных данных из файла
def readInputData(filename):
    with open(filename) as f:
        read_data = f.read()
    return read_data

# Вывод графа
def draw_graph(graph,start,end):
    
    nodes = start.union(end)
    G=Digraph(format='png')

    for node in nodes:
        G.node(node)

    for i in graph:
        for j in graph[i]:
            G.edge(i, j)
    G.render('graph')
    img = Image.open('graph.png')
    img.show()

# Из информации, прочитанной из файла, формируем представление графа
# в виде хэш-таблицы.
def makeEdgesDict(dataFromFile):
    edgesListString = re.findall(r'\d+\s\d+',dataFromFile)
    edges = {}
    for i in edgesListString:
        key, value = i.split(' ')
        edges.setdefault(key,[])
        edges[key].append(value)
    return edges

# Из списка ребер, извлечем i,j узлы
def getStartAndEndOfNodes(edges):
    start = edges.keys()
    end = []
    for i in edges.values():
        for j in i:
            end.append(j)
    start = set(start)
    end = set(end)
    return start,end

#Т.к. из вершины исходят ребра с определенным уровнем
# Найдем уровень для каждой вершины
def doMagic(startNode,edges):
    copy_edges = copy.copy(edges)
    
    startNodeList = set()
    startNodeList.add(startNode)

    level = {}
    level.setdefault(startNode,0)

    while len(copy_edges)>0 and len(startNodeList)>0:
        startNode = startNodeList.pop()
        copy_edges.pop(startNode)
        start, end = getStartAndEndOfNodes(copy_edges)
        # найдем вершины в которую ничего не входит
        for i in start:
            if i not in end:
                startNodeList.add(i)
                level.setdefault(i,level[startNode]+1)
    return level
    

def main():
    dataFromFile = readInputData('data.txt')
    edges = makeEdgesDict(dataFromFile)

    # найдем начальный узел
    start, end = getStartAndEndOfNodes(edges)
    startNode = ''

    for i in start:
        if i not in end:
            startNode = i
            break

    orderVertexByLayer = doMagic(startNode,edges)
    orderEdgesByLayer = {}

    for i in orderVertexByLayer:
        layer = orderVertexByLayer.get(i)
        orderEdgesByLayer.setdefault(layer,[])
        for j in edges[i]:
            orderEdgesByLayer[layer].append({i:j})

    for i in orderEdgesByLayer:
        print('{} layer: '.format(i))
        for j in orderEdgesByLayer.get(i):
            for k in j:
                print('[{},{}]'.format(k,j.get(k)))
    
    draw_graph(edges,start,end)
        
if __name__=='__main__':
    main()