Помогите решить лабораторную работу в универе Python

Задача 2.3 (Числа Эрдеша)

PC/UValDs: 110206/10044

Венгерский ученый Пауль Эрдеш (Paul Erdus, 1913-1966) был одним из самых известных математиков XX века. Любой математик, имевший честь быть соавтором Эрдеша, глубоко уважаем.

К сожалению, не у всех была возможность написать статью совместно с Эрдешем, лучшее, что они могли сделать, - это опубликовать статью с кем-либо, кто опубликовал научную статью в соавторстве с Эрдешем. Это дало начало так называемым числам Эрдеша. Автор, публиковавшийся совместно с Эрдешем, имеет число Эрдеша 1. Автор, не публиковавшийся с Эрдешем, но публиковавшийся совместно с кем-либо, кто имеет число Эрдеша 1, получал число Эрдеша 2 и т. д.

Ваша задача - написать программу, которая рассчитывает числа Эрдеша для данного множества статей и ученых.

Входные данные

Первая строка входных данных содержит число сценариев. Каждый сценарий состоит из базы данных статей и из списка имен. Он начинается со строки вида Р N, где Р и N- натуральные числа. За этой строкой следует база данных статей из Р строк, каждая из которых содержит описание одной статьи, выглядящее так:

Smith, M.N. , Martin, G. , Erdos, P. : Newtonian forms of prime factors

После Р статей идут N строк с именами. Такая строка с именем имеет следующий формат:

Martin,   G.

Выходные данные

Для каждого сценария вы должны вывести строку, содержащую "Scenario /'" (где I - это номер сценария), и имена авторов вместе с их числами Эрдеша для всех авторов из списка имен. Авторы должны выводиться в том же порядке, в котором они были в списке имен. Число Эрдеша основано на статьях из базы данных статей этого сценария. Авторы, которые не имеют никакого отношения к Эрдешу судя по статьям данной базы данных, имеют число Эрдеша " infinity".

Пример входных данных

1
4 3
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors
Erdos, P., Reisig, W.: Stuttering in petri nets
Smith, M.N., Chen, X.: First order derivates in structured programming
Jablonski, Т., Hsueh, Z.: Selfstabilizing data structures
Smith, M.N.
Hsueh, Z.
Chen, X.

Соответствующие выходные данные

Scenario 1
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2

Мой код выдаёт везде "Infinity", кроме Scenario: 1. В чём ошибка?

def calculate_erdos_number(database, names):
    graph = {}  # граф соавторств
    erdos_numbers = {}  # числа Эрдеша для каждого автора

    # Инициализация чисел Эрдеша
    for name in names:
        erdos_numbers[name] = float('inf')

    # Построение графа соавторств
    for article in database:
        authors = article.split(':')[0].split(',')
        for i in range(len(authors)):
            for j in range(i + 1, len(authors)):
                author1 = authors[i].strip()
                author2 = authors[j].strip()
                if author1 not in graph:
                    graph[author1] = set()
                if author2 not in graph:
                    graph[author2] = set()
                graph[author1].add(author2)
                graph[author2].add(author1)

    # Поиск чисел Эрдеша для каждого автора
    visited = set()  # посещенные авторы
    queue = []  # очередь для обхода в ширину

    # Начальные авторы (те, у которых число Эрдеша равно 1)
    for name in names:
        if name in graph:
            erdos_numbers[name] = 1
            queue.append(name)
            visited.add(name)

    # Обход в ширину для нахождения чисел Эрдеша
    while queue:
        current_author = queue.pop(0)
        for neighbor in graph[current_author]:
            if neighbor not in visited:
                erdos_numbers[neighbor] = erdos_numbers[current_author] + 1
                queue.append(neighbor)
                visited.add(neighbor)

    return erdos_numbers


# Чтение входных данных
num_scenarios = int(input())
scenarios = []
for _ in range(num_scenarios):
    num_articles, num_names = map(int, input().split())
    articles = []
    for _ in range(num_articles):
        articles.append(input())
    names = [input().strip() for _ in range(num_names)]
    scenarios.append((articles, names))

# Выполнение сценариев
for i, (articles, names) in enumerate(scenarios, start=1):
    erdos_numbers = calculate_erdos_number(articles, names)
    print(f"Scenario {i}")
    for name in names:
        if erdos_numbers[name] == float('inf'):
            print(f"{name} infinity")
        else:
            print(f"{name} {erdos_numbers[name]}")

Ответы (1 шт):

Автор решения: Stanislav Volodarskiy

Я нашёл две ошибки:

  1. Неверно разобраны авторы статей. Разбиение по запятым приводит к ['Erdos', 'P.', 'Reisig', 'W.']. Авторов было два, разобраны они на четыре строки, которые следует объединить попарно:
def parse_authors(authors):
    return tuple(map(
        ', '.join,
        zip(*(iter(map(str.strip, authors.split(','))), ) * 2)
    ))

...

        # authors = article.split(':')[0].split(',')
        authors = parse_authors(article[:article.index(':')])
  1. Выделение непосредственных соавторов сделано с ошибкой:
        # if name in graph:
        if name in graph['Erdos, P.']:

Если хорошенько почистить получится такое:

import collections


def parse_authors(authors):
    return tuple(map(
        ', '.join,
        zip(*(iter(map(str.strip, authors.split(','))), ) * 2)
    ))


def calculate_erdos_number(articles, names):
    
    # Построение графа соавторств
    graph = {}
    for article in articles:
        coauthors = parse_authors(article[:article.index(':')])
        for a in coauthors:
            for b in coauthors:
                graph.setdefault(a, set()).add(b)

    erdos_numbers = {'Erdos, P.': 0}  # числа Эрдеша для каждого автора
    queue = collections.deque(['Erdos, P.'])  # очередь для обхода в ширину
    while queue:
        author = queue.pop()
        erdos_number = erdos_numbers[author] + 1
        for coauthor in graph[author]:
            if coauthor not in erdos_numbers:
                erdos_numbers[coauthor] = erdos_number
                queue.append(coauthor)

    return erdos_numbers


def main():
    for i in range(int(input())):
        n, p = map(int, input().split())
        articles = [input() for _ in range(n)]
        names = [input().strip() for _ in range(p)]
        erdos_numbers = calculate_erdos_number(articles, names)
        print(f"Scenario {i + 1}")
        for name in names:
            print(f"{name} {erdos_numbers.get(name, 'infinity')}")


main()
→ Ссылка