#35 issue

[baygeldin]

Моей задачей было исследование возможности оптимизации AdjacencyGraph.cs. Критических мест в коде, где производительность бы сильно проседала из-за неоптимального кода, я не нашел. Однако, я выделил несколько методов, где можно было бы сделать технические оптимизации. Это метод RemoveVertice и RemoveEdgeIf, в первом создавалась лишняя коллекция ребер, а во втором вызывался метод, который производил лишнюю проверку на включение ребра в граф. Также, стоит выделить несколько других методов, где также может показаться, что создается лишняя коллекция и это может ввести в заблуждение. Это методы, которые принимают предикаты для удаления ребер/вершин. Дело в том, что если удалять ребра/вершины сразу, как только мы поняли, что они удовлетворяют предикату, то мы нарушаем топологию графа и следующие предикаты могут сработать неправильно, т.к. они могут зависеть от структуры графа.

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

• Случайное остовное дерево распределенное по нормальному закону
• Случайный граф Эрдёша-Реньи
• Случайный граф Уоттса-Строгатца
• Случайный граф Барабаши-Альберта
• Делегат для случайных весов вершин

Также там есть вспомогательные методы для генерации полного графа, кольца с заданной out-degree, и случайная сильно-связная компонента в графе.

Для бенчмарков был создан проект "GraphTasks.Performance". Результаты измерений показали, что реализованные оптимизации не дают прироста в производительности (как в Debug, так и в Release) по сравнению с предыдущими реализациями. В итоге, можно сказать, что существующая реализация AdjacencyGraph.cs является оптимальной.

[gsvgit]

Поправьте генераторы диапазонов и решите merge-конфликты.