CodeStars. Track 04. Математика

Задача.
Чтобы узнать, сколько комментариев у тебя будет на GitHub, реши следующую задачу:На международном музыкальном фестивале участники говорят на множестве разных языков. Чтобы все могли понимать друг друга, организаторы предложили использовать автоматические переводчики, но переводчики есть не для всех пар языков. В текстовом файле в каждой строке содержится (через пробел) имя переводчика, с какого языка и на какой он может переводить. Какое минимальное количество переводчиков необходимо, чтобы переводить с Исландского на Албанский?

Предисловие.
Ох лол... у меня не будет комментариев на GitHub, потому что у меня нет аккаунта на GitHub. Но задача есть задача. Классическая задача на графы, каждый язык - вершина графа, а переводчик - ребро графа, связывающее языки. И надо найти кратчайший путь в графе. Структура данных проста: есть язык, точки входа и точки выхода. Алгоритм известен... что означает, мы с легкостью можем его загуглить, например здесь (Задача о кратчайшем пути в Википедии). Наученная прошлым опытом и вооруженная ленью, я предполагаю, что библиотеки работы с графами для C# уже есть. Есть три аспекта работы с графами: создание структуры данных, алгоритмы и отображение. Почти все библиотеки поддерживают создание структур и их отображение. Различия в основном лежат в алгоритмах визуализации, различных параметрах визуализации, механизмах выгрузки картинок (например в pdf), способа ввода данных и возможностях автоматической генерации графа. А вот математические алгоритмы реализует только QuickGraph. Может быть и не только он.. но остальных мне найти не удалось. )) 

1. Microsoft Automatic Graph Layout (MSAGL) она же Glee - собственно была библиотека Glee, теперь она же перекуплена MS, доработана и называется страшной аббревиатурой MSAGL. Также иногда в инетиках именуется Microsoft Glee. Что не совсем корректно, по ссылке есть раздел отличий.
2. Graphviz но в нем мне не устанавливая разобраться не удалось. Хотя в этом формате вот здесь есть пример: QuickGraph + Graphiz  . Если верить документации на сайте очень развитые варианты  вывода и настроек отображения.
3. Graph# - по факту WPF контроллер для отображения графов. Содержит несколько алгоритмов визуализации. 
4. NodeXL - вроде работает только с графами заданными через Excel.
5. QuickGraph - библиотека обеспечивающая мат. алгоритмы работы с графами. А также позволяет выводить графы через Glee, Graphiz. 

Решение.

Сначала разберемся с математикой. 

1. Добавляем QuickGraph в ссылки и включаем использование:
   
   using QuickGraph;
   using QuickGraph.Algorithms.ShortestPath;
   
2. Создаем граф. Так как переводчик единица универсальная - в том смысле, что, вообще говоря, переводить может в обоих направлениях, то создаем ненаправленный граф.
   
    UndirectedGraph<string, Edge<string>> languageGraph = null;
   
3. Пишем метод, для заполнения этого графа из файла. Предположим FillGraph();
4. Думаем над тем, какой нам нужен алгоритм. Мне нравится Дейкстра. Это ничем не обосновано, на самом деле.
   
   var a = new UndirectedDijkstraShortestPathAlgorithm<string, Edge<string>>(languageGraph, edgeCost);
   
5. Используем алгоритм:
   -  Назначаем ключевую вершину:
   
    a.SetRootVertex("Исландский");
   
   - Делаем расчет алгоритма: a.Compute(); Это по факту запускает алгоритм с заданным графом и настройками.
   - Получаем искомое: 
   
   if (a.TryGetDistance("Албанский", out path_length))               MessageBox.Show(path_length.ToString());
   else     
      MessageBox.Show("Что-то не так.");
   
6. Получаем правильный ответ. 

Визуализация  : to be continued.