S_Lord of The Rings

"""
В этом номере я восопльзовался результатами номеров 2-3, например, использую найденные индексы начала
и конца каждой главы в тексте книги "Братство кольца"
"""

from pdfminer.high_level import extract_text
import json
import requests

file = "j-r-r-tolkien-lord-of-the-rings-01-the-fellowship-of-the-ring-retail-pdf.pdf"
text = extract_text(file)
txt_list = text.split() #список всех слов книги, разделённых пробелом

#Так пишутся названия глав в скачанном тексте:
chapters_titles_in_pfd = [
    "A LONG-EXPECTED PARTY",
    "THE SHADOW OF THE PAST",
    "THREE IS COMPANY",
    "A SHORT CUT TO MUSHROOMS",
    "A CONSPIRACY UNMASKED",
    "THE OLD FOREST",
    "IN THE HOUSE OF TOM BOMBADIL",
    "FOG ON THE BARROW-DOWNS",
    "AT THE SIGN OF THE PRANCING PONY",
    "STRIDER",
    "A KNIFE IN THE DARK",
    "FLIGHT TO THE FORD", #Chapter 12
    "MANY MEETINGS",
    "THE COUNCIL OF ELROND",
    "THE RING GOES SOUTH",
    "A JOURNEY IN THE DARK",
    "THE BRIDGE OF KHAZAD-DUˆ M",
    "LOTHLO´ RIEN",
    "THE MIRROR OF GALADRIEL",
    "FAREWELL TO LO´ RIEN",
    "THE GREAT RIVER",
    "THE BREAKING OF THE FELLOWSHIP",
]

indexes = [80513, 135385, 195047, 246726, 277838, 305571, 340779, 370761, 406890, 440901, 471795, 522770, 569883, 618489, 704484, 761559, 823374, 852567, 902818, 938981, 971921, 1010478]
chapters_idx_in_text = {}
for i in range(0, len(chapters_titles_in_pfd)):
    if i == len(chapters_titles_in_pfd)-1:
        chapters_idx_in_text[chapters_titles_in_pfd[i]] = (indexes[i], -1)
    else:
        chapters_idx_in_text[chapters_titles_in_pfd[i]] = (indexes[i], indexes[i + 1])

#print(chapters_idx_in_text)
url = 'https://the-one-api.dev/v2/character'
from requests.structures import CaseInsensitiveDict
headers = CaseInsensitiveDict()
headers["Accept"] = "application/json"
headers["Authorization"] = "Bearer 7mbNq6GVWo0LiEQS7GCc"
get_characters = requests.get(url, headers=headers)
if get_characters.status_code == requests.codes.ok:
    api_characters = get_characters.json()

#Делаем API запрос, чтобы узнать все имена персонажей из "Вдастелина колец"
all_characters = []
for one in api_characters["docs"]:
    all_characters.append(one["name"])
#Узнаем, какие имена встречаются в тексте
heroes_in_text = []
for hero in all_characters:
    if hero in txt_list:
        heroes_in_text.append(hero)



#Будем называть ИНДЕКСОМ ГЕРОЯ каждый индекс вхождения слова в список txt_list -- список всех слов, разделённых пробелом
#Например:
# имя героя -- 'a'
#txt_list = ['a','b','c','a']
#Тогда 0 и 3 -- являются ИНДЕКСАМИ героя


#Функции
#Посчитать расстояние между 2-мя индексами
def dst(a, b):
    return abs(a - b)



#Посчитать расстояние между одним индексом героя A и всеми индексами героя B
def binP_dst(x, array):
    L = 0
    R = len(array) - 1
    while R - L > 1:
        idx = (L + R) // 2
        y = array[idx]
        if y >= x:
            R = idx
            L = (L + R) // 2
        else:
            L = idx
            R = (R + len(array)) // 2
    if dst(x, array[L]) <=  dst(x, array[R]):
        return dst(x, array[L])
    else:
        return dst(x, array[R])



heroes_idx = {}


#Посчитать минимальное расстояние между именами 2-х героев в тексте
def min_dist(hero_A, hero_B):
    min_dst = pow(10, 10)
    idx_A = heroes_idx[hero_A]
    idx_B = heroes_idx[hero_B]
    for i in range(len(idx_A)):
        new_dst = binP_dst(idx_A[i], idx_B)
        if new_dst < min_dst:
            min_dst = new_dst
    return min_dst


#Получить список всех индексов одного персонажа в списке txt_list
def get_idx(hero_name):
    hero = hero_name
    from_ = 0
    all_idx = []
    while hero in txt_list[from_::]:
        idx = txt_list.index(hero, from_)
        all_idx.append(idx)
        from_ = idx+1
    return all_idx


#Теперь посчитаем все индексы для каждого героя
for hero in heroes_in_text:
    hero_idx = get_idx(hero)
    heroes_idx[hero] = hero_idx





heroes_dist = {}
for hero in heroes_in_text:
    heroes_dist[hero] = {}

for hero_A in heroes_idx:
    for hero_B in heroes_idx:
        if (hero_A != hero_B) and (hero_B not in heroes_idx[hero_A]) and (hero_A not in heroes_idx[hero_B]):
            minimum_dist = min_dist(hero_A, hero_B)
            heroes_dist[hero_A][hero_B] = minimum_dist
            heroes_dist[hero_B][hero_A] = minimum_dist


with open("heroes_dist.json", 'w', encoding='utf-8') as fh:
    fh.write(json.dumps(heroes_dist, ensure_ascii=False, indent = 4))

#Персонажи не связаны, если количество слов между ними больше N.
#Пусть N = среднеарифметиечское кол-во слов в одной главе, делённое на 80
N = len(txt_list) / len(chapters_titles_in_pfd) / 80
"""Обоснование выбора числа N  в задании 4.
Назовём героев "связными", если они вместе принимают участие хотя бы в одном эпизоде.
Глава -- это смысловая часть, в которой происходит какой-то некотрое количество эпизодов.
Значит, если два каких-то персонажа фигурируют в одной и той же главе, то есть вероятность,
что они вместе принимают,участие в каком-то эпизоде.

Чтобы как можно более точно отразить связть персонажей между собой, разделим
средний размер главы на 80, предпологая, что в одной главе может быть до 80 эпизодов.
Теперь после деления на 80 вероятность того, что персонажи принимают участие в одном эпиходе, значительно возросла.

В итоге вышло, что N = 110 (примерно).
Больше этого значения N лучше не брать, поскольку, чем больше N, тем более запутанный и визуально непонятный граф.
"""

#Строим граф
import networkx as nx
import matplotlib.pyplot as plt
from random import randint
G = nx.Graph()
marked_edges = []
colors = ['red', 'green', 'pink',  'brown', 'yellow', 'purple', 'blue']

for hero_A in heroes_in_text:
    for hero_B in heroes_dist[hero_A]:
        if heroes_dist[hero_A][hero_B] <= N:
            if min(hero_A, hero_B) + max(hero_A, hero_B) not in marked_edges:
                marked_edges.append(min(hero_A, hero_B) + max(hero_A, hero_B))
                G.add_edge(hero_A, hero_B, weight = heroes_dist[hero_A][hero_B])
color_map = []
cnt = -1 #сделаем рандомные цвета для всех вершин, чтобы было легче различать разных героев
for edge in G:
    cnt += 1
    cnt %= len(colors)
    color_map.append(colors[cnt])
color_map_2 = []
cnt = -1
for node in G:
    cnt += 1
    cnt %= len(colors)
    color_map_2.append(colors[cnt])
#Разноцветные рёбра в графе могут помочь лучше проследить связть между 2-мя персонажами
nx.draw(G, with_labels=True,node_color= color_map_2,edge_color = color_map)#,  node_size = 10
#plt.savefig("N4_22.png")
plt.show()