## Graph-related classes

Base implementations of the relevant classes in my graph library. I’m using C#9 in a .NET 5 project. I opted to use `struct`

s for my `Vertex`

and `Edge`

types to disallow `null`

, which simplifies the equality and comparison implementations. I’ve also chosen to keep all collections as generic as possible using `IEnumerable<T>`

and I’ve also tried to use LINQ where I could because it’s convenient.

`Graph.cs`

A simple directed graph with some basic functionalities.

```
public class DirectedGraph<T, U>
where T : IComparable<T>, IEquatable<T>
where U : IComparable<U>, IEquatable<U>
{
public LinkedList<Vertex<T>> Vertices { get; set; } = new();
public LinkedList<Edge<T, U>> Edges { get; set; } = new();
public virtual void Add(T state)
=> Vertices.AddLast(new Vertex<T>(state));
public virtual void SetEdge(Vertex<T> from, Vertex<T> to, U weight)
{
if (Vertices.Contains(from) && Vertices.Contains(to))
{
Edges.AddLast(new Edge<T, U>(from, to, weight));
}
}
public virtual IEnumerable<Edge<T, U>> GetEdgesFrom(Vertex<T> from)
=> Edges.Where(x => x.From.Equals(from));
public virtual IEnumerable<Edge<T, U>> GetEdgesTo(Vertex<T> to)
=> Edges.Where(x => x.To.Equals(to));
// Method to be reviewed
public IEnumerable<IEnumerable<Edge<T, U>>> GetPathsWithLengthFrom(int length, Vertex<T> vertex)
{
// Using breadth-first search
if (length == 1)
{
// This seems like a reasonable base case
return GetEdgesFrom(vertex).Select(x => Enumerable.Empty<Edge<T, U>>().Append(x));
}
else if (length > 1)
{
var pathsSoFar = GetPathsWithLengthFrom(length - 1, vertex);
var newPaths = Enumerable.Empty<IEnumerable<Edge<T, U>>>();
foreach (var path in pathsSoFar)
{
// Better way to duplicate paths or other approach altogether?
var pathEnd = path.Last().To;
var nextPieces = GetEdgesFrom(pathEnd);
foreach (var nextPiece in nextPieces)
{
newPaths = newPaths.Append(path.Append(nextPiece));
}
}
return newPaths;
}
throw new ArgumentOutOfRangeException(nameof(length), "Path length must be greater than or equal to 1.");
}
}
```

`Vertex.cs`

Abridged version of the vertex class with basic interface implementations. In my actual project I also implemented all the comparison and equality operators (<, >, ==, etc.).

```
public struct Vertex<T> :
IComparable<Vertex<T>>,
IEquatable<Vertex<T>>,
IComparable<T>,
IEquatable<T>
where T :
IComparable<T>,
IEquatable<T>
{
public Vertex(T state)
=> State = state;
public T State { get; set; }
#region Interface implementations and operator overloads
public int CompareTo(Vertex<T> other)
=> State.CompareTo(other.State);
public int CompareTo(T other)
=> State.CompareTo(other);
public bool Equals(Vertex<T> other)
=> CompareTo(other) == 0;
public bool Equals(T other)
=> CompareTo(other) == 0;
public override int GetHashCode()
=> State.GetHashCode();
#endregion
}
```

`Edge.cs`

```
public struct Edge<T, U>
where T : IComparable<T>, IEquatable<T>
where U : IComparable<U>, IEquatable<U>
{
public Edge(Vertex<T> from, Vertex<T> to, U weight)
=> (From, To, Weight) = (from, to, weight);
public Vertex<T> From { get; set; }
public Vertex<T> To { get; set; }
public U Weight { get; set; }
}
```

## Goal of the graph library

Initially, I wanted to use graphs to enumerate all possible ways to choose `k`

elements from a set of `n`

total elements, but I discovered better ways to achieve that goal.

That being said, I created a graph with customizable states and weights for a poker calculator. The customizable weight could for example keep track of which cards were drawn or which hands are likely to arise given the current game state and the remaining cards in the deck.

Finally, writing a small graph theory library from scratch helps me learn more about algorithms and data structures.

## Why C# and not a faster language like C/C++?

I’m just more familiar with C# and I like LINQ, C# also has a ton of abstractions that I would likely have to import or write myself in C/C++ (the more I have to write myself, the more likely I’m going to make mistakes). Not to mention memory management with pointers and references.

But if C# turns out to be too slow, even after optimisations, I might switch over to C/C++ anyway.