## Archive for the ‘**Abstract Algebra**’ Category

## Tropical Representation of the All-Pairs Shortest Path Problem

### Motivation

While I was doing my Abstract Algebra research the other month, I came across an interesting way of simplifying the representation of the all-pairs shortest path problem using Tropical Geometry. I thought it was pretty clever, so I thought I’d do a quick write-up.

### Problem Statement

The all-pairs shortest path problem is to identify the minimum path cost, , out of the possible paths between vertices and .

### Proposition

Consider a weighted directed graph (digraph), , consisting of vertices, , and directed edges (arcs), , and a function, , yielding the weight of an edge. Only those weights from the positive affinely extended real numbers, , are allowed per the problem statement. The adjacency matrix representation, , of is given by the following matrix:

Now, consider a semi-ring over whose additive operator, , is given by the minimum function, , and whose multiplicative operator, , is given by addition, . The additive unit is given by infinity, , and the multiplicative unit by zero, . This semi-ring is the Tropical Semi-ring . (The namesake of *tropical* is in honor of Brazilian Imre Simon who developed this branch of mathematics.)

Linear algebra constructs can be tropicalized to yield the familiar definitions for matrix addition and multiplication for matricies and .

Given the two prior statements, the elegant solution to the all-pairs shortest path problem is given by taking powers of the adjacency matrix: .

### Proof

To see how this works out, start with . The matrix represents the minimum cost between any two adjacent vertices. In other words, the minimum cost for all paths containing a single edge. The next inductive step is to consider paths containing at most two adjacent edges. Squaring the adjacency matrix yields all such paths. When the matrix is squared, each edge is concatenated to all other adjacent edges and the minimum weight of the paths is selected. This thought process can iterated as follows:

The result is a typical Bellman equation. A graph can have at most edges between any two vertices, thus, the solution to the all-pairs shortest path problem is given by .

### Example

As a worked example, consider the following graph whose set of vertices is given by the set , set of arcs by and weight function, , as labeled on the graph.

The all-pairs shortest paths are given by the following calculations where the row and column coordinates correspond to the vertices of . Values in **bold** denote a change in the shortest path between two vertices.

### Computational Complexity

From asymptotic standpoint, tropical matrix multiplication is still on the order of traditional matrix multiplication of . Computing the all-pairs shortest path problem using this approach is on the order of since we must perform the tropical matrix multiplication times. Now, This can be improved slightly since tropical matrix multiplication is associative, so we can leverage the repeated squaring approach and reduce the time complexity down to .

The time complexity can be further reduced to using the Floyd-Warshall Algorithm, which is another dynamic programming approach that is similar in form to the tropical representation of the problem. In essence, it follows the same base case, but it’s recurrence statement only considers a range of vertices with respect to the two vertices being considered. A more in depth review of the algorithm can be found in the references.

### References

“Floyd-Warshall’s Algorithm.” *Algorithmist*. Web. 12 Apr. 2012.

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. “25.2 The Floyd-Warshall Algorithm.” *Introduction to Algorithms*. 2nd ed. Cambridge, MA: MIT, 2001. 629-35. Print.

Diestel, Reinhard. *Graph theory*. Heidelberg New York: Springer, 2010.

Laface, Antonio. *Introduction to Tropical Geometry* [pdf]. 29 Nov. 2006. Web. 11 Apr. 2012.

Maclagan, Diane, and Bernd Sturmfels. *Introduction to Tropical Geometry* [pdf]. 4 Nov. 2009. Web. 9 Apr. 2012.

Mohri, Mehryar. “Semiring Frameworks and Algorithms for Shortest-Distance Problems” [pdf]. *Journal of Automata, Languages and Combinatorics* 7 (2002) 3: 321-50. 8 Aug. 2002. Web. 31 Mar. 2012.

## Abstract Algebra in C#

### Motivation

In C++ it is easy to define arbitrary template methods for computations involving primitive numeric types because all types inherently have arithmetic operations defined. Thus, a programmer need only implement one method for all numeric types. The compiler will infer the use and substitute the type at compile time and emit the appropriate machine instructions. This is C++’s approach to parametric polymorphism.

With the release of C# 2.0 in the fall of 2005, the language finally got a taste of parametric polymorphism in the form of generics. Unfortunately, types in C# do not inherently have arithmetic operations defined, so methods involving computations must use ad-hoc polymorphism to achieve the same result as in C++. The consequence is a greater bloat in code and an increased maintenance liability.

To get around this design limitation, I’ve decided to leverage C#’s approach to subtype polymorphism and to draw from Abstract Algebra to implement a collection of interfaces allowing for C++ like template functionality in C#. The following is an overview of the mathematical theory used to support and guide the design of my solution. In addition, I will present example problems from mathematics and computer science that can be represented in this solution along with examples how type agnostic computations that can be performed using this solution.

### Abstract Algebra

Abstract Algebra is focused on how different algebraic structures behave in the presence of different axioms, operations and sets. In the following three sections, I will go over the fundamental sub-fields and how they are represented under the solution.

In all three sections, I will represent the distinction between algebraic structures using C# interfaces. The type parameters on these interfaces represent the sets being acted upon by each algebraic structure. This convention is consistent with intuitionistic (i.e., Chruch-style) type theory embraced by C#’s Common Type System (CTS). Use of parameter constraints will be used when type parameters are intended to be of a specific type. Functions on the set and elements of the set will be represented by methods and properties respectively.

#### Group Theory

Group Theory is the simplest of sub-fields of Abstract Algebra dealing with the study of a single binary operation, , acting on a set . There are five axioms used to describe the structures studied under Group Theory:

- Closure:
- Associativity:
- Commutativity :
- Identity:
- Inverse:

The simplest of these structures is the Groupoid satisfying only axiom (1). Any Groupoid also satisfying axiom (2) is known as a Semi-group. Any Semi-group satisfying axiom (4) is a Monoid. Monoid’s also satisfying axiom (5) are known as Groups. Any Group satisfying axiom (3) is an Abelian Group.

public interface IGroupoid<T> { T Operation(T a, T b); } public interface ISemigroup<T> : IGroupoid<T> { } public interface IMonoid<T> : ISemigroup<T> { T Identity { get; } } public interface IGroup<T> : IMonoid<T> { T Inverse(T t); } public interface IAbelianGroup<T> : IGroup<T> { }

#### Ring Theory

The next logical sub-field of Abstract Algebra to study is Ring Theory which is the study of two operations, and , on a single set. In addition to the axioms outlined above, there is an addition axiom for describing how one operations distributes over the other.

- Distributivity:

All of the following ring structures satisfy axiom (6). Rings are distinguished by the properties of their operands. The simplest of these structures is the Ringoid where both operands are given by Groupoids. Any Ringoid whose operands are Semi-groups is a Semi-ring. Any Semi-ring whose first operand is a Group is a Ring. Any Ring whose second operand is a Monoid is a Ring with Unity. Any Ring with Unity whose second operand is a Group is Division Ring. Any Division Ring whose operands are both Abelian Groups is a Field.

public interface IRingoid<T, A, M> where A : IGroupoid<T> where M : IGroupoid<T> { A Addition { get; } M Multiplication { get; } T Distribute(T a, T b); } public interface ISemiring<T, A, M> : IRingoid<T, A, M> where A : ISemigroup<T> where M : ISemigroup<T> { } public interface IRing<T, A, M> : ISemiring<T, A, M> where A : IGroup<T> where M : ISemigroup<T> { } public interface IRingWithUnity<T, A, M> : IRing<T, A, M> where A : IGroup<T> where M : IMonoid<T> { } public interface IDivisionRing<T, A, M> : IRingWithUnity<T, A, M> where A : IGroup<T> where M : IGroup<T> { } public interface IField<T, A, M> : IDivisionRing<T, A, M> where A : IAbelianGroup<T> where M : IAbelianGroup<T> { }

#### Module Theory

The last, and more familiar, sub-field of Abstract Algebra is Module Theory which deals with structures with an operation, , over two separate sets: and that satisfy the following axioms.

- Distributivity of :
- Distributivity of :
- Associativity of :

All of the following module structures satisfy axioms (7)-(9). A Module consists of a scalar Ring and an vector Abelian Group. Any Module whose Ring is a Ring with Unity is a Unitary Module. Any Unitary Module whose Ring with Unity is a Abelian Group is a Vector Space.

public interface IModule< TScalar, TVector, TScalarRing, TScalarAddativeGroup, TScalarMultiplicativeSemigroup, TVectorAddativeAbelianGroup > where TScalarRing : IRing<TScalar, TScalarAddativeGroup, TScalarMultiplicativeSemigroup> where TScalarAddativeGroup : IGroup<TScalar> where TScalarMultiplicativeSemigroup : ISemigroup<TScalar> where TVectorAddativeAbelianGroup : IAbelianGroup<TVector> { TScalarRing Scalar { get; } TVectorAddativeAbelianGroup Vector { get; } TVector Distribute(TScalar t, TVector r); } public interface IUnitaryModule< TScalar, TVector, TScalarRingWithUnity, TScalarAddativeGroup, TScalarMultiplicativeMonoid, TVectorAddativeAbelianGroup > : IModule< TScalar, TVector, TScalarRingWithUnity, TScalarAddativeGroup, TScalarMultiplicativeMonoid, TVectorAddativeAbelianGroup > where TScalarRingWithUnity : IRingWithUnity<TScalar, TScalarAddativeGroup, TScalarMultiplicativeMonoid> where TScalarAddativeGroup : IGroup<TScalar> where TScalarMultiplicativeMonoid : IMonoid<TScalar> where TVectorAddativeAbelianGroup : IAbelianGroup<TVector> { } public interface IVectorSpace< TScalar, TVector, TScalarField, TScalarAddativeAbelianGroup, TScalarMultiplicativeAbelianGroup, TVectorAddativeAbelianGroup > : IUnitaryModule< TScalar, TVector, TScalarField, TScalarAddativeAbelianGroup, TScalarMultiplicativeAbelianGroup, TVectorAddativeAbelianGroup > where TScalarField : IField<TScalar, TScalarAddativeAbelianGroup, TScalarMultiplicativeAbelianGroup> where TScalarAddativeAbelianGroup : IAbelianGroup<TScalar> where TScalarMultiplicativeAbelianGroup : IAbelianGroup<TScalar> where TVectorAddativeAbelianGroup : IAbelianGroup<TVector> { }

### Representation of Value Types

The CTS allows for both value and reference types on the .NET Common Language Infrastructure (CLI). The following are examples of how each theory presented above can leverage value types found in the C# language to represent concepts drawn from mathematics.

#### Enum Value Types and the Dihedral Group

One of the simplest finite groups is the Dihedral Group of order eight, , representing the different orientations of a square, , obtained by reflecting the square about the vertical axis, , and rotating the square by ninety degrees, . The generating set is given by and gives rise to the set These elements are assigned names as follows: , , , , , , and . The relationship between these elements is visualized below:

The easiest way to represent this group as a value type is with an enum.

enum Symmetry { Rot000, Rot090, Rot180, Rot270, RefVer, RefDes, RefHoz, RefAsc }

From this enum we can define the basic Group Theory algebraic structures to take us to .

public class SymmetryGroupoid : IGroupoid<Symmetry> { public Symmetry Operation(Symmetry a, Symmetry b) { // 64 cases } } public class SymmetrySemigroup : SymmetryGroupoid, ISemigroup<Symmetry> { } public class SymmetryMonoid : SymmetrySemigroup, IMonoid<Symmetry> { public Symmetry Identity { get { return Symmetry.Rot000; } } } public class SymmetryGroup : SymmetryMonoid, IGroup<Symmetry> { public Symmetry Inverse(Symmetry a) { switch (a) { case Symmetry.Rot000: return Symmetry.Rot000; case Symmetry.Rot090: return Symmetry.Rot270; case Symmetry.Rot180: return Symmetry.Rot270; case Symmetry.Rot270: return Symmetry.Rot090; case Symmetry.RefVer: return Symmetry.RefVer; case Symmetry.RefDes: return Symmetry.RefAsc; case Symmetry.RefHoz: return Symmetry.RefHoz; case Symmetry.RefAsc: return Symmetry.RefDes; } throw new NotImplementedException(); } }

#### Integral Value Types and the Commutative Ring with Unity over

C# exposes a number of fixed bit integral value types that allow a programmer to pick an integral value type suitable for the scenario at hand. Operations over these integral value types form a commutative ring with unity whose set is the congruence class where is the number of bits used to represent the integer and is the equivalance class with .

Addition is given by just as multiplication is given by . Both statements are equivalent to the following congruence statements: and respectively.

Under the binary numeral system, modulo is equivalent to ignoring the bits exceeding , or equivalently, where . As a result only the first (right most) bits need to be considered when computing the sum or product of two congruence classes, or in this case, integer values in C#. Thus, in the following implementation, it is not necessary to write any extra code to represent these operations other than writing them in their native form.

The reason why we are limited to a commutative ring with unity instead of a full field is that multiplicative inverses do not exist for all elements. A multiplicative inverse only exists when where is the multiplicative inverse of . For a solution to exist, . Immediately, any even value of will not have a multiplicative inverse in . However, all odd numbers will.

public class AddativeIntegerGroupoid : IGroupoid<long> { public long Operation(long a, long b) { return a + b; } } public class AddativeIntegerSemigroup : AddativeIntegerGroupoid, ISemigroup<long> { } public class AddativeIntegerMonoid : AddativeIntegerSemigroup, IMonoid<long> { public long Identity { get { return 0L; } } } public class AddativeIntegerGroup : AddativeIntegerMonoid, IGroup<long> { public long Inverse(long a) { return -a; } } public class AddativeIntegerAbelianGroup : AddativeIntegerGroup, IAbelianGroup<long> { } public class MultiplicativeIntegerGroupoid : IGroupoid<long> { public long Operation(long a, long b) { return a * b; } } public class MultiplicativeIntegerSemigroup : MultiplicativeIntegerGroupoid, ISemigroup<long> { } public class MultiplicativeIntegerMonoid : MultiplicativeIntegerSemigroup, IMonoid<long> { public long Identity { get { return 1L; } } } public class IntegerRingoid : IRingoid<long, AddativeIntegerGroupoid, MultiplicativeIntegerGroupoid> { public AddativeIntegerGroupoid Addition { get; private set;} public MultiplicativeIntegerGroupoid Multiplication { get; private set;} public IntegerRingoid() { Addition = new AddativeIntegerGroupoid(); Multiplication = new MultiplicativeIntegerGroupoid(); } public long Distribute(long a, long b) { return Multiplication.Operation(a, b); } } public class IntegerSemiring : IntegerRingoid, ISemiring<long, AddativeIntegerSemiring, MultiplicativeIntegerSemiring> { public AddativeIntegerSemiring Addition { get; private set;} public MultiplicativeIntegerSemiring Multiplication { get; private set;} public IntegerSemiring() : base() { Addition = new AddativeIntegerSemiring(); Multiplication = new MultiplicativeIntegerSemiring(); } } public class IntegerRing : IntegerSemiring, IRing<long, AddativeIntegerGroup, MultiplicativeIntegerSemigroup>{ public new AddativeIntegerGroup Addition { get; private set; } public IntegerRing() : base() { Addition = new AddativeIntegerGroup(); } } public class IntegerRingWithUnity : IntegerRing, IRingWithUnity<long, AddativeIntegerGroup, MultiplicativeIntegerMonoid> { public MultiplicativeIntegerMonoid Multiplication { get; private set; } public IntegerRingWithUnity() : base() { Multiplication = new MultiplicativeIntegerMonoid(); } }

#### Floating-point Value Types and the Real Vector Space

C# offers three types that approximate the set of Reals: floats, doubles and decimals. Floats are the least representative followed by doubles and decimals. These types are obviously not continuous, but the error involved in rounding calculations with respect to the calculations in question are negligible and for most intensive purposes can be treated as continuous.

As in the previous discussion on the integers, additive and multiplicative classes are defined over the algebraic structures defined in the Group and Ring Theory sections presented above. In addition to these implementations, an additional class is defined to describe a vector.

public class Vector<T> { private T[] vector; public int Dimension { get { return vector.Length; } } public T this[int n] { get { return vector[n]; } set { vector[n] = value; } } public Vector() { vector = new T[2]; } }

With these classes, it is now possible to implement the algebraic structures presented in the Module Theory section from above.

public class RealVectorModule : IModule<double, Vector<double>, RealRing, AddativeRealGroup, MultiplicativeRealSemigroup, VectorAbelianGroup<double>> { public RealRing Scalar { get; private set; } public VectorAbelianGroup<double> Vector { get; private set; } public RealVectorModule() { Scalar = new RealRing(); Vector = new VectorAbelianGroup<double>(new AddativeRealAbelianGroup()); } public Vector<double> Distribute(double t, Vector<double> r) { Vector<double> c = new Vector<double>(); for (int i = 0; i < c.Dimension; i++) c[i] = Scalar.Multiplication.Operation(t, r[i]); return c; } } public class RealVectorUnitaryModule : RealVectorModule, IUnitaryModule<double, Vector<double>, RealRingWithUnity, AddativeRealGroup, MultiplicativeRealMonoid, VectorAbelianGroup<double>> { public new RealRingWithUnity Scalar { get; private set; } public RealVectorUnitaryModule() : base() { Scalar = new RealRingWithUnity(); } } public class RealVectorVectorSpace : RealVectorUnitaryModule, IVectorSpace<double, Vector<double>, RealField, AddativeRealAbelianGroup, MultiplicativeRealAbelianGroup, VectorAbelianGroup<double>> { public new RealField Scalar { get; private set; } public RealVectorVectorSpace() : base() { Scalar = new RealField(); } }

### Representation of Reference Types

The following are examples of how each theory presented above can leverage reference types found in the C# language to represent concepts drawn from computer science.

#### Strings, Computability and Monoids

Strings are the simplest of reference types in C#. From an algebraic structure point of view, the set of possible strings, , generated by an alphabet, , and paired with a concatenation operation, , forms a monoid.

public class StringGroupoid : IGroupoid<string> { public string Operation(String a, String b) { return string.Format("{0}{1}", a, b); } } public class StringSemigroup : StringGroupoid, ISemigroup<string> { } public class StringMonoid : StringSemigroup, IMonoid<string> { public string Identity { get { return string.Empty; } } }

Monoids over strings have a volley of applications in the theory of computation. Syntactic Monoids describe the smallest set that recognizes a formal language. Trace Monoids describe concurrent programming by allowing different characters of an alphabet to represent different types of locks and synchronization points, while the remaining characters represent processes.

#### Classes, Interfaces, Type Theory and Semi-rings

Consider the set of types , that are primitive and constructed in C#. The generating set of is the set of primitive reference and value types, , consisting of the types discussed thus far. New types can be defined by defining classes and interfaces.

A simple operation over takes two types, , and yields a third type, , known as a sum type. In type theory, this means that an instance of can be either an instance of or . A second operation over takes two types and yields a third type representing a tuple of the first two types. In other words, .

Both operations form a semi-group and and in conjunction the two form a semi-ring.

To implement this semi-ring is a little involved. The .NET library supports emitting dynamic type definitions at runtime. For sum types, this would lead to an inheritance view of the operation. Types and would end up deriving from which means that any sequence of sums would yield an inheritance tree. A product type would result in composition of types with projection operations, , to access and assign the element of the composite. Both type operation implementations are outside the scope of this write-up and I’ll likely revisit this topic in a future write-up.

#### Delegates and Process Algebras

The third type of reference type to mention is the delegate type which is C#’s approach to creating first-class functions. The simplest of delegates is the built-in Action delegate which represents a single procedure taking no inputs and returning no value.

Given actions , we can define a possible execution operator, , where either or is executed denoted as . The choice operation forms a commutative semigroup since operations are associative and the operation is commutative .

A product operation, , representing the sequential execution of and then is given by . The sequence operator forms a groupoid with unity since the operation is not associative and there is an identity action representing a void operation resulting in .

Both operations together form a ringoid, since the sequence operation distributes over the choice operation . Meaning that takes place and then or takes places is equivalent to and then takes place or and then takes place.

public class SequenceGroupoidWithUnity<Action> : IGroupoid<Action> { public Action Identity { get { return () => {}; } } public Action Operation(Action a, Action b) { return () => { a(); b(); } } } public class ChoiceGroupoid<Action> : IGroupoid<Action> { public Action Operation(Action a, Action b) { if(DateTime.Now.Ticks % 2 == 0) return a; return b; } }

The process algebra an be extended further to describe parallel computations with an additional operation. The operations given thus far enable one to derive the possible execution paths in a process. This enables one to comprehensively test each execution path to achieve complete test coverage.

### Examples

The motivation of this work was to achieve C++’s approach to parametric polymorphism by utilizing C# subtype polymorphism to define the algebraic structure required by a method (akin to the built-in operations on types in C++). To illustrate how these interfaces are to be used, the following example extension methods operate over a collection of a given type and accept the minimal algebraic structure to complete the computation. The result is a single implementation of the calculation that one would expect in C++.

static public class GroupExtensions { static public T Sum<T>(this IEnumerable<T> E, IMonoid<T> m) { return E .FoldL(m.Identity, m.Operation); } } static public class RingoidExtensions { static public T Count<T, R, A, M>(this IEnumerable<R> E, IRingWithUnity<T, A, M> r) where A : IGroup<T> where M : IMonoid<T> { return E .Map((x) => r.Multiplication.Identity) .Sum(r.Addition); } static public T Mean<T, A, M>(this IEnumerable<T> E, IDivisionRing<T, A, M> r) where A : IGroup<T> where M : IGroup<T> { return r.Multiplication.Operation( r.Multiplication.Inverse( E.Count(r) ), E.Sum(r.Addition) ); } static public T Variance<T, A, M>(this IEnumerable<T> E, IDivisionRing<T, A, M> r) where A : IGroup<T> where M : IGroup<T> { T average = E.Mean(r); return r.Multiplication.Operation( r.Multiplication.Inverse( E.Count(r) ), E .Map((x) => r.Addition.Operation(x, r.Addition.Inverse(average))) .Map((x) => r.Multiplication.Operation(x, x) ) .Sum(r.Addition) ); } } static public class ModuleExtensions { static public TV Mean<TS, TV, TSR, TSRA, TSRM, TVA>(this IEnumerable<TV> E, IVectorField<TS, TV, TSR, TSRA, TSRM, TVA> m) where TSR : IField<TS, TSRA, TSRM> where TSRA : IAbelianGroup<TS> where TSRM : IAbelianGroup<TS> where TVA : IAbelianGroup<TV> { return m.Distribute( m.Scalar.Multiplication.Inverse( E.Count(m.Scalar) ), E.FoldL( m.Vector.Identity, m.Vector.Operation ) ); } }

### Conclusion

Abstract Algebra comes with a rich history and theory for dealing with different algebraic structures that are easily represented and used in the C# language to perform type agnostic computations. Several examples drawn from mathematics and computer science illustrated how the solution can be used for both value and reference types in C# and be leveraged in the context of a few example type agnostic computations. The main benefit of this approach is that it minimizes the repetitious coding of computations required under the ad-hoc polymorphism approach adopted by the designers of C# language. The downside is that several structures must be defined for the types being computed over and working with C# parameter constraint system can be unwieldy. While an interesting study, this solution would not be practical in a production setting under the current capabilities of the C# language.

### References

Baeten, J.C.M. *A Brief History of Process Algebra* [pdf]. Department of Computer Science, Technische Universiteit Eindhoven. 31 Mar. 2012.

ECMA International. *Standard ECMA-335 Common Language Infrastructure* [pdf]. 2006.

Fokkink, Wan. *Introduction of Process Algebra* [pdf]. 2nd ed. Berlin: Springer-Verlang, 2007. 10 Apr. 2007. 31 Mar. 2012.

Goodman, Joshua. *Semiring Parsing* [pdf]. Computational Linguistics 25 (1999): 573-605. Microsoft Research. 31 Mar. 2012.

Hungerford, Thomas. *Algebra*. New York: Holt, Rinehart and Winston, 1974.

Ireland, Kenneth. *A classical introduction to modern number theory*. New York: Springer-Verlag, 1990.

Litvinov, G. I., V. P. Maslov, and A. YA Rodionov. *Universal Algorithms, Mathematics of Semirings and Parallel Computations* [pdf]. Spring Lectures Notes in Computational Science and Engineering. 7 May 2010. 31 Mar. 2012 .

Mazurkiewicz, Antoni. *Introduction to Trace Theory* [pdf]. Rep. 19 Nov. 1996. Institute of Computer Science, Polish Academy of Sciences. 31 Mar. 2012.

Pierce, Benjamin. *Types and programming languages.* Cambridge, Mass: MIT Press, 2002.

Stroustrup, Bjarne. *The C++ Programming Language.* Reading, Mass: Addison-Wesley, 1986.