Графи в Python: списък от съседи и матрица

Проблем

Таблицата, която не се събира

Куриерска фирма пази уличната мрежа на града в таблица: ред и колона за всяко кръстовище, а в клетката пише 1, ако между двете има улица. Когато фирмата работеше в един квартал с 300 кръстовища, таблицата беше 90 000 клетки и никой не се оплакваше.

После фирмата покри целия град: 40 000 кръстовища. Таблицата стана 40 000 × 40 000 = 1,6 милиарда клетки. Дори по един байт на клетка това са 1,6 GB, а сървърът започна да пада при всяко зареждане на картата.

Най-обидното е, че почти всичко в таблицата е 0. От кръстовище излизат три-четири улици, не 40 000. Как да пазиш само улиците, които ги има?

Идеята

Спирки и улици: граф

Картата на доставките се описва с две неща: спирки (кръстовища, складове, адреси) и улици между тях. Такова нещо се казва граф. Спирките са върховете му (vertex), а улиците са ребрата (edge). Броят върхове се бележи с V, а броят ребра с E.

Ненасочен граф: улицата е двупосочна. Ако има път от Гара до Площад, има и обратно.
Насочен граф: еднопосочните улици. Ребро Гара → Площад не дава път Площад → Гара.
Претеглен граф: всяко ребро носи число: дължина в метри, минути, цена в €.

Ето нашия град: 8 спирки и 9 двупосочни улици. Реката го дели на две части, свързани с два моста. Така идва графът от системата на фирмата: списък със спирките и списък с улиците (по двойка имена на ред).

stops = [
    "Склад", "Гара", "Пазар", "Площад",
    "Парк", "Кино", "Болница", "Стадион",
]
streets = [
    ("Склад", "Гара"), ("Склад", "Пазар"),
    ("Гара", "Площад"), ("Пазар", "Площад"),
    ("Пазар", "Парк"), ("Площад", "Кино"),
    ("Кино", "Болница"), ("Парк", "Стадион"),
    ("Болница", "Стадион"),
]

Същият град ще ни трябва през целия модул: за най-късия път, за островите след затворен мост, после за Dijkstra.

Идеята

Два начина да го пазиш

Матрица на съседство. Номерираш спирките от 0 до V − 1. Таблицата е V × V, а клетката [i][j] казва дали има улица от i до j. Това е таблицата от проблема.

Списък от съседи. За всяка спирка пазиш списък само с нейните съседи. В кода това е речник от име към списък: dict от име към list. Празни места няма: улица, която я няма, не заема нищо.

Двата се строят от един и същ списък с улици, в един и същ цикъл.

Виж го

Една улица, два записа

graph = {stop: [] for stop in stops}
index = {stop: i for i, stop in enumerate(stops)}
matrix = [[False] * len(stops) for _ in stops]
for a, b in streets:
    graph[a].append(b)
    graph[b].append(a)
    i, j = index[a], index[b]
    matrix[i][j] = matrix[j][i] = True

Стъпка по стъпка, с думи

Осем спирки, още без улици. Всяка получава празен списък и номер: реда и колоната си в матрицата 8 × 8, цялата с нули.
Първата улица, Склад – Гара: Гара влиза в списъка на Склад, а Склад в списъка на Гара. В матрицата две клетки стават 1: [0][1] и [1][0].
Склад – Пазар: Пазар застава след Гара в списъка на Склад. Редът в списъка е редът на улиците.
Двупосочната улица се записва два пъти: в двата списъка и в двете клетки. Затова матрицата е симетрична спрямо диагонала.
Пазар – Парк и Площад – Кино минават над реката. Пазар и Площад вече имат по трима съседи, другите по двама.
Последните улици на другия бряг. Всеки списък расте само с истинските си улици.
9 улици: 18 записа в списъците, 64 клетки в матрицата, 46 от тях нули. При 40 000 кръстовища това са около 120 000 записа срещу 1,6 милиарда клетки.

Цялата програма печата списъците и матрицата:

for stop in stops:
    print(stop + ": " + ", ".join(graph[stop]))
for row in matrix:
    print(" ".join("1" if cell else "0" for cell in row))

Склад: Гара, Пазар
Гара: Склад, Площад
Пазар: Склад, Площад, Парк
Площад: Гара, Пазар, Кино
Парк: Пазар, Стадион
Кино: Площад, Болница
Болница: Кино, Стадион
Стадион: Парк, Болница
0 1 1 0 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 1 0 0 0
0 1 1 0 0 1 0 0
0 0 1 0 0 0 0 1
0 0 0 1 0 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 1 0 1 0

Списъкът на всяка спирка е в реда, в който са дошли улиците. Матрицата е симетрична: ред 2 и колона 2 са еднакви, защото всяка улица е двупосочна.

Пробвай

Предвиди изхода

Три улици около Площад, в друг ред. Какво печата програмата?

streets = [
    ("Пазар", "Площад"), ("Площад", "Кино"),
    ("Гара", "Площад"),
]
graph = {stop: [] for stop in stops}
for a, b in streets:
    graph[a].append(b)
    graph[b].append(a)
print(", ".join(graph["Площад"]))

Отговор

Пазар, Кино, Гара

Гара, Пазар, Кино

Гара, Кино, Пазар

Пробвай

Попълни

Двупосочната улица трябва да се запише и в двете клетки:

for a, b in streets:
    i, j = index[a], index[b]
    matrix[i][j] =  = True

Идеята

Колко струва

Трите въпроса, които куриерското приложение задава постоянно, струват различно:

	матрица	списък от съседи
памет	V² клетки	V списъка и 2E записа: O(V + E)
има ли улица между a и b?	една клетка: O(1)	преглед на съседите на a: O(съседи)
кои са съседите на a?	целият ред: O(V)	само съседите: O(съседи)

Програмата обхожда съседите на всяка спирка и по двата начина и брои всяко поглеждане: в матрицата всяка клетка, в списъка всяка спирка и всеки запис.

matrix_looks = matrix_found = 0
for i in range(len(stops)):
    for j in range(len(stops)):
        matrix_looks += 1
        if matrix[i][j]:
            matrix_found += 1
list_looks = list_found = 0
for stop in stops:
    list_looks += 1
    for nxt in graph[stop]:
        list_looks += 1
        list_found += 1
print(f"Матрица: {matrix_looks} поглеждания, {matrix_found} съседи")
print(f"Списък: {list_looks} поглеждания, {list_found} съседи")
in_matrix = matrix[index["Пазар"]][index["Парк"]]
in_list = "Парк" in graph["Пазар"]
print(f"Има ли улица Пазар - Парк? {in_matrix} {in_list}")

Матрица: 64 поглеждания, 18 съседи
Списък: 26 поглеждания, 18 съседи
Има ли улица Пазар - Парк? True True

При 8 спирки разликата е малка. Пусни същото върху град-решетка от n кръстовища, всяко свързано с десния и долния си съсед:

Матрица: целият ред на всяко кръстовище O(n²)
Списък от съседи: само истинските улици O(n)

Алгоритъм	n = 10	n = 1000	n = 5000	n = 100 000
Матрица: целият ред на всяко кръстовище	100	1 000 000	25 000 000	≈ 10 000 000 000
Списък от съседи: само истинските улици	36	4872	24 716	498 734

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

matrix_looks = matrix_found = 0
for i in range(len(stops)):
    for j in range(len(stops)):
        matrix_looks += 1
        if matrix[i][j]:
            matrix_found += 1
list_looks = list_found = 0
for stop in stops:
    list_looks += 1
    for nxt in graph[stop]:
        list_looks += 1
        list_found += 1
print(f"Матрица: {matrix_looks} поглеждания, {matrix_found} съседи")
print(f"Списък: {list_looks} поглеждания, {list_found} съседи")
in_matrix = matrix[index["Пазар"]][index["Парк"]]
in_list = "Парк" in graph["Пазар"]
print(f"Има ли улица Пазар - Парк? {in_matrix} {in_list}")

При 1000 кръстовища матрицата прави 1 000 000 поглеждания, а списъкът 4 872. При 5000 матрицата вече е 25 000 000, списъкът 24 716. Тези числа са и паметта: матрицата държи n² клетки, списъкът толкова записа, колкото поглеждания прави.

Затова картите на градове, социалните мрежи и зависимостите между пакети се пазят като списъци от съседи. Те са редки графи: E е от порядъка на V, не на V².

По-точно, за любопитните

Матрицата печели, когато графът е гъст: почти всеки е свързан с почти всеки, например таблица на разстоянията между 50 склада. Тогава V² клетки не са разхищение, а „има ли ребро“ е една клетка. Има и среден път: списъкът от съседи с множество (set) вместо списък отговаря на „има ли улица“ средно за O(1), с цената на повече памет на запис.

Идеята

Посока и дължина

В истинската система улицата идва с дължина, а някои улици са еднопосочни. Списъкът от съседи пази тогава двойка: накъде и колко метра. Системата ги изпраща като текст, по улица на ред: „от до метри“.

lines = [
    "Склад Гара 400",
    "Склад Пазар 300",
    "Гара Площад 500",
    # …
]
graph = {stop: [] for stop in stops}
for line in lines:
    a, b, meters = line.split()
    graph[a].append((b, int(meters)))
    graph[b].append((a, int(meters)))

Съседът и дължината са кортеж (b, метри). split() разделя реда на три части, а int прави метрите число.

text = ", ".join(f"{to} {meters} м" for to, meters in graph["Пазар"])
print("Пазар" + ": " + text)

Пазар: Склад 300 м, Площад 350 м, Парк 600 м

Еднопосочната улица е само първото добавяне: в списъка на a влиза b, обратното не. В матрицата се пълни само [i][j], и тя спира да е симетрична. В претеглена матрица клетката пази дължината, а липсващата улица е специална стойност, например безкрайност.

Пробвай

Намери грешката

Колега строи списъка от съседи. Програмата печата:

graph = {stop: [] for stop in stops}
for a, b in streets:
    graph[a].append(b)
    graph[b].append(b)

Склад: Гара, Пазар
Гара: Гара, Площад
Пазар: Пазар, Площад, Парк
Площад: Площад, Площад, Кино
Парк: Парк, Стадион
Кино: Кино, Болница
Болница: Болница, Стадион
Стадион: Стадион, Стадион

Гара се оказва съсед сама на себе си, а Склад липсва от списъка ѝ. На кой ред е грешката?

Избери реда с грешката.

По-точно

Как е в другите езици

Капан: [[False] * n] * n прави n препратки към един и същ ред. Смениш ли matrix[0][1], сменя се колона 1 във всеки ред. Затова матрицата се прави с [[False] * n for _ in range(n)].
Всяка клетка на списък е препратка (8 байта), дори когато стойността е False. Матрица 40 000 × 40 000 от списъци е около 12,8 GB само за препратките. За числени таблици има bytearray или масивите на NumPy.
collections.defaultdict(list) създава празния списък сам при първата улица: graph[a].append(b) без предварителния цикъл.

Упражнение

Улици и метри

Реши задачата в редактора си.

Улиците на спирката. Системата изпраща двупосочните улици като редове „от до метри“, а еднопосочните отделно:

lines = [
    "Склад Гара 400",
    "Склад Пазар 300",
    "Гара Площад 500",
    "Пазар Площад 350",
    "Пазар Парк 600",
    "Площад Кино 450",
    "Кино Болница 300",
    "Парк Стадион 500",
    "Болница Стадион 250",
]

one_way = [
    "Гара Пазар 650",
    "Стадион Кино 550",
]

Построй претегления граф: двупосочните в двете посоки, еднопосочните само от първата спирка към втората. За всяка спирка изведи колко улици излизат от нея и колко метра са общо, а накрая спирката с най-много улици (при равенство първата по ред):

Склад: 2 улици, 700 м
Гара: 3 улици, 1550 м
Пазар: 3 улици, 1250 м
Площад: 3 улици, 1300 м
Парк: 2 улици, 1100 м
Кино: 2 улици, 750 м
Болница: 2 улици, 550 м
Стадион: 3 улици, 1300 м
Най-много улици: Гара (3)

Още задачи

Задънени улици. Изведи спирките, от които излиза само една улица.
Матрица с метри. Построй матрица, в която клетката е дължината на улицата или -1, ако улица няма, и я изведи.
Обратна посока. От графа с еднопосочните улици построй обратния: всяко ребро a → b става b → a. Кой ще ти трябва, ако питаш „от кои спирки се стига до Болница“?

Тест

Провери се

1. Градът има 40 000 кръстовища, а от всяко излизат около 3 улици. Колко клетки има матрицата на съседство?120 000: по една за всеки край на улица60 000: по една за всяка улица1,6 милиарда: 40 000 × 40 000

2. Приложението пита „има ли улица между Пазар и Парк?“. Колко струва въпросът?И в двете една стъпкаВ матрицата една клетка, в списъка обхождане на съседите на ПазарВ матрицата целият ред, в списъка една стъпка

3. Улицата Гара → Площад е еднопосочна. Какво има в списъка от съседи?Двете са една в списъка на другаПлощад е в списъка на Гара, но Гара не е в списъка на ПлощадНикоя от двете

4. Кога матрицата е по-добрият избор?Когато графът е гъст и често питаш „има ли ребро между тези два“Винаги, защото е по-бързаКогато градът е голям и рядък

Граф: списък от съседи и матрица

Бисквитки