Skip to content

README.md

Latest commit

 

History

History
291 lines (207 loc) · 9.14 KB

README.md

File metadata and controls

291 lines (207 loc) · 9.14 KB

VKGraph

Go VK API Graph Algorithms Gorilla Mux

Go-сервис для поиска кратчайшей цепочки знакомств между двумя пользователями VK через граф друзей и двусторонний BFS.

VK API · Алгоритм · API · Быстрый-старт

О проекте

VKGraph — небольшой backend-проект на Go, который работает с социальным графом VK.

Пользователь вводит два VK ID, сервис получает списки друзей через VK API и ищет кратчайший путь между людьми: кто через кого связан. По сути, это мини-версия идеи «теории шести рукопожатий», но поверх реального графа друзей.

Проект, на мой взгляд, интересен тем, что здесь есть не просто CRUD или работа с API, а реальная алгоритмическая задача: обход графа с внешними API-вызовами, восстановление пути и отдача результата через HTTP.

Что реализовано

  • подключение к VK API через access token;
  • получение списка друзей пользователя;
  • получение информации о пользователях: имя, ссылка, аватар, пол;
  • поиск кратчайшего пути между двумя пользователями VK;
  • двусторонний BFS для ускорения поиска;
  • восстановление найденного пути;
  • HTTP API на Go;
  • простой web-интерфейс для ввода двух ID;
  • базовые тесты для графовой логики и VK client слоя.

Как это работает

VK ID A + VK ID B
        ↓
Backend получает друзей A и B через VK API
        ↓
Запускается bidirectional BFS
        ↓
Поиск идет одновременно от A и от B
        ↓
Когда фронты поиска пересекаются — путь найден
        ↓
Backend восстанавливает цепочку пользователей
        ↓
Frontend показывает кратчайший путь

Архитектура

flowchart TD
    A["Web UI"] --> B["Go HTTP Server"]
    B --> C["gorilla/mux router"]

    C --> D["/friends/{userID}"]
    C --> E["/friends/{userIDa}/{userIDb}"]
    C --> F["/friends/info/{userIDa}/{userIDb}"]

    D --> G["VK client"]
    E --> H["Bidirectional BFS"]
    F --> H

    H --> G
    G --> I["VK API"]

    H --> J["Shortest path: IDs"]
    F --> K["User details"]
    K --> L["JSON response"]
Loading

Алгоритм

Обычный BFS от одного пользователя может быстро стать тяжелым: социальный граф широкий, у каждого пользователя могут быть сотни друзей, а каждый шаг требует внешних API-вызовов.

Поэтому используется двусторонний BFS:

start user → → →
               встреча
end user   ← ← ←

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

В проекте это вынесено в отдельную графовую логику:

  • bidirectionalSearch — основной поиск;
  • bfsStep — один шаг BFS;
  • mergePaths — склейка двух половин пути;
  • backtrace — восстановление маршрута по map предыдущих вершин.

API

Получить друзей пользователя

GET /friends/{userID}

Возвращает список друзей пользователя с базовой информацией.

Найти кратчайший путь между двумя пользователями

GET /friends/{userIDa}/{userIDb}

Возвращает путь как список VK ID.

Найти путь с деталями пользователей

GET /friends/info/{userIDa}/{userIDb}

Возвращает путь с именами, аватарами и ссылками на профили.

Пример ответа:

[
  {
    "id": 1,
    "name": "User A",
    "source": "https://vk.com/id1",
    "photo": "https://...",
    "sex": 2
  },
  {
    "id": 2,
    "name": "Mutual Friend",
    "source": "https://vk.com/id2",
    "photo": "https://...",
    "sex": 1
  },
  {
    "id": 3,
    "name": "User B",
    "source": "https://vk.com/id3",
    "photo": "https://...",
    "sex": 1
  }
]

Стек

Область Технологии
Язык Go 1.22
HTTP router gorilla/mux
VK integration SevereCloud/vksdk
Config godotenv, .env
Algorithm bidirectional BFS
Frontend HTML, CSS, JavaScript

Структура проекта

.
├── main.go              # запуск сервера, маршруты, static files
├── go.mod               # Go module и зависимости
├── src/
│   ├── graph.go         # bidirectional BFS и восстановление пути
│   ├── handlers.go      # HTTP handlers
│   ├── models.go        # модели ответа
│   ├── vk_client.go     # работа с VK API
│   ├── graph_test.go    # тесты графовой логики
│   └── vk_client_test.go
└── static/
    ├── index.html       # web-форма
    ├── script.js        # запросы к backend
    └── style.css

Быстрый старт

1. Клонировать репозиторий

git clone https://github.com/Optoed/VKGraph.git
cd VKGraph

Сейчас основной код находится в ветке visual. Если GitHub открывает не ее, переключись:

git checkout visual

2. Создать .env

ACCESS_TOKEN=your_vk_access_token_here

Токен нужен для запросов к VK API.

3. Установить зависимости

go mod download

4. Запустить сервер

go run main.go

Сервер запускается на:

http://localhost:8081

Пример использования

Через браузер:

http://localhost:8081

Через HTTP API:

curl http://localhost:8081/friends/info/USER_ID_A/USER_ID_B

Где USER_ID_A и USER_ID_B — числовые VK ID пользователей.

Важные ограничения

  • VK API может ограничивать количество запросов;
  • закрытые профили и приватные списки друзей могут ломать полноту графа;
  • поиск по большому социальному графу может быть медленным без кэша;
  • проект рассчитан на исследование графовой логики и интеграции с VK API, а не на production-нагрузку.

Что можно улучшить дальше

  • добавить кэширование друзей, чтобы не дергать VK API повторно;
  • добавить лимит глубины поиска;
  • добавить rate limiting и обработку ошибок VK API;
  • визуализировать путь как граф, а не только как список;
  • добавить Dockerfile;
  • добавить Swagger/OpenAPI;
  • улучшить frontend: карточки пользователей, аватары, ссылки, loader;
  • добавить хранение уже найденных путей.

Авторство

Проект создан как развлекательная практическая работа с Go, VK API и алгоритмами на графах.

Лицензия

MIT License.