Теорія графів у Грі Престолів



Нещодавно, на Geektimes я опублікував статті, де навів трохи поверхневої статистики з серії книг «Пісня льоду і полум'я». Але я не став заглиблюватися в найцікавішу частину, граф соціальних зв'язків, бо тема заслуговує окремої уваги. У цій статті я покажу як теорія графів може допомогти при аналізі подібних даних і наведу реалізації алгоритмів, якими я користувався.

Всім кому цікаво, ласкаво просимо під кат.

З опитування вищезгаданої статті, я зробив висновок, що більше третини аудиторії Geektimes ознайомлено з книгою фентезі роману, а більше половини з сюжетом серіалу. Я сподіваюся, аудиторії Geektimes і Habrahabr перетинаються і вам можливо будуть цікаві не тільки використані алгоритми, але і результати.

Дані
Почнемо, звичайно ж, з головного — даних. У нас є граф соціальної активності:



На ньому зображені персонажі з світу престолів у вершинах графа, де розмір вершини залежить від сказаних ним слів, і діалогів персонажів на ребрах графа, де товщина ребра залежить від кількості проведених розмов.

Загальні відомості про графи:

Неорієнтований Граф.
Вершин (читай персонажів): 1105
Ребер (читай діалогів): 3505

Це все добре, але хто ж склав список усіх розмов, та ще й визначив їх приналежність запитаєте ви мене (в 5-ти книгах адже майже 2 мільйони слів). Метод умовних випадкових полів, відповім я. Так, для збору даних було залучено машинне навчання і, як заявляє «тренер» моделі, точність визначення приналежності розмови становить близько 75%. Я додам опитувальник в кінці статті, щоб дізнатися варто перекладати цю статтю про те як метод умовних випадкових полів був застосований.

Отже, формат вхідних даних для всіх алгоритмів буде однаковий:

Перший рядок містить V та E, кількість вершин та ребер в графі відповідно.

Далі йдуть V рядків з ID персонажа і його іменем. Після цього E рядків виду u v w — опис ребер. Означає, що між u та v є ребро з вагою w, u та v ID персонажа. Нагадаю, що вага означає кількість діалогів між відповідними персонажами. Вага самих вершин враховуватися ніде не буде, оскільки не знайшов гідного йому застосування. Ах да, код алгоритмів буде представлений на мові C++.

Нам, звичайно ж, потрібно вважати дані. Для цього я створив файли definitions.h definitions.cpp. Далі я скрізь буду підключати definitions.h щоб коду було менше і код читався легше. Кожен наступний алгоритм реалізований як окрема функція і викликається функції main.

defenitions.h
#ifndef DEF_H
#define DEF_H
#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include < iostream>
#include < string>
#include < vector>
#include <map>
#include < algorithm>
#include <queue>
#include <set>
#include <iterator>
#include <functional>

using namespace std;

extern int reverseID[];
extern vector<int> id;
extern vector < vector < int> > weight, edge;
extern map<int, string> name;
extern int V, E;

void read_data();
#endif


definitions.cpp
#include "definitions.h"

int reverseID[3000];
vector<int> іd; // origin ID of characters
vector < vector < int> > weight; // weights edges of
vector < vector < int> > edge; // the graph's edges
map<int, string> name; // names of characters
int V, E; // amount of vertices edges and

void read_data() {
freopen("input.in", "r", stdin); // read from the input file

cin >> V >> E;

id.resize(V);
weight.resize(V);
edge.resize(V);

int u;
char s[100];
for (int i = 0; i < V; i++) { // read the names
scanf("%d %[^\n]", &u, s);
name[i] = string(s);
id[i] = u; // origin ID by assigned ID
reverseID[u] = i; // assigned ID by origin ID
}

int a, b, w;
for (int i = 0; i < E; i++) { // read the edges and weights
cin >> a >> b >> w;
edge[reverseID[a]].push_back(reverseID[b]);
edge[reverseID[b]].push_back(reverseID[a]);
weight[reverseID[a]].push_back(w);
weight[reverseID[b]].push_back(w);
}
}


main.cpp
#include "definitions.h"
#include "degree.h"
#include "dfsbfs.h"
#include "bridges_articulations.h"
#include "cliques.h"
#include "spanning.h"
#include "cut.h"

int main() {
read_data();

degree();
count_components();
calculate_diameter();
find_cliques();
get_spanning_tree();
find_bridges_and_articulations();
find_cut();
}


Ступінь вершини
Для початку спробуємо реалізувати щось дуже просте, що навіть соромно назвати алгоритмом, але буде цікаво читачеві/глядачеві. Знайдемо ступінь кожної вершини. Ступінь вершини — це кількість ребер, інцидентних (примикають до) вершини. Цей параметр в контексті графа, який ми маємо, покаже нам скільки ж «друзів» у персонажа.

Це можна зробити за один прохід і складність цього алгоритму Про(V+E). Якщо застосувати і сортування результату, як це зробив я, то складність O(E+V*log(V)).

Алгоритм визначення ступеня вершин
#include "definitions.h"

void degree() {
freopen("degree.txt", "w", stdout); // output file

vector< pair<int,int> > degree(V);
for (int i = 0; i < V; i++) {
degree[i] = make_pair(edge[i].size(), i);
}

stable_sort(degree.begin(), degree.end());

for (int i = V-1; i >= 0; i--) {
cout << name[degree[i].second] << ": " << degree[i].first << endl;
}
}


Топ 10 багатозв'язних персонажів:

  1. Тіріон Ланністер: 168
  2. Джон Сноу: 128
  3. Арья Старк: 104
  4. Джеймі Ланністер: 102
  5. Серсея Ланністер: 86
  6. Кейтілін Старк: 85
  7. Теона Грейджой: 76
  8. Дайнерис Таргаріен: 73
  9. Брієнні: 71
  10. Санса Старк: 69
Весь список

Цікаво те, що в топі не виявилося того, хто знайомий з багатьма і за займаною посадою зобов'язаний підтримувати контакт з людьми, Вариса (він на 25ом місці). А ось, здавалося б, другорядний персонаж Брієнні, від імені якої голови ще немає, на 9ом місці.

Обхід графа
Отже, тепер перейдемо до простих алгоритмів, а саме до пошуку в глибину (Depth-first search) і пошуку в ширину (Breadth-first search). Обидва алгоритму дуже схожі, розрізняються тільки способом обходу графа. Вони застосовуються, коли потрібно пройти по ребрах від заданої вершини в графі до іншого. У разі пошуку в глибину, граф проходиться починаючи від вершини і по черзі в максимальну глибину по одному з вихідних ребер. У випадку ж з пошуком завширшки граф обходиться спочатку всім своїм сусідніх вершин, далі по сусідах сусідніх вершин і так поки не пройдених вершин не залишиться. Обидва алгоритми мають складність O(V+E).

Зв'язність графа
Знайдемо компоненти зв'язності нашого графа. Компонента зв'язності це підграф, у якого всі вершини мають шлях до будь-якої іншої вершини компоненти. Для цього запустимо алгоритм пошуку в глибину по одному з вершин, а після завершення, в такій, не позначеної алгоритмом, вершині. Таким чином кожен запуск пошуку означатиме нову компоненту зв'язності.

Код підрахунку компонент зв'язності
#include "definitions.h"

vector<bool> useddfs;
vector<int> comp;

void dfs(int u) {
useddfs[u] = true;
comp.push_back(u);
for (vector < int>:: iterator i = edge[u].begin(); i != edge[u].end(); i++)
if (!useddfs[*i])
dfs(*i);
}

void count_components() {
freopen("components.txt", "w", stdout); // output file

int comp_num = 0;
useddfs.resize(V, false);
for (int i = 0; i < V; i++) {
if (!useddfs[i]) {
comp.clear();
dfs(i);
comp_num++;
}
}
cout << comp_num;
}


Було б дуже дивно, якби граф був зв'язковим і в ньому було більше однієї компоненти, чи не правда? Але на мій подив в графі виявилося аж 3 компоненти! Але подивившись на них я побачив, що була присутня одна велика компонента, та 2 інші, в яких було по одному персонажеві (Це були усміхнений старий (A smiley old man), який розмовляв з Ар'єю біля Божого ока (god's eye). І кухар (A Cook), який грав з Варіс на кораблі). Нічого незвичайного, у них немає імен і дивно, що учасники розмови взагалі визначилися правильно. Я, звичайно ж, додав відсутні ребра і в результаті весь граф вийшов зв'язковим.

Теорія рукостискань
Наступне що ми знайдемо з допомогою алгоритму пошуку вже в ширину — максимальна кількість рукостискань в графі, іншими словами діаметр графа, тобто наидлиннейший з найкоротших шляхів між усіма вершинами графа. Як виявилося, максимальна кількість рукостискань це 8. Непоганий результат для твору про «середньовічних століттях», якщо враховувати Теорію 6-ти рукостискань. Для прикладу, одна з таких ланцюжків зв'язку:

Матінка Кротиха (Mother Mole) — Репійниця (Thistle) — Варамир (Varamyr) — Джон Сноу (Jon Snow) — Еддард Старк (Ned Stark) — Барристан Селмі (Barristan Selmy) — Квентін Мартелл (Quentyn Martell) — Принц-Халамидник (The Tattered Prince) — Льюїс Ланстер (Lewis Lanster)

Такий алгоритм працює за O(V*V+V*E). Так як потрібно запустити алгоритм BFS з кожної вершини графа. Будь цей граф деревом, то було б тільки 2 рази запустити BFS. Спочатку з будь-якої вершини графа, а потім з найвіддаленішої від неї вершини. І найбільша глибина останнього запуску і була б діаметром графа.

А раз я знайшов найдовші шляхи для всіх вершин графа, то можна обчислити і середнє значення, а так само скласти розподіл максимальних шляхів. Середнє значення для довжини максимальних шляхів виявилося 6,16 (в середньому цілком вписується в теорію про 6ти рукостисканнях), а загальна середня відстань 3,6, для порівняння у фейсбуку цей параметр 4.57.

Розподіл максимальних довжин шляхів:



Якщо поглянути на розподіл то ми бачимо що 77 персонажів знаходяться «в центрі» графа, іншими словами вони можуть зв'язатися з будь-яким іншим персонажем не більше ніж через 4х інших. Серед них всі основні персонажі історії, крім Дайнерис Таргаріен і Санса Старк, а серед тих, кому в книгах присвячено менше п'яти глав потрапили в список Барристан Селмі, Джон Коннингтон і Мелісандра.

Весь результат

Код знаходження наведених параметрів
#include "definitions.h"

vector<bool> usedbfs;

void bfs(int u, vector<int> &distance, vector<int> &path) {
queue<int> q;
q.push(u);
usedbfs[u] = true;
path[u] = -1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (vector < int>:: iterator i = edge[u].begin(); i != edge[u].end(); i++) {
int to = *i;
if (!usedbfs[to]) {
usedbfs[to] = true;
q.push(to);
distance[to] = distance[u] + 1;
path[to] = u;
}
}
}
}

void calculate_diameter() {
freopen("diameter.txt", "w", stdout); // output file

int diameter = 0;
int current_max = 0;
double average_max = 0;
double average_average = 0;
vector < vector < int> > distribution(V, vector<int> (0));
vector < vector < int> > max_path;
vector<int> farthest_node;
for (int i = 0; i < V; i++) {
vector<int> distance_to(V, 0);
vector<int> path(V,-1);
usedbfs.clear();
usedbfs.resize(V, false);
bfs(i, distance_to, path);
current_max = 0;
for (int j = 0; j < V; j++) {
average_average += distance_to[j];

if (distance_to[j] > current_max)
current_max = distance_to[j];

if (distance_to[j] > diameter) {
diameter = distance_to[j];
farthest_node.clear();
max_path.clear();
max_path.push_back(path);
farthest_node.push_back(j);
} else if (distance_to[j] == diameter){
max_path.push_back(path);
farthest_node.push_back(j);
}
}
average_max += current_max;
distribution[current_max].push_back(i);
}
average_max /= V;
average_average /= V*V;

cout << "Diameter: " << diameter << endl;
cout << "Average path: " << average_average << endl;
cout << "Average farthest path: " << average_max << endl;

vector < vector < int> > farthest_path; 

for (int i = 0; i < farthest_node.size(); i++) {
farthest_path.push_back(vector < int>());
for (int u = farthest_node[i]; u != -1; u = max_path[i][u])
farthest_path[i].push_back(u);
}

cout << "Farthest paths:" << endl;
for (int i = 0; i < farthest_path.size(); i++) {
cout << i+1 << ": ";
for (vector < int>:: iterator j = farthest_path[i].begin(); j != farthest_path[i].end(); j++)
cout << name[*j] << ". ";
cout << endl;
}

int minimum = V;
cout << "Farthest paths distribution:" << endl;
for (int i = 0; i <= diameter; i++) {
if (distribution[i].size() != 0 && i < minimum)
minimum = i;

cout << i << ": " << distribution[i].size() << endl;
}

cout << "Characters with minimum farthest path:" << endl;
for (vector < int>:: iterator i = distribution[minimum].begin(); i != distribution[minimum].end(); i++) {
cout << name[*i] << endl;
}
}


Кліки в графі
Алгоритм Брона-Кербоша дозволяє знайти максимальні кліки в графі, іншими словами підмножини вершин, будь-які дві з яких пов'язані ребром. У контексті розглянутого графа це дозволить знайти сильно пов'язані компанії, які спілкувалися між собою в історії. Складність алгоритму лінійна відносно кількості клік у графі, але в гіршому випадку вона экспоненциальна O(3V/3), алгоритм вирішує NP повну завдання все таки. Сам по собі алгоритм являє рекурсивні функцію, яка для кожної вершини знаходить максимальну кліку, тобто таку, в яку можна додати жодної іншої вершини. Отже, результати:

Розподіл розмірів клік:



Як видно, максимальна кліка розміром в 9 персонажів. Приміром одна з таких — компанія Ланністеров: Тіріон, Джеймі, Серсея, Варіс, Тайвін, Кеван, Пицель, Петіро і Мейс Тіреллі. Що цікаво, всі кліки розміру 8 і 9 сформовані в Королівській Гавані або поблизу неї. А максимальна кліка з Дайнерис розміру 5.

Весь результат

Код знаходження клік
#include "definitions.h"

vector < vector < int> > cliques;

bool compare_vectors_by_size(const vector<int> &i, const vector<int> &j)
{
return (i.size() > j.size());
}

void bron_kerbosch(set <int> R, set <int> P, set <int> X) { // where R is probable clique, P - possible vertices in clique, X - exluded vertices
if (P. size() == 0 && X. size() == 0) { // R is maximal clique
cliques.push_back(vector < int>(0));
for (set<int>:: iterator i = R. begin(); i != R. end(); i++) {
cliques.back().push_back(*i);
}
}
else {
set <int> foriterate = P;
for (set<int>:: iterator i = foriterate.begin(); i != foriterate.end(); i++) {
set <int> newR;
set <int> newP;
set <int> newX;

newR = R;
newR.insert(*i);

set_intersection(P. begin(), P. end(), edge[*i].begin(), edge[*i].end(), inserter(newP, newP.begin()));

set_intersection(X. begin(), X. end(), edge[*i].begin(), edge[*i].end(), inserter(newX, newX.begin()));

bron_kerbosch(newR, newP, newX);

P. erase(*i);
X. insert(*i);
}
}
}

void find_cliques() {
freopen("cliques.txt", "w", stdout); // output file

set <int> P;
for (int i = 0; i < V; i++) {
P. insert(i);
stable_sort(edge[i].begin(), edge[i].end());
}

bron_kerbosch(set<int>(), P, set<int>());

stable_sort(cliques.begin(), cliques.end(), compare_vectors_by_size);

cout << "Distribution:" << endl;
int max_size = 0;
int max_counter = 0;
for (int i = cliques.size()-1; i >= 0 ; i--) {
if (cliques[i].size() > max_size) {
if (max_counter > 0) {
cout << max_size << ": " << max_counter << endl;
}
max_size = cliques[i].size();
max_counter = 0;
}

max_counter++;
}
if (max_counter > 0) {
cout << max_size << ": " << max_counter << endl;
}

cout << "Cliques:" << endl;
for (int i = 0; i < cliques.size(); i++) {
cout << i + 1 << "(" << cliques[i].size() << "): ";
for (int j = 0; j < cliques[i].size(); j++) {
cout << name[cliques[i][j]] << ". ";
}
cout << endl;
}
}


Остовне дерево
А тепер трохи спростимо наш граф зв'язків, залишивши в ньому лише «кістяк», так зване остовне дерево, тобто найбільш важливі ребра зв'язку і при цьому перетворивши граф дерево з усіма вихідними даними вершинами. Допоможе нам в цьому алгоритм Крускала. Жадібний Алгоритм, для його здійснення потрібно всього лише відсортувати всі ребра по їх вазі і по черзі додавати кожне ребро, якщо воно пов'язує дві компоненти. Якщо використовувати правильну структуру даних (зазвичай використовують систему непересічних множин), то складність алгоритму вийде O(E(logE)+V+E) = O(E(logV)). Нижче наведено результат графа, який піддався цим маніпуляціям. Я так само для читання видалив ребра з вагою 1.


картинка кликабельна

Отже, з цього графа можна побачити головних героїв і їх зв'язок між собою. Як я і очікував, Тіріон Ланністер знаходиться в «центрі» всіх зв'язків, від нього виходять 4 великі гілки: Серсея Ланністер, Джон Сноу, Санса Старк і Джорах Мормонт (гілка Дайнерис). Останні в свою чергу герої наступного рівня зв'язків. Цілком очікуваний результат, чи не правда?

Весь результат

Код побудови остовного дерева
#include "definitions.h"

vector<int> p;

int dsu_get(int v) {
return (v == p[v]) ? v : (p[v] = dsu_get(p[v]));
}

void dsu_unite(int u, int v) {
u = dsu_get(u);
v = dsu_get(v);

if (rand() & 1)
swap(u, v);

if (u != v)
p[u] = v;
}


void get_spanning_tree() {
freopen("spanning.txt", "w", stdout); // output file

vector < pair < int, pair<int, int> > > edges_weights, result;

vector < vector<bool> > used;
for (int i = 0; i < V; i++) {
used.push_back(vector<bool>(V, 'false'));
}

for (int i = 0; i < V; i++) {
for (int j = 0; j < edge[i].size(); j++) {
int cur_v = edge[i][j];
if (!used[i][cur_v]) {
edges_weights.push_back(make_pair(weight[i][j], make_pair(i, cur_v)));
used[i][cur_v] = true;
used[cur_v][i] = true;
}
}
}

sort(edges_weights.begin(), edges_weights.end(), greater< pair < int, pair<int, int> > >());

for (int i = 0; i < V; i++) {
p.push_back(i);
}

for (int i = 0; i < E; i++) {
int u = edges_weights[i].second.first;
int v = edges_weights[i].second.second;
int w = edges_weights[i].first;

if (dsu_get(u) != dsu_get(v)) {
result.push_back(edges_weights[i]);
dsu_unite(u, v);
}
}

for (vector < pair < int, pair<int, int> > >::iterator i = result.begin(); i != result.end(); i++) {
cout << id[(i->second).first] << " " << id[(i->second).second] << " " << i>first << endl;
}
}


А ось скільки всього остовных дерев, включаючи не тільки максимальні можна побудувати? Неймовірно багато у даному графі, зрозуміло. Але їх можна підрахувати за допомогою теорему Кірхгофа. Теорема говорить, що якщо побудувати матрицю, де всі елементи матриці суміжності будуть замінені на протилежні, а на головній діагоналі будуть стояти ступеня відповідних вершин, то все алгебраїчні доповнення отриманої матриці будуть рівні і це значення буде кількістю остовных дерев графа.

Мости і шарніри
Мостами у графі називають ребра, при видаленні яких, кількість компонент зв'язності збільшується. Аналогічне визначення і шарнірів, тільки на відміну від мостів, шарніри це вершини, при видаленні яких кількість компонент зв'язності зростає. У даному графі, наявність мостів буде означати що в світі престолів існують зв'язки, які є єдиним джерелом комунікації між окремими групами персонажів. Шарніри ж, це герої, які є єдиним посередником до групи інших персонажів. Мости і шарніри шукати не дуже важко. Для цього нам знадобиться знайомий нам алгоритм пошуку в глибину, але злегка модифікований. Потрібно використовувати так зване час входу в вершину і функцію часу виходу (fout) на вершині, яка буде приймати значення мінімуму часу входу і значень fout вершини в яку пошук в глибину пройдено, таким чином, якщо при проході ребра виявиться, що значення функції fout на вершині більше ніж час заходу в неї, то це буде мостом, а так само і шарніром, а якщо одно, то тільки шарніром. Іншими словами ми перевіряємо, чи повертаємося ми після обходу в те ж саме ребро/вершину і тільки в неї при обході частини графа, якщо так, то це і буде шуканим мостом або шарніром.

Як і очікувалося, всі шарніри і мости охоплювали тільки малозначущих персонажів. Кількість вершин в компонентах, що вийшло б ізолювати, видаленням шарнірів і мостів, не перевищує 4х. Це означає, що немає героя, яким би неможливо було пожертвувати. Всі пов'язані між собою як мінімум через двох інших персонажів.

Весь результат

Код пошуку мостів і шарнірів
#include "definitions.h"

vector<bool> used, usedcnt;
int timer = 0;
vector<int> tin, fout, articulations;
vector < pair<int,int> > bridges;

int count_rec(int v, int skip) {
int cnt = 1;
usedcnt[v] = true;

for (int i = 0; i < edge[v].size(); i++) {
int to = edge[v][i];

if(to == skip || usedcnt[to]) 
continue;

cnt += count_rec(to skip);
}

return cnt;
}

int count_from(int v, int skip, bool clean = true){
usedcnt.resize(V, false);

if (clean) {
for (int i = 0; i < usedcnt.size(); i++)
usedcnt[i] = false;
}

return count_rec(v, skip);
}

void dfs(int v, int prev = -1) {
used[v] = true;
tin[v] = fout[v] = timer++;

int root_calls = 0;
bool in_ar_list = false;
for (int i = 0; i < edge[v].size(); i++) {
int to = edge[v][i];

if (to == prev) continue;

if (used[to])
fout[v] = min(fout[v], tin[to]);
else {
dfs(to, v);
fout[v] = min(fout[v], fout[to]);

if (fout[to] > tin[v]) {
bridges.push_back(make_pair(v, to));
}

if (fout[to] >= tin[v] && prev != -1 && !in_ar_list) {
articulations.push_back(v);
in_ar_list = true;
}

root_calls++;
}
}

if (prev == -1 && root_calls > 1)
articulations.push_back(v);
}

void find_bridges_and_articulations() {
freopen("bridges_and_articulations.txt", "w", stdout); // output file

used.resize(V, false);
tin.resize(V);
fout.resize(V);

for (int i = 0; i < V; i++)
if (!used[i])
dfs(i);

cout << "Bridges:" << endl;
for (int i = 0; i < bridges.size(); i++) {
cout << name[bridges[i].first] << " (" << count_from(bridges[i].first, bridges[i].second) << ") - " << name[bridges[i].second] << " (" << count_from(bridges[i].second, bridges[i].first) <<")" << endl;
}


cout << endl << "Articulation points:" << endl; 
for (int i = 0; i < articulations.size(); i++) {
int cur = articulations[i];
cout << name[cur];

for (int i = 0; i < usedcnt.size(); i++)
usedcnt[i] = false;

for (int j = 0; j < edge[cur].size(); j++) {
if (!usedcnt[edge[cur][j]]) {
int comp_size = count_from(edge[cur][j], cur, false); 
cout << " (" << comp_size << ")";
}
}
cout << endl;
}
}


Мінімальний розріз
Але все ж цікаво дізнатися, скільки героїв потрібно «вбити» щоб повністю виключити контакт двох найпопулярніших (за вищевикладеною статистикою) персонажів, скажімо, Тіріона Ланністеров і Арью Старк, або Джона Сноу і Серсо Ланністеров. Для цього будемо використовувати алгоритм Диница. Для початку розберемося, як працює алгоритм.

теорема Форда-Фалкерсона випливає, що величина максимального потоку в графі шляхів дорівнює величиною пропускної здатності його мінімального розрізу. Іншими словами, ми можемо знайти мінімальний розріз між двома вершинами (стік і джерело) якщо знайдемо максимальний потік між цими вершинами. Алгоритм Диница як раз дозволяє знайти величину максимального потоку і, власне, сам потік. Я не буду розбирати докладно сам алгоритм і надам вам можливість самим розібратися в ньому. Для розуміння отриманого результату достатньо знати, що потік — це певна функція, яка для кожного ребра лежить на шляху від витоку до стоку, визначає позитивну величину, що не перевищує пропускну здатність цього ребра. Для спрощення можна уявити систему труб з водою, де обсяг води, що протікає від витоку до стоку в момент t є величина потоку.

Поставлена мною завдання злегка відрізняється від тієї, що вирішує алгоритм. Справа в тому, що потік визначається на ребрах, і якщо ми знайдемо мінімальний розріз, то він «розріже» граф по ребрах, тобто зв'язків у графі, але нам потрібно розрізати граф не по ребрах, а вершин, тобто персонажам. Щоб вирішити цю задачу потрібно піддати граф невеликим змінам. Раздвоим кожну вершину в графі, скажімо замість вершини v у нас вийдуть вершини v1 та v2, далі якщо між двома вершинами v та u було ребро, то перенаправимо v1 u2, u1 v2, замість ребра (u, v) вийдуть ребра (v1, u2) та (u1, v2). І між кожними роздвоєними вершинами v1 та v2 проведемо ребро (v2, v1). В отриманому, вже орієнтованому, графі, всі зв'язки збережуться, але там де раніше були вершини, з'являться ребра. Якщо вага цих ребер буде 1, а у всіх інших, скажімо нескінченність (на практиці можна використовувати кількість вершин в графі), то ребро між роздвоєними вершинами буде слабкою ланкою у графі і за принципом «запобіжника» не дозволить пройти більшого потоку через себе, що дасть можливість дізнатися кількість вершин, які потрібно видалити, щоб граф став несвязным. А далі запустимо алгоритм Диница на отриманому графі.

Складність алгоритму O(n2m). Тому ми будемо шукати величину максимального потоку не по всіх пар вершин, а тільки по персонажам, які мають найбільшу кількість зв'язків, інакше для даного графа складність вийде O(n5), де n=1000 і працювати все буде багато годин. Нижче я наведу результати по топ 100 персонажам зв'язків.

Я трохи здивувався результатами. Виявилося, що в топ 100, розрізати граф можна позбувшись мінімум 6ти персонажів. Всі такі зв'язки при цьому містять Джона Коннингтона або Эурона Грейджоя як стоку/витоку. Але це не основні персонажі. Що цікаво, в топ 10, в основному мінімальний потік дорівнює близько 45ти. Наприклад, між Тіріоном і Ар'єю потік дорівнює 53, а між Джоном Сноу і Серсеей 42. Але є і персонаж, якого можна відокремити, видаливши 16 інших персонажів. Це Дайнерис Таргаріен, не дивно, адже вона найбільш віддалена героїня на карті престолів.

Ще цікаво було б дізнатися, хто ж найбільш «важливий» герой в потоках. Тобто через кого найчастіше протікає максимальний потік. Тут є чому здивуватися. Топ 10 важливих персонажів в потоках (в дужках відповідна кількість входжень в потоки):

  1. Тіріон Ланністер (4109)
  2. Джеймі Ланністер (3067)
  3. Арья Старк (3021)
  4. Джон Сноу (2883)
  5. Еддард Старк (2847)
  6. Серсея Ланністер (2745)
  7. Теона Грейджой (2658)
  8. Брієнні (2621)
  9. Сандор Клегане (2579)
  10. Санса Старк (2573)
По-перше, Еддард Старк був важливим персонажем і їх, на жаль (або на щастя) не шкодують. По-друге, Сандор Клегане, від імені якого не написано жодної глави, все ж важливий персонаж. У третіх, топ 10 персонажів вельми живучі, в усякому разі поки, але найцікавіше, що з 10 персонажів, це:

11. Джофрей Ланністер
12. Робб Старк
13. Ренлі Баратеонов
14. Кейтілін Старк
15. Русе Болтон
16. Йорен
17. Сем
18. Мелісандра
19. Бран Старк
20. Варіс

де верхні 6 персонажів вже вбиті. Не позаздриш цій десятці.

Так само, завдяки потокам, вдалося вирахувати «зайві» вершини, авторів реплік яких не вдалося правильно розпізнати, тому вони були пов'язані з багатьма персонажами, з якими не повинні були перетнутися. Ними виявилися Чоловік (A Man) і Страж (A Guard). У слідстві чого, я видалив ці вершини і перерахував всю статистику заново.

Весь результат

Код знаходження мінімального розрізу по вершинам
#include "definitions.h"

const int INF = 1000000000;

struct edge_s{
int a, b, c, flow; // a->b, c-capacity, flow=0
edge_s(int a, int b, int c, int flow) : a(a), b(b), c©, flow(flow) {}
};

vector< pair<int, int> > top_degree;
vector< pair<int, int> > top_flow;
vector<int> dis;
vector<int> ptr;
vector<edge_s> edgelist;
vector < vector < int> > edges_dup;

bool compare_pairs_by_second(const pair<int, int> &i, const pair<int, int> &j)
{
return (i.second > j.second);
}

bool bfs_dinic(int s, int t) {
queue<int> q;
q.push(s);
dis[s] = 0;

while (!q.empty() && dis[t] == -1) {
int v = q.front();
q.pop();

for (int i = 0; i < edges_dup[v].size(); i++) {
int ind = edges_dup[v][i],
next = edgelist[ind].b;

if (dis[next] == -1 && edgelist[ind].flow < edgelist[ind].c) {
q.push(next);
dis[next] = dis[v] + 1;
}
}
}

return dis[t] != -1;
}

int dfs_dinic(int v, int t, int flow) {
if (!flow) {
return 0;
}

if (v == t) {
return flow;
}

for (; ptr[v] < (int) edges_dup[v].size(); ptr[v]++) {
int ind = edges_dup[v][ptr[v]];
int next = edgelist[ind].b;

if (dis[next] != dis[v] + 1) {
continue;
}

int pushed = dfs_dinic(next, t min(flow, edgelist[ind].c - edgelist[ind].flow));

if (pushed) {
edgelist[ind].flow += pushed;
edgelist[ind ^ 1].flow -= pushed;
return pushed;
}
}

return 0;
}

long long dinic_flow(int s, int t) {
long long flow = 0;

while (true) {
fill(dis.begin(), dis.end(), -1);

if (!bfs_dinic(s, t)) {
break;
}

fill(ptr.begin(), ptr.end(), 0);

while (int pushed = dfs_dinic(s, t, INF)) {
flow += pushed;
}
}
return flow;
}

void dinic_addedge(int a, int b, int c) {
edges_dup[a].push_back((int) edgelist.size());
edgelist.push_back(edge_s(a, b, c, 0));
edges_dup[b].push_back((int) edgelist.size());
edgelist.push_back(edge_s(b, a, 0, 0));
}

void find_cut() {
freopen("cut_min.txt", "w", stdout); // output file

dis.resize(2 * V, 0);
ptr.resize(2 * V, 0);
edges_dup.resize(2 * V, vector<int>(0));
const int top = min(10, V);

for (int i = 0; i < V; i++)
top_flow.push_back(make_pair(0, i));

for (int i = 0; i < V; i++) {
top_degree.push_back(make_pair(edge[i].size(), i));
for (int j = 0; j < edge[i].size(); j++) {
int to = edge[i][j];
dinic_addedge(i, to + V, V);
}
dinic_addedge(i + V, i, 1);
}

stable_sort(top_degree.rbegin(), top_degree.rend());

cout << "Minimum cut between characters:" << endl;
for (int i = 0; i < top; i++) {
for (int j = i + 1; j < top; j++) {
vector < int>:: iterator p = find(edge[top_degree[i].second].begin(), edge[top_degree[i].second].end(), top_degree[j].second);

if (p != edge[top_degree[i].second].end())
continue;

int flow = dinic_flow(top_degree[i].second, top_degree[j].second + V);
cout << name[top_degree[i].second] << " -> " << name[top_degree[j].second] << " = " << flow << endl; 

for (int k = 0; k < edgelist.size(); k++) {
if ((edgelist[k].a == (edgelist[k].b + V)) && (edgelist[k].flow == 1)) {
top_flow[edgelist[k].b].first++;
}
edgelist[k].flow = 0;
}
}
}

stable_sort(top_flow.rbegin(), top_flow.rend());

cout << endl << "Top involved characters in the flows:" << endl;
for (int i = 0; i < top; i++) {
cout << name[top_flow[i].second] << " (" << top_flow[i].first << ")" << endl;
}
}


На цьому все. Насамкінець можна зазначити, що Тіріон Ланністер дуже важливий персонаж у світі престолів. Сподіваюся, стаття виявилася для вас цікавою, а можливо і корисною. Вихідний код всіх алгоритмів є так само і на GitHub, посилання нижче.

Посилання:

Проект на GitHub
Вихідний соціальний граф
Програма Gephi, за допомогою якого можна відкрити проект
Автор фото заголовка Adam Foster

В кінці, як і обіцяв, опитувач: чи варто перекладати статью про те, як були визначені автори діалогів у книгах?

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.