Stefanio 8 апр 2022 в 20:30

Властелин структур

15 мин

10K

Программирование*.NET*C#*Математика*Функциональное программирование*

Технотекст 2021

Ранее, в материале "Абстрактная алгебра в действии" я привёл некоторые примеры алгебраического подхода в программировании. Публикацию восприняли относительно хорошо, поэтому в этой заметке продолжится развитие мысли о том, что некоторые задачи, хоть так и не кажется на первый взгляд, на самом деле, могут быть решены алгебраическим способом. Сегодня мы продвинемся дальше в вопросе знакомства с абстрактной алгеброй и посмотрим на новые примеры кода с её применением.

В прошлый раз мы познакомились с такими понятиями как полугруппа и моноид. Как можно догадаться, на этом алгебра не закончилась. Чтобы двигаться дальше, как было понятно из предыдущей заметки, нам надо накидывать ограничения на операцию, определённой над носителем структуры. Но как понять в каком направлении двигаться?

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

Начинаем входить в контекст. Здесь и далее имеем ввиду, что у нас есть структура и некая абстрактная бинарная операция. Имеем пару $(G, \circ)$ , которую обзовём моноидом. Значит, мы можем взять из любые и , сделать $a \circ b$ и получить некоторое $c \in G$ . Хорошо. А что если перед нами взяли и поставили такой вопрос?

$a \circ x = b \\ a, x, b \in G \\ x = \; ?$

А мы не можем на него ответить. Просто потому что в моноиде нет инструментов для решения такой задачи. Ну, то есть, мы можем сказать, что $x = a^{-1} \circ b$ , где $a^{-1}$ называется обратным для элементом, а сам - обратимый. Или, по-научному, называется обратимым элементом, если:

$\exists \; h = a^{-1}: a \circ h = h \circ a = e$

Но мы не можем гарантировать обратимость каждого элемента моноида. Хотя, есть вариант выкрутиться из этой ситуации...

Группа

Очевидно, что не все элементы моноида обратимы. И также очевидно, что моноид может содержать такие элементы, а они в свою очередь образуют некое подмножество. Это подмножество называется "группа". Группа это моноид, в котором для каждого элемента найдётся обратный. Это и есть следующее ограничение, уже третья по счёту аксиома.

$\forall \; g \in G \; \exists \; h=g^{-1} \in G: g \circ h = h \circ g = e$

public interface IGroup<T> : IMonoid<T>
{
    T Inverse(T item);
}

И теперь наше уравнение $a \circ x = b$ , будучи помещённым в группу, всегда имеет решение.

Чем интересны группы? Как вы уже могли догадаться тем, что для каждого объекта, неважно какой он природы, всегда найдётся его антипод. Его обратный объект. Его реверс. Его симметрия. Кстати, вы часто могли слышать, что теория групп - это наука о симметриях.

Кстати, забавно, но существует так называемая симметрическая группа . Это группа, которая содержит все биекции, с помощью которых можно поменять местами элементы множества размера . Самый легко читаемый способ представления элемента симметрической группы - это две строки чисел. Верхняя - числа , а снизу - на какое место они встают. Например, возьмём произвольный элемент $\phi \in S_3$ :

$\phi = \begin{pmatrix} 1 & 2& 3 \\ 2&3&1 \end{pmatrix}$

Это значит, что первый элемент встанет на второе место, второй на третье и третий на первое. Операция (композиция) определятся очень просто - $(\phi \circ \pi) (i) = \pi (\phi(i))$ . Обратный элемент тоже находится просто: достаточно поменять местами строки и переупорядочить - $\phi(i) = j \implies \phi^{-1}(j) =i$ .

Permutation.cs

public class Permutation : IEquatable<Permutation>
{
    private readonly int[] _map;

    public Permutation(params int[] map)
    {
        _map = new int[map.Length];
        for (var i = 0; i < map.Length; i++)
        {
            _map[i] = map[i];
        }
    }

    public int this[int index] => _map[index];

    public bool Equals(Permutation other)
    {
        if (other != null && _map.Length == other._map.Length)
        {
            return _map.Zip(other._map)
                .All(pair => pair.First == pair.Second);
        }

        return false;
    }

    public override string ToString() =>
        new StringBuilder()
            .AppendJoin(' ', Enumerable.Range(1, _map.Length))
            .Append('\n')
            .AppendJoin(' ', _map.Select(x => x + 1))
            .ToString();
}

SymmetricGroup.cs

public readonly struct SymmetricGroup : IGroup<Permutation>
{
    private readonly int _length;

    public SymmetricGroup(int length)
    {
        _length = length;
    }

    public Permutation Plus(Permutation left, Permutation right)
    {
        var newMap = new int[_length];
        for (var i = 0; i < _length; i++)
        {
            newMap[i] = right[left[i]];
        }

        return new Permutation(newMap);
    }

    public Permutation Zero =>
        new(Enumerable.Range(0, _length).ToArray());

    public Permutation Inverse(Permutation item)
    {
        var newMap = new int[_length];
        for (var i = 0; i < _length; i++)
        {
            newMap[item[i]] = i;
        }

        return new Permutation(newMap);
    }
}

Также, чтобы наше уравнение могло иметь решение $x = b \circ a^{-1}$ , операция $\circ$ должна обладать свойством коммутативности (то самое "от перемены мест слагаемых сумма не меняется"). И оказывается, что достаточно широкий класс групп можно сузить до коммутативных, так называемых абелевых групп. Абелева группа это группа, в которой:

$\forall \; g, h \in G : g \circ h = h \circ g$

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

Допустим, мы хотим сделать некий каталог. Такую сущность, где можно было бы добавлять/удалять элементы, а хранение организовано по принципу append-only базы данных. То есть по сути мы можем только записывать информацию о неких изменениях. О событиях, произошедших в каталоге.

public record CatalogueEvent<T>;

public record Add<T>(T Data) : CatalogueEvent<T>;

public record Remove<T>(T Data) : CatalogueEvent<T>;

public record Nothing<T> : CatalogueEvent<T>;

При этом к самому каталогу есть требование, чтобы по элементам можно было пройтись и получить некий агрегат. Понятно, что при агрегации элементы каталога будут отображаться в некий элемент моноида, чтобы их можно было агрегировать. При чём здесь группы?

В поставленной задаче прослеживается некий сюжет о симметрии. То есть, мы можем добавлять, а можем и удалять. При этом эти действия противоположны друг другу. И при преобразовании события в некий агрегирующий элемент мы можем гарантировать сохранение этой концепции с помощью группы.

public class Catalogue<T> : IEnumerable<CatalogueEvent<T>>
{
    private readonly List<CatalogueEvent<T>> _catalogueEvents = new();

    public S Reduce<S, G>(Func<T, S> map, G group = default)
        where G : struct, IGroup<S>
        => _catalogueEvents.Select(t =>
            t switch
            {
                Add<T> add => map(add.Data),
                Remove<T> rm => group.Inverse(map(rm.Data)),
                Nothing<T> => group.Zero,
                _ => default
            }
        ).Sum<S, G>();

    public Catalogue<T> Add(T item)
    {
        _catalogueEvents.Add(new Add<T>(item));
        return this;
    }

    public Catalogue<T> Remove(T item)
    {
        _catalogueEvents.Add(new Remove<T>(item));
        return this;
    }

    public Catalogue<T> Nothing()
    {
        _catalogueEvents.Add(new Nothing<T>());
        return this;
    }

    public IEnumerator<CatalogueEvent<T>> GetEnumerator() =>
        _catalogueEvents.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() =>
        GetEnumerator();
}

Собственно в методе Reduce и происходит то, что было описано. Чтобы гарантировать агрегацию, мы говорим: map происходит в некий моноид, и сама агрегация проводится через расширение Sum, известное по прошлой статье. А затем сужаем моноид до группы чтобы Remove событиям сопоставлять "реверс" объекта.

Пощупаем наш каталог.

var stringsCatalogue = new Catalogue<string>()
    .Add("abc")
    .Nothing()
    .Remove("c")
    .Remove("a")
    .Add("ed");

IntAddGroup.cs

private struct IntAddGroup : IGroup<int>
{
    public int Plus(int left, int right) => left + right;

    public int Zero => 0;

    public int Inverse(int item) => -item;
}

В самом каталоге мы как-то манипулировали со строками. Получим например длину строки после манипуляций

stringsCatalogue.Reduce<int, IntAddGroup>(s => s.Length); // 3

Согласен, пока потребность в каталоге не очень мотивирована, но зато отчётливо видно, что оно работает. Ок, а что если мы захотим например на основе этих записей собрать строку, которая получится в результате таких операций? Да, у строк есть конкатенация, но с ней получается только моноид. Трудно придумать так называемый "минус" для строк. Конечно, интуитивно мы представляем себе что-то вроде:

"abc" - "c" == "ab"

Но вот что делать, если попался кейс "abc" - "d", или "" - "", или "" - "xyz"? Ответа на вопрос в таких условиях не существует, но, как это обычно бывает выход есть всегда.

У многих к этому моменту могла возникнуть идея раскручивать историю о множествах. Мы знаем, что string это IEnumerable<char>, и получается начать отталкиваться от проведения аналогии с множествами, и раскрутить её до коллекции.

Однако, множества с операцией объединения образуют лишь коммутативный моноид ~~(оставлю доказательство этого утверждения в качестве упражнения читателю)~~. Мы можем получить абелеву группу, если вместо объединения возьмём симметрическую разницу, но поведение этой операции немного не то.

Оказывается, что если мы будем отдельно вести учёт включений и исключений, то и вовсе добьёмся желаемого поведения. Делается это через представление множества в виде пары двух множеств: слева элементы, которые надо включить; справа, которые надо исключить.

PairedHashSet.cs

public record PairedSet<T>(HashSet<T> First, HashSet<T> Second)
{
    public PairedSet() : this(new(), new())
    {
    }

    public PairedHashSet(IEnumerable<T> single) : this(new(single), new())
    {
    }
}

public static class PairedSetExtensions
{
    public static HashSet<T> ToHashSet<T>(this PairedSet<T> pairedSet)
    {
        var (first, second) = pairedSet;
        return first.Except(second);
    }
}

public static class HashSetExtensions
{
    public static HashSet<T> Except<T>(this HashSet<T> first, HashSet<T> second)
    {
        var result = new HashSet<T>(first);
        result.ExceptWith(second);
        return result;
    }
    
    public static HashSet<T> Union<T>(this HashSet<T> first, HashSet<T> second)
    {
        var result = new HashSet<T>(first);
        result.UnionWith(second);
        return result;
    }
}

public struct PairedHashSetGroup<T> : IGroup<PairedHashSet<T>>
{
    public PairedHashSet<T> Plus(PairedHashSet<T> left, PairedHashSet<T> right)
    {
        var (left1, left2) = left;
        var (right1, right2) = right;
        var newLeft = left1.Except(right2).Union(right1.Except(left2));
        var newRight = left2.Except(right1).Union(right2.Except(left1));
        return new PairedHashSet<T>(newLeft, newRight);
    }

    public PairedHashSet<T> Zero => new ();
    
    public PairedHashSet<T> Inverse(PairedHashSet<T> item)
    {
        var (first, second) = item;
        return new PairedHashSet<T>(second, first);
    }
}

Такая логика очень просто переносится на списки, при чём мы можем выбрать - исключать с конца списка или с его начала.

PairedList.cs

public record PairedList<T>(List<T> First, List<T> Second)
{
    public PairedList() : this(new(), new())
    {
    }

    public PairedList(IEnumerable<T> single) : this(new(single), new())
    {
    }
}

public static class PairedListExtensions
{
    public static List<T> ToList<T>(this PairedList<T> pairedList)
    {
        var (first, second) = pairedList;
        return first.Except(second);
    }
}

public static class ListExtensions
{
    public static List<T> Union<T>(this List<T> list, List<T> items)
    {
        var result = new List<T>(list);
        result.AddRange(items);
        return result;
    }
    
    public static List<T> Except<T>(this List<T> first, List<T> second)
    {
        var result = new List<T>(first);
        second.ForEach(item =>
        {
            var li = result.LastIndexOf(item);
            if (li > -1)
            {
                result.RemoveAt(li);
            }
        });
        return result;
    }
}

PairedListGroup.cs

public struct PairedListGroup<T> : IGroup<PairedList<T>>
{
    public PairedList<T> Plus(PairedList<T> left, PairedList<T> right)
    {
        var (left1, left2) = left;
        var (right1, right2) = right;
        var newLeft = left1.Except(right2).Union(right1.Except(left2));
        var newRight = left2.Except(right1).Union(right2.Except(left1));
        return new PairedList<T>(newLeft, newRight);
    }

    public PairedList<T> Zero => new ();
    
    public PairedList<T> Inverse(PairedList<T> item)
    {
        var (first, second) = item;
        return new PairedList<T>(second, first);
    }
}

PairedEnumerable.cs

Да, классы "парных" структур почти идентичные, но особо красиво и не напишешь.

И теперь, вернувшись к нашему каталогу, мы можем проверить всё описанное.

var chars = stringsCatalogue.Reduce<PairedList<char>, PairedListGroup<char>>(
    s => new PairedList<char>(s)
).ToList();
Console.WriteLine(string.Join("", chars)); // bed

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

// немного расширим список конструкторов
public record PairedList<T>(List<T> First, List<T> Second)
{
    ...
    public PairedList(T item) : this(new List<T> {item})
    {
    }
}

И тогда можно написать такое расширение к каталогу.

public static class CatalogueExtensions
{
    public static List<T> Collect<T>(this Catalogue<T> catalogue) =>
        catalogue.Reduce<PairedList<T>, PairedListGroup<T>>(
            x => new PairedList<T>(x)
        ).ToList();
}

Такое сработает даже для какой-нибудь dto'шки.

public record SomeDto(int Number, bool Flag, string Field)
{
}

Сделаем для неё каталог и поиграемся с ним.

var someDtosCatalogue = new Catalogue<SomeDto>()
    .Add(new SomeDto(1, false, "asa"))
    .Add(new SomeDto(2, true, "asa"))
    .Remove(new SomeDto(1, false, "asa"));

Элементарно, размер коллекции (не каталога).

someDtosCatalogue.Reduce<int, IntAddGroup>(_ => 1)

Можно взять саму коллекцию и что-то с ней сделать.

var someDtosObjects = someDtosCatalogue.Collect();
someDtosObjects.ForEach(Console.WriteLine);
// SomeDto { Number = 2, Flag = True, Field = asa }

Или потрогать логи.

var logs = someDtosCatalogue.ToList();
logs.ForEach(Console.WriteLine);
// Add { Data = SomeDto { Number = 1, Flag = False, Field = asa } }
// Add { Data = SomeDto { Number = 2, Flag = True, Field = asa } }
// Remove { Data = SomeDto { Number = 1, Flag = False, Field = asa } }

Что-то на группах сильно задержались, пора двигаться дальше.

Кольцо

С древних времён до наших дней дошёл очень известный и интересный факт. Если имеется прямоугольный треугольник со сторонами , то они удовлетворяют равенству . Данное утверждение - это теорема Пифагора, знакомая, наверно, почти каждому школьнику.

При этом у людей всегда был интерес к рассмотрению в рамках этой теоремы таких прямоугольных треугольников, у которых стороны целые. Какое-то время спустя возникло описание всех таких треугольников, но прогресс на этом не останавливается.

Любого математика и программиста, на мой взгляд, объединяет желание обобщать. И прогресс пошёл в сторону обобщения по показателю степени: оказывается, что написанная выше формула - это частный случай Диофантова уравнения . И в 1637 году, математик Пьер Ферма сформулировал свою Великую Теорему, которая говорит о том, что таких целых троек не найти для натуральных . Это историческое событие, можно сказать, положило начало теории колец.

Дело в том, что первые попытки доказательства осуществлялись для конкретных значений и базировались на изучении делимости в множествах вида $\mathbb{Z}[\sqrt{-n}]= \{ a + b\sqrt{-n}: a,b \in \mathbb{Z} \}$ . В результате рассмотрения таких множеств математики пришли к выводу, что их элементы ведут себя как целые числа, и возникла необходимость в обобщении их арифметики. Так возникло понятие кольца.

Кольцо (коммутативное) - это множество с двумя бинарными операциями и $\times$ такое, что:

- абелева группа;
$(R, \times)$ - (коммутативный) моноид;
$\times$ дистрибутивно относительно - $\forall \; a, b, c \in R : (a + b) \times c = a \times c + b \times c$ (при чём как слева, так и справа).

public interface IRing<T> : IGroup<T>
{
    T One { get; }
    
    T Times(T left, T right);
}

Дальнейшие примеры будут менее приближенными к реальности, может быть даже в какой-то степени игрушечными, но не менее занимательными и интересными.

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

Начнём издалека, со знакомства с таким понятием, как гомоморфизм. Гомоморфизм - это отображение между двумя структурами, которое сохраняет операцию. Например, есть две структуры: $(G, \oplus)$ и $(H, \otimes)$ Тогда, отображение $\phi: G \to H$ называется гомоморфизмом, если

$\forall \; x, y \in X \; \phi(x \oplus y) = \phi(x) \otimes \phi(y)$

Самое главное для понимания то, что гомоморфизм - это абстрактная штука, целый класс отображений. Потому что они бывают сюръективные, инъективные, в себя и т. д.

Самым важным гомоморфизмом является изоморфизм(биекция, сохраняющая операцию). Но почему? Потому что помимо того, что у двух структур одинаковое поведение операции, есть взаимно-однозначное соответствие между ними. А значит не важно, с элементами какой структуры работать для описания её свойств, потому что мы всегда можем прыгать туда-сюда.

Например, вещественные числа по сложению $(\mathbb{R}, +)$ образуют группу, и положительные вещественные по умножению $(\mathbb{R}_+^*, *)$ тоже. Между ними существует изоморфизм $x \mapsto e^x$ (поэлементная нотация отображения).

И надо ли нам рассматривать каждую группу по отдельности, когда можно описать одну, а потом сказать, что вторая это первая с точностью до изоморфизма? Вопрос риторический.

Есть также другой интересный класс гомоморфизмов, это эндоморфизмы. Эндоморфизм - это гомоморфизм в себя. Множество всех эндоморфизмов структуры обозначается , а если - абелева группа, то - кольцо. Для этого сложение надо определить поточечно, а в качестве умножения взять композицию функций.

public struct End<T, G> : IRing<Func<T, T>>
    where G : struct, IGroup<T>
{
    public Func<T, T> Plus(Func<T, T> left, Func<T, T> right) => 
        x => default(G).Plus(left(x), right(x));

    public Func<T, T> Zero => _ => default(G).Zero;

    public Func<T, T> Inverse(Func<T, T> item) =>
        x => default(G).Inverse(x);

    public Func<T, T> One => x => x;

    public Func<T, T> Times(Func<T, T> left, Func<T, T> right) =>
        x => left(right(x));
}

Поиграемся с End<T, G> и создадим например функцию, генерирующую множество степеней двойки. Перед этим добавим одноэлементный конструктор в PairedHashSet<T> и напишем расширение для кольца, считающее степень.

RingExtensions.cs

public static class RingExtensions
{
    public static T Power<T>(this IRing<T> ring, T item, int n)
    {
        var result = item;
        for (var i = 1; i < n; i++)
        {
            result = ring.Times(result, item);
        }

        return result;
    }
}

var end = default(End<PairedHashSet<int>, PairedHashSetGroup<int>>);
var id = end.One;
Func<PairedHashSet<int>, PairedHashSet<int>> x2 = 
    s => new (s.ToHashSet().Select(i => i * 2));
var idPlusX2 = end.Plus(id, x2);
var pows = end.Power(idPlusX2, 6)(new (1)); // {1, 2, 4, 8, 16, 32, 64}

Полукольцо

Как и в случае с группой у кольца есть свой "полу" аналог. Всё также есть тройка $(S, +, \times)$ , но требуют от неё других вещей:

- коммутативный моноид;
$(S, \times)$ - моноид;
Умножение дистрибутивно относительно сложения;
Для всех элементов полукольца выполняется поглощающее свойство нуля: $\forall \; x \in S \; x \times 0 = 0 = 0 \times x$ .

public interface ISemiRing<T> : IMonoid<T>
{
    T One { get; }

    T Times(T left, T right);
}

То есть, в отличие от кольца у нас не требуют обратного элемента по сложению, а требование для нуля вытекает как раз из отсутствия формального минуса. Здесь можно посмотреть примеры структур, где оно не выполняется.

Каких-то общих размышлений о полукольце не будет. Просто скажу, что у него есть много практических применений. Например, в этой книжке научно обосновывается (с точки зрения математики) и детально описывается тот факт, что широкий класс задач на графах можно решить более менее унифицированным способом за счёт обобщения матричного умножения и адаптации матрицы инцидентности к нужному умножению.

Для этого необходимо рассматривать матрицы не как систему чисел, а как систему произвольных элементов, над которыми можно построить алгебру. То есть рассматривается множество всех квадратных матриц размера $n \times n$ , элементы которой взяты из полукольца $(S, \oplus, \otimes)$ . Тогда умножение матриц можно определить в терминах операций полукольца:

$c_{ij} = \bigoplus_{k = 1}^n a_{ik} \otimes b_{kj}$

public class SquareMatrix<T, S> : IEnumerable<SquareMatrix<T, S>.Vector>
    where S : struct, ISemiRing<T>
{
    private readonly int _size;
    private readonly List<Vector> _rows = new();

    public SquareMatrix(int size)
    {
        _size = size;
        for (var i = 0; i < _size; i++)
        {
            _rows.Add(new Vector(
                Enumerable.Repeat(default(S).Zero, _size)
            ));
        }
    }

    public SquareMatrix(int size, params IEnumerable<T>[] rows)
    {
        _size = size;
        _rows.AddRange(rows.Select(x => new Vector(x)));
    }

    public T this[int i, int j]
    {
        get => _rows[i][j];
        set => _rows[i][j] = value;
    }

    public SquareMatrix<T, S> Transpose()
    {
        var columns = Enumerable
            .Range(0, _size)
            .Select(i => _rows.Select(col => col[i]));
        return new (_size, columns.ToArray());
    }

    public SquareMatrix<T, S> Product(SquareMatrix<T, S> that)
    {
        var transposed = that.Transpose();
        var rows = this
            .Select(x => transposed.Select(x.Dot));
        return new (_size, rows.ToArray());
    }

    public SquareMatrix<T, S> Power(int n)
    {
        var result = this;
        for (var i = 1; i < n; i++)
        {
            result = result.Product(this);
        }

        return result;
    }

    public IEnumerator<Vector> GetEnumerator() => _rows.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    public override string ToString() =>
        new StringBuilder()
            .AppendJoin('\n', _rows.Select(row =>
                new StringBuilder()
                    .Append('|')
                    .AppendJoin(", ", row)
                    .Append('|')))
            .ToString();

    public class Vector : IEnumerable<T>
    {
        private readonly List<T> _items;

        public Vector(IEnumerable<T> items)
        {
            _items = new List<T>(items);
        }

        public T this[int index]
        {
            get=> _items[index];
            set => _items[index] = value;
        }

        public T Dot(Vector that) => _items
            .Zip(that._items)
            .Select(pair => default(S).Times(pair.First, pair.Second))
            .Sum<T, S>();

        public IEnumerator<T> GetEnumerator() => _items.GetEnumerator();

        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    }
}

И, например, в полукольце $(\mathbb{R} \cup \{ + \infty\}, \min, +)$ , решается задача о нахождении размера самого короткого пути между вершинами и за или меньше шагов. В полукольце же $(\mathbb{R} \cup \{ - \infty\}, \max, +)$ решается аналогичная задача для нахождения размера самого длинного пути.

MinPlus.cs

public struct MinPlus : ISemiRing<double>
{
    public double Plus(double left, double right) => Min(left, right);

    public double Zero => double.PositiveInfinity;
    
    public double One => 0;

    public double Times(double left, double right) => left + right;
}

MaxPlus.cs

public struct MaxPlus : ISemiRing<double>
{
    public double Plus(double left, double right) => Max(left, right);

    public double Zero => double.NegativeInfinity;
    
    public double One => 0;

    public double Times(double left, double right) => left + right;
}

Проверим для начала, насколько корректно работает возведение в степень в полукольце целых чисел.

SquareMatrix<int, IntSemiRing> testMatrix = new(3,
    new[] {1, 0, 3},
    new[] {0, 5, 0},
    new[] {2, 0, 6}
);
Console.WriteLine(testMatrix.Power(4));

Действительно, получилась матрица

$\begin{pmatrix} 343 & 0 & 1029 \\ 0 & 625 & 0 \\ 686 & 0 & 2058 \end{pmatrix}$

Теперь рассмотрим следующий граф для примера

Как уже говорилось ранее, мы можем решать задачи, обобщая матричное умножение. В случае двух упомянутых ранее задач, всё что надо сделать это вычислить $A^k_{ij}$ .

public class WeightedGraph
{
    private readonly int _size;
    private readonly Dictionary<int, List<(int Vertex, double Weight)>> _adjancencyList = new();

    public WeightedGraph(int size, params (int, List<(int Vertex, double Weight)>)[] adjancencyList)
    {
        _size = size;
        adjancencyList.ToList()
            .ForEach(x => _adjancencyList[x.Item1] = x.Item2);
    }

    private SquareMatrix<double, S> GetAdjacencyMatrix<S>() 
        where S : struct, ISemiRing<double>
    {
        var adjancencyMatrix = new SquareMatrix<double, S>(_size);
        for (var i = 0; i < _size; i++)
        {
            adjancencyMatrix[i, i] = default(S).One;
        }

        foreach (var key in _adjancencyList.Keys)
        {
            foreach (var (vertex, weight) in _adjancencyList[key])
            {
                adjancencyMatrix[key, vertex] = weight;
            }
        }

        return adjancencyMatrix;
    }
    
    public double GetShortestPath(int i, int j, int k) => 
        GetAdjacencyMatrix<MinPlus>()
            .Power(k)[i, j];

    public double GetLongestPath(int i, int j, int k) =>
        GetAdjacencyMatrix<MaxPlus>()
            .Power(k)[i, j];
}

Например, очевидно, что кратчайший путь $a \to d$ за 3 и менее шагов займёт 8 единиц, а длиннейший за 2 и менее шагов - 13.

var weightedGraph = new WeightedGraph(4,
    (0, new() {(1, 3), (2, 8), (3, 12)}),
    (1, new() {(2, 2), (3, 10)}),
    (2, new() {(3, 3)})
);

Console.WriteLine(weightedGraph.GetShortestPath(0, 3, 3)); // 8
Console.WriteLine(weightedGraph.GetLongestPath(0, 3, 2)); // 13

Резюме

Надеюсь этот материал принёс вам гораздо больше полезного и интересного, чем предыдущий. Да, многие из нас на работе гоняют json'ы, клепают формочки, но разве это значит, что не нужно развиваться? Мне кажется, порой мы забываем о том, что профессия программиста неразрывно связана с творчеством, поиском, исследованиями и энтузиазмом, который драйвит всю эту деятельность. Всё ещё впереди. Поэтому, хочется закончить словами отсюда. Лучше и не скажешь.

Ещё я веду telegram канал StepOne, где оставляю небольшие заметки про разработку и мир IT.

Алгебраический код на GitHub

Теги:

Хабы:

Властелин структур

Группа

Кольцо

Полукольцо

Резюме

Публикации

Истории

Работа

Ближайшие события