Graph Analysis System - README

Аккаунты участников:

1. ylyastar
   (Я выполняла роль Student 2 у этого участника команды)
2. yanasim
3. anastasiakoc

🎯 Описание процесса работы

Этапы разработки:

В качестве моделей использовались

1. Сборка команды
   Объединились три разработчика с распределением ролей согласно требованиям проекта.

2. Распределение ролей
   Каждому участнику была назначена стартовая позиция (Student 1, 2, 3) с четким определением зон ответственности.

3. Следование инструкциям
   Работа выполнялась строго по предоставленной спецификации из файла

   spec/codex.md
   , соблюдая все требования и ограничения.

4 Выбор инструментов разработки

Для разработки проекта Graph Analysis System были выбраны ChatGPT (GPT-4) и Cursor IDE, которые предоставили комплексный набор возможностей для эффективной разработки:

🤖 ChatGPT (GPT-4)

Основные возможности:

• Генерация архитектурных решений и дизайн-паттернов
  Помогал проектировать структуру классов, интерфейсы и взаимодействие между компонентами системы

• Помощь в написании сложных алгоритмов
  Участвовал в реализации графовых алгоритмов: DFS, BFS, поиск кратчайших путей, обнаружение циклов

• Проверка логики и выявление потенциальных проблем
  Анализировал код на предмет логических ошибок, потенциальных багов и edge cases

• Объяснение концепций и лучших практик
  Разъяснял сложные концепции графовой теории и принципы разработки на C#

• Анализ требований спецификации
  Помогал интерпретировать требования из

  spec/codex.md
  и преобразовывать их в технические решения

💻 Cursor IDE

Ключевые возможности:

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

• Совместная работа над кодом
  Встроенный AI ассистент для парного программирования (pair programming)

• Обсуждение архитектурных решений
  Прямо в редакторе с инлайн-комментариями и обсуждениями рядом с кодом

• Проведение код-ревью
  Автоматический анализ кода и предложения по улучшению качества, стиля и производительности

• Рефакторинг в реальном времени
  Умные подсказки и автоматические исправления кода по мере написания

• Навигация по коду
  Понимание контекста и семантики для быстрого перемещения между связанными частями проекта

• Генерация тестов
  Создание unit-тестов на основе существующей реализации кода

🔄 Интеграция инструментов

Синергия подходов:

1. Использование ChatGPT для стратегического планирования

   • Архитектурное проектирование высокого уровня
   • Алгоритмические решения и выбор подходов
   • Анализ требований и создание плана разработки

2. Применение Cursor для непосредственной реализации

   • Написание и редактирование кода
   • Локальный рефакторинг и оптимизация
   • Непосредственная разработка с AI-помощником

3. Перемещение контекста между инструментами

   • Экспорт архитектурных решений в Cursor для реализации
   • Импорт конкретных проблем кода в ChatGPT для анализа
   • Циклический процесс улучшения: проектирование → реализация → анализ

Рабочий процесс:

[Спецификация] → [ChatGPT: Анализ] → [Архитектура] → [Cursor: Реализация] → [Код] → [ChatGPT: Проверка] → [Улучшения]

Преимущества комбинации:

• ChatGPT обеспечивает глубину анализа и стратегическое мышление
• Cursor предоставляет точность реализации и локальный контекст
• Вместе они создают полноценный цикл разработки от концепции до готового кода

Такой подход позволил достичь высокого качества кода при сохранении соответствия всем требованиям спецификации и эффективного использования времени разработки.

5. Цикличная ротация ролей
   В процессе разработки участники менялись ролями, что позволило:

   • Каждому поработать над разными аспектами проекта
   • Получить разнообразный опыт
   • Обеспечить более качественный код через разные подходы

6. Процесс исправления ошибок
   При обнаружении проблем:

   • Создавались запросы на слияние (pull requests)
   • Проводились обсуждения в комментариях
   • Реализовывались исправления после согласования
   • Тестировались изменения перед слиянием

📁 Описание репозитория

Структура каталогов и файлов:

Каталоги:

1. .gitverse/
   Содержит служебные файлы для управления проектом и автоматического тестирования.

2. demo/
   Демонстрационные материалы:

   • spec_compliance.md, test_scenarios.md
     - примеры работы программы
   • test_output.txt - подтверждение использования спецификации

3. dev/
   Исходный код приложения:

   • solution.cs
     - основная реализация на C#

4. spec/
   Спецификация проекта:

   • codex.md
     - техническое задание и требования

5. tasks/
   Файлы с заданиями и задачами проекта

Файлы в корне:

1. CONTRIBUTING.md - инструкция по участию в проекте
2. README.md - этот файл с описанием проекта

Выводы о структуре:

• Организация по функциональности: Четкое разделение на разработку (dev), демонстрацию (demo), спецификации (spec) и задачи (tasks)
• Система контроля версий: Использование Git с автоматическим тестированием через .gitverse
• Полнота проекта: Включает как исходный код (C#), так и полную документацию
• Руководство для разработчиков: Наличие CONTRIBUTING.md для новых участников
• Демонстрационные материалы: Примеры работы программы в папке demo

💻 Описание кода программы

Архитектура программы

Программа представляет собой консольное приложение на C# для анализа графов городов и маршрутов. Реализована с использованием объектно-ориентированного подхода.

Основные классы:

1. Класс

GraphStats

Вспомогательный класс для хранения статистики графа:

2. Класс

Graph

- Основной класс графа

Назначение:

Управляет структурой графа, реализует все алгоритмы работы с графом.

Структура данных:

Ключевые методы:

Операции с вершинами и рёбрами:

• AddCity(string name)
  - добавление города с валидацией
• RemoveCity(string name)
  - удаление города со всеми связанными рёбрами
• AddEdge(string city1, string city2)
  - создание связи между городами
• RemoveEdge(string city1, string city2)
  - удаление связи

Алгоритмы обхода:

• DFS(string startCity)
  - рекурсивный глубинный поиск
• BFS(string startCity)
  - поиск в ширину с использованием очереди

Анализ графа:

• FindConnectedComponents()
  - поиск компонент связности (рекурсивно)
• FindShortestPath(string from, string to)
  - поиск кратчайшего пути (BFS-based)
• DetectCycle()
  - обнаружение циклов с использованием DFS
• GetStats()
  - получение статистики графа

Вспомогательные методы:

• PrintAdjacency()
  - вывод списка смежности
• QuickSort()
  - ручная реализация быстрой сортировки (вместо LINQ)

3. Класс

Program

- Пользовательский интерфейс

Назначение:

Точка входа в программу, обработчик команд пользователя.

Основные функции:

• Чтение и парсинг команд из консоли
• Вызов соответствующих методов класса Graph
• Отображение результатов в понятном формате
• Обработка ошибок ввода

Поддерживаемые команды:

add city <name>          - Добавить город
remove city <name>       - Удалить город
connect <city1> <city2>  - Соединить города
remove-edge <city1> <city2> - Удалить связь
path <city1> <city2>     - Найти кратчайший путь
components               - Показать компоненты связности
cycle-check              - Проверить наличие циклов
stats                    - Показать статистику
show                     - Отобразить граф
help                     - Показать справку
exit                     - Выйти из программы

Алгоритмические особенности:

1. Рекурсивные алгоритмы с защитой

Все рекурсивные методы содержат проверку глубины:

2. Поиск кратчайшего пути

Используется алгоритм BFS с восстановлением пути:

• Обход в ширину от начальной вершины
• Запись родительских вершин
• Восстановление пути от конечной к начальной вершине

3. Обнаружение циклов

Алгоритм на основе DFS с проверкой обратных рёбер:

• Отслеживание вершин в текущем пути рекурсии
• Обнаружение рёбер к уже посещённым вершинам (кроме родительской)

4. Ручная сортировка

Для соответствия требованиям спецификации реализована быстрая сортировка:

• Алгоритм QuickSort для сортировки городов и соседей
• Разделение Ломуто (Lomuto partition scheme)
• Рекурсивная реализация

Технические характеристики:

Производительность:

• Сложность алгоритмов: O(V + E) для большинства операций
• Поддерживаемый размер: до 200 вершин (по спецификации)
• Время выполнения: < 1 секунды для всех операций

Ограничения по библиотекам:

• Используется только
  System
  и
  System.Collections.Generic
• Запрещены внешние NuGet пакеты
• Не используются графовые библиотеки
• LINQ не используется (все алгоритмы реализованы вручную)

Обработка ошибок и валидация:

1. Проверка существования городов:

   • При операциях с несуществующими городами выводятся понятные сообщения об ошибках

2. Валидация входных данных:

   • Проверка пустых имён городов
   • Проверка дублирования городов
   • Валидация рёбер (город не может быть соединён сам с собой)

3. Обработка граничных случаев:

   • Пустой граф
   • Отсутствие пути между городами
   • Граф из одной вершины
   • Циклы вида A-A

4. Защита от исключений:

   • Все публичные методы обёрнуты в try-catch блоки
   • Использование безопасных операций с коллекциями

Пример работы программы:

=== Graph Analysis System ===
> add city Moscow
City 'Moscow' added successfully.

> add city Kazan
City 'Kazan' added successfully.

> connect Moscow Kazan
Edge between 'Moscow' and 'Kazan' added successfully.

> show

=== Graph Adjacency List ===
Kazan: Moscow
Moscow: Kazan

> path Moscow Kazan
Shortest path: Moscow → Kazan

> stats

=== Graph Statistics ===
Nodes: 2
Edges: 1
Connected: yes

Ключевые преимущества реализации:

1. Полное соответствие спецификации: Все требования из
   spec/codex.md
   выполнены
2. Качественный код: После код-ревью добавлена обработка исключений, документация и улучшена надёжность
3. Модульность: Чёткое разделение ответственности между классами
4. Расширяемость: Легко добавлять новые алгоритмы и команды
5. Пользовательский интерфейс: Интуитивно понятные команды с автоподсказками

Тестирование:

Программа включает комплексные тестовые сценарии, проверяющие:

• Все команды из спецификации
• Граничные случаи
• Обработку ошибок
• Производительность

Проект готов к использованию и полностью соответствует всем поставленным требованиям.