Сборка

make

Собираются два бинарника:

• bin/pagerank — основной пайплайн (CSV → бинарный кэш → PageRank → CSV)
• bin/gen_synthetic_graph — генератор синтетических графов для нагрузочного тестирования (см. ниже)

Запуск на своих данных

Формат входных данных полностью соответствует заданию: CSV с заголовком from,to, далее по одному ориентированному ребру на строку, id вершин — int32.

bin/pagerank --input edges.csv --output ranks.csv

На выходе: ranks.csv с заголовком vertex,rank, по одной строке на каждый id вершины в диапазоне [0, max_id_seen], суммарно ранги дают 1.

Полезные флаги (все опциональны):

--cache PATH     путь к бинарному кэшу рёбер (по умолчанию: <input>.bin)
--damping D      коэффициент затухания, по умолчанию 0.85
--epsilon E      порог сходимости по L1-норме, по умолчанию 1e-8
--max-iters N    ограничение числа итераций, по умолчанию 100
--threads N      число рабочих потоков, по умолчанию = hardware_concurrency()
--quiet          не выводить прогресс по итерациям в stderr

При первом запуске на конкретном CSV строится бинарный кэш <input>.bin (прямое преобразование CSV в 8-байтные записи, подробнее в REPORT.md). Последующие запуски на том же входном файле автоматически переиспользуют этот кэш (проверка по mtime) — это важно, если нужно перебрать несколько значений --damping/--epsilon, не перепарсивая многогигабайтный CSV каждый раз заново.

Быстрая проверка

make test

Запускает пайплайн на data/edges_example.csv — том самом примере из 4 рёбер, что приведён в тексте задания.

Нагрузочное тестирование на больших графах (без доступа к сети)

В задании предлагается использовать датасеты SNAP или LDBC; утилита tools/gen_synthetic_graph — это замена для окружений без доступа к сети для их скачивания. Она пишет синтетический CSV прямо на диск потоково (никогда не держа его целиком в памяти), с настраиваемым распределением out-degree с тяжёлым хвостом и настраиваемым числом явных гипер-узлов — то есть именно тем adversarial-случаем, что описан в задании:

bin/gen_synthetic_graph \
  --vertices 2000000 --avg-degree 60 \
  --hypernodes 3 --hypernode-degree 300000 \
  --seed 42 --output large.csv

bin/pagerank --input large.csv --output large_ranks.csv --threads 4

--seed по умолчанию фиксирован (42), поэтому сгенерированный граф — а значит, и все результаты ниже по пайплайну — полностью воспроизводимы.

Если хочется использовать реальный датасет, подойдёт любой edge-list из SNAP после удаления строк-комментариев и добавления заголовка from,to (либо можно просто передать --cache и позволить build_graph_and_degrees самой пропустить некорректный/отсутствующий заголовок — она уже это умеет, см. graph_io.cpp).

Структура репозитория

src/                    основная библиотека + CLI
tools/                  генератор синтетических графов
data/edges_example.csv  пример из 4 рёбер прямо из текста задания
scripts/run_example.sh  скрипт на собрать + запустить + проверить
Makefile
REPORT.md               анализ: выбор метрики, результаты, ограничения