Student 1: Tatiana_Gan

Student 2: pacost

Student 3: KiV

Роль student 2 выполняла в репозитории KiV

Система анализа графов городов

1. Назначение системы

Система реализована как консольное приложение на C#. Она предназначена для работы с графом городов и маршрутов, включая следующие функции:

• Обход графа в ширину (BFS) и глубину (DFS)
• Поиск компонент связности (рекурсивно)
• Вычисление кратчайшего пути между городами по количеству рёбер
• Обнаружение циклов в графе
• Вывод статистики графа: количество вершин, рёбер, максимальная и средняя степень, связность
• Поддержка добавления и удаления городов и маршрутов
• Загрузка и сохранение данных в CSV

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

GraphAnalysisSystem/ ├── GraphAnalysisSystem.csproj # Проект C# (.NET 6.0+) ├── Program.cs # Основной класс запуска приложения ├── GraphClasses/ # Классы модели графа │ ├── CityNode.cs # Класс для хранения информации о городе │ ├── RouteEdge.cs # Класс для хранения информации о маршруте │ ├── Graph.cs # Основной класс графа с методами работы │ └── GraphStats.cs # Класс для статистики графа ├── CommandProcessor.cs # Класс обработки команд пользователя ├── demo/ # Папка с демонстрационными данными │ ├── sample_data/ │ │ ├── airports.csv │ │ └── routes.csv │ ├── test_commands/ │ │ ├── test_bfs.txt │ │ ├── test_dfs.txt │ │ ├── test_components.txt │ │ ├── test_path.txt │ │ ├── test_detect_cycles.txt │ │ └── test_stats.txt │ ├── screenshots/ # Скриншоты работы системы │ └── reports/ │ └── demo_report.md # Отчет по демонстрации └── README.md # Инструкции по использованию системы

3. Описание кода

3.1 Классы

1. CityNode

   • Свойства:
     Id
     ,
     Name
     ,
     Latitude
     ,
     Longitude
   • Представляет город как вершину графа

2. RouteEdge

   • Свойства:
     City1
     ,
     City2
     ,
     Distance
   • Методы:
     • Connects(string cityId)
       – проверяет, связано ли ребро с указанным городом
     • GetOtherCity(string cityId)
       – возвращает другую вершину ребра

3. GraphStats

   • Свойства: количество вершин и рёбер, компонент связности, наличие циклов, максимальная и средняя степень, связность
   • Переопределен
     ToString()
     для удобного вывода в консоль

4. Graph

   • Основной класс графа
   • Методы:
     • AddNode
       ,
       RemoveNode
       – добавление и удаление городов
     • AddEdge
       ,
       RemoveEdge
       – добавление и удаление маршрутов
     • BFS
       ,
       DFS
       – обход графа
     • FindConnectedComponents
       – рекурсивный поиск компонент связности
     • FindShortestPath
       – кратчайший путь по числу рёбер
     • DetectCycle
       – проверка на наличие циклов
     • GetStats
       – сбор статистики графа
     • ToAdjacencyString
       – текстовая визуализация графа
     • LoadFromCsv
       ,
       SaveToCsv
       – загрузка и сохранение данных

5. CommandProcessor

   • Обрабатывает команды пользователя и вызывает методы графа
   • Поддерживает команды:
     add city
     ,
     remove city
     ,
     connect
     ,
     disconnect
     ,
     bfs
     ,
     dfs
     ,
     components
     ,
     path
     ,
     detect-cycles
     ,
     stats
     ,
     load
     ,
     save
     ,
     list
     ,
     help
     ,
     exit
   • Обрабатывает ошибки и некорректный ввод

6. Program

   • Точка входа в приложение
   • Инициализирует
     CommandProcessor
     и тестовые данные
   • Запускает цикл чтения команд из консоли

4. Данные

• Источник: OpenFlights Data Set
• Формат CSV:
  • airports.csv:
    id,name,latitude,longitude
  • routes.csv:
    source,target,distance
• Для демо используется упрощенный граф из 7 городов и 6 маршрутов

5. Основные алгоритмы

• BFS – обход в ширину
• DFS – обход в глубину (стековая и рекурсивная реализация для компонентов)
• Поиск компонент связности – рекурсивно через DFS
• Кратчайший путь – BFS по количеству рёбер
• Обнаружение циклов – DFS с отслеживанием родителя
• Статистика графа – подсчет вершин, рёбер, компонентов, степени

6. Особенности реализации

• Объектно-ориентированный подход (ООП)
• Используются только стандартные структуры .NET:
  Dictionary
  ,
  List
  ,
  HashSet
  ,
  Queue
  ,
  Stack
• Все команды обрабатываются через консоль
• Обработка ошибок и некорректного ввода встроена

8. Запуск приложения

Открыть проект в Visual Studio или другой IDE с поддержкой C# и .NET 6.0+

Построить проект (Build)

Запустить Program.cs

Вводить команды в консоль, например help для списка команд