Attempt to make a generic graph implementation and playing around with graph algorithms in C#

DirectedGraph.cs

public class DirectedGraph<TVertex, TWeight>
    where TVertex : IComparable<TVertex>, IEquatable<TVertex>
    where TWeight : IComparable<TWeight>, IEquatable<TWeight>
{
    private readonly List<Vertex<TVertex>> _vertices = new();
    private readonly List<Edge<TVertex, TWeight>> _edges = new();
    private readonly Dictionary<Vertex<TVertex>, List<Edge<TVertex, TWeight>>> _adjacencyList = new();

    public DirectedGraph() { }
    public DirectedGraph(DirectedGraph<TVertex, TWeight> other)
    {
        _vertices.AddRange(other.Vertices.ToList());
        _edges.AddRange(other.Edges.ToList());
        UpdateAdjacencyList();
    }

    public List<Vertex<TVertex>> Vertices { get => _vertices; }
    public List<Edge<TVertex, TWeight>> Edges { get => _edges; }
    public Dictionary<Vertex<TVertex>, List<Edge<TVertex, TWeight>>> AdjacencyList { get => _adjacencyList; }

    public void UpdateAdjacencyList()
    {
        _adjacencyList.Clear();
        foreach (Vertex<TVertex> vertex in _vertices)
        {
            _adjacencyList[vertex] = new();
        }
        foreach (Edge<TVertex, TWeight> edge in _edges)
        {
            _adjacencyList[edge.Source].Add(edge);
        }
    }

    public void AddVertex(Vertex<TVertex> vertex, bool updateAdjacency = true)
    {
        if (_adjacencyList.ContainsKey(vertex))
        {
            throw new ArgumentException("Cannot add duplicate vertex.", nameof(vertex));
        }
        _vertices.Add(vertex);
        if (updateAdjacency)
        {
            UpdateAdjacencyList();
        }
    }

    public void RemoveVertex(Vertex<TVertex> vertex, bool updateAdjacency = true)
    {
        if (!_adjacencyList.ContainsKey(vertex))
        {
            throw new ArgumentException("Cannot remove nonexistent vertex.", nameof(vertex));
        }
        _vertices.Remove(vertex);
        if (updateAdjacency)
        {
            UpdateAdjacencyList();
        }
    }

    public void AddVertices(IEnumerable<Vertex<TVertex>> vertices)
    {
        foreach (Vertex<TVertex> vertex in vertices)
        {
            AddVertex(vertex, false);
        }
        UpdateAdjacencyList();
    }

    public void RemoveVertices(IEnumerable<Vertex<TVertex>> vertices)
    {
        foreach (Vertex<TVertex> vertex in vertices)
        {
            RemoveVertex(vertex, false);
        }
        UpdateAdjacencyList();
    }

    public void AddEdge(Edge<TVertex, TWeight> edge, bool updateAdjacency)
    {
        if (!_adjacencyList.ContainsKey(edge.Source))
        {
            AddVertex(edge.Source);
        }
        if (_edges.Contains(edge))
        {
            throw new ArgumentException("Cannot add duplicate edge.", nameof(edge));
        }
        if (!_adjacencyList.ContainsKey(edge.Destination))
        {
            AddVertex(edge.Destination);
        }
        _edges.Add(edge);
        if (updateAdjacency)
        {
            UpdateAdjacencyList();
        }
    }

    public void AddEdges(IEnumerable<Edge<TVertex, TWeight>> edges)
    {
        foreach (Edge<TVertex, TWeight> edge in edges)
        {
            AddEdge(edge, false);
        }
        UpdateAdjacencyList();
    }
}

Edge.cs

public class Edge<TVertex, TWeight> : Identifiable
    where TVertex : IComparable<TVertex>, IEquatable<TVertex>
    where TWeight : IComparable<TWeight>, IEquatable<TWeight>
{
    public Edge(Vertex<TVertex> source, Vertex<TVertex> destination, TWeight weight)
    {
        Source = source;
        Destination = destination;
        Weight = weight;
    }

    public Vertex<TVertex> Source { get; }
    public Vertex<TVertex> Destination { get; }
    public TWeight Weight { get; }

    public override string ToString()
        => $"{Source} -> {Destination} ({Weight})";

    public override bool Equals(object? obj)
        => base.Equals(obj);

    public override int GetHashCode()
        => base.GetHashCode();
}

GraphExtensions.cs

public static class GraphExtensions
{
    public static DirectedGraph<TVertex, TWeight> BreadthFirstSearch<TVertex, TWeight>(
            this DirectedGraph<TVertex, TWeight> g,
            Vertex<TVertex> source,
            int? maxDistance = null)
        where TVertex : IComparable<TVertex>, IEquatable<TVertex>
        where TWeight : IComparable<TWeight>, IEquatable<TWeight>
    {
        DirectedGraph<TVertex, TWeight> gPrime = new(g);
        IEnumerable<Edge<TVertex, TWeight>> nextEdges = gPrime.AdjacencyList[source];
        int distanceFromSource = 0;
        source.Visit(distanceFromSource++);
        while (nextEdges.Any() && (maxDistance is null || distanceFromSource <= (int)maxDistance))
        {
            foreach (Edge<TVertex, TWeight> next in nextEdges)
            {
                next.Destination.Visit(distanceFromSource);
            }
            nextEdges = nextEdges
                        .Select(next => next.Destination)
                        .Distinct()
                        .SelectMany(dest => gPrime.AdjacencyList[dest])
                        .Distinct()
                        .Where(n => !n.Destination.Visited)
                        .ToList();
            distanceFromSource++;
        }
        return gPrime;
    }

    public static DirectedGraph<TVertex, int> BreadthFirstSearchByDistance<TVertex>(
            this DirectedGraph<TVertex, int> g,
            Vertex<TVertex> source,
            Func<int, bool> distancePredicate)
        where TVertex : IComparable<TVertex>, IEquatable<TVertex>
    {
        DirectedGraph<TVertex, int> gPrime = new(g);
        IEnumerable<Edge<TVertex, int>> nextEdges = gPrime.AdjacencyList[source];
        int distanceFromSource = 0;
        source.Visit(distanceFromSource++);
        while (nextEdges.Any() && distancePredicate(distanceFromSource))
        {
            foreach (Edge<TVertex, int> next in nextEdges)
            {
                next.Destination.Visit(distanceFromSource);
            }
            nextEdges = nextEdges
                        .Select(next => next.Destination)
                        .Distinct()
                        .SelectMany(dest => gPrime.AdjacencyList[dest])
                        .Distinct()
                        .Where(n => !n.Destination.Visited)
                        .ToList();
            distanceFromSource++;
        }
        return gPrime;
    }

    public static IEnumerable<List<Edge<TVertex, TWeight>>> GetPathsBetween<TVertex, TWeight>(
            this DirectedGraph<TVertex, TWeight> g,
            Vertex<TVertex> source,
            Vertex<TVertex> destination,
            List<Edge<TVertex, TWeight>>? visited = null)
        where TVertex : IComparable<TVertex>, IEquatable<TVertex>
        where TWeight : IComparable<TWeight>, IEquatable<TWeight>
    {
        List<List<Edge<TVertex, TWeight>>> paths = new();
        visited ??= new();
        List<Edge<TVertex, TWeight>> nextUnvisitedEdges =
            g.AdjacencyList[source]
                .Where(e => !visited.Any(ve => e.Destination == ve.Source))
                .ToList();
        foreach (var edge in nextUnvisitedEdges)
        {
            List<Edge<TVertex, TWeight>> nextPath = new(visited);
            nextPath.Add(edge);
            if (edge.Destination != destination)
            {
                // Continue searching
                IEnumerable<List<Edge<TVertex, TWeight>>> nextPaths =
                    g.GetPathsBetween(edge.Destination, destination, nextPath);
                foreach (var path in nextPaths)
                {
                    // Return newly found paths
                    yield return path;
                }
            }
            else
            {
                // Return current path
                yield return nextPath;
            }
        }
    }

    public static long GetPathCount<TVertex, TWeight>(
            this DirectedGraph<TVertex, TWeight> g,
            Vertex<TVertex> source,
            Vertex<TVertex> destination,
            List<Vertex<TVertex>>? visited = null)
        where TVertex : IComparable<TVertex>, IEquatable<TVertex>
        where TWeight : IComparable<TWeight>, IEquatable<TWeight>
    {
        visited ??= new() { source };
        long totalPaths = 0;
        List<Edge<TVertex, TWeight>> nextUnvisitedEdges =
            g.AdjacencyList[source]
                .Where(e => !visited.Contains(e.Destination))
                .ToList();
        foreach (var edge in nextUnvisitedEdges)
        {
            List<Vertex<TVertex>> visitedThisPath = new(visited);
            visitedThisPath.Add(edge.Destination);
            if (edge.Destination != destination)
            {
                totalPaths += g.GetPathCount(edge.Destination, destination, visitedThisPath);
            }
            else
            {
                totalPaths++;
            }
        }
        return totalPaths;
    }
}

Identifiable.cs

public class Identifiable : IComparable<Identifiable>, IEquatable<Identifiable>
{
    protected Identifiable()
    {
        Id = Guid.NewGuid();
    }
    public Guid Id { get; }

    public int CompareTo(Identifiable? other)
        => other is null
            ? 1
            : Id.CompareTo(other.Id);

    public bool Equals(Identifiable? other)
        => CompareTo(other) == 0;

    public override bool Equals(object? obj)
        => obj is Identifiable o && Equals(o);

    public override int GetHashCode()
        => HashCode.Combine(Id);

    public static bool operator ==(Identifiable left, Identifiable right)
        => left.Equals(right);

    public static bool operator !=(Identifiable left, Identifiable right)
        => !(left == right);

    public static bool operator <(Identifiable left, Identifiable right)
        => left.CompareTo(right) < 0;

    public static bool operator <=(Identifiable left, Identifiable right)
        => left.CompareTo(right) <= 0;

    public static bool operator >(Identifiable left, Identifiable right)
        => left.CompareTo(right) > 0;

    public static bool operator >=(Identifiable left, Identifiable right)
        => left.CompareTo(right) >= 0;
}

Program.cs

// Graph with letters (Reddit example)
DirectedGraph<string, int> charGraph = new();

// Vertices
Vertex<string> A = new("A");
Vertex<string> B = new("B");
Vertex<string> C = new("C");
Vertex<string> D = new("D");
Vertex<string> E = new("E");

// Edges (undirected)
Edge<string, int> a1 = new(A, B, 1);
Edge<string, int> a2 = new(B, A, 1);
Edge<string, int> b1 = new(B, C, 1);
Edge<string, int> b2 = new(C, B, 1);
Edge<string, int> c1 = new(C, D, 1);
Edge<string, int> c2 = new(D, C, 1);
Edge<string, int> d1 = new(D, E, 1);
Edge<string, int> d2 = new(E, D, 1);
Edge<string, int> e1 = new(A, E, 1);
Edge<string, int> e2 = new(E, A, 1);
Edge<string, int> f1 = new(B, E, 1);
Edge<string, int> f2 = new(E, B, 1);
Edge<string, int> g1 = new(B, D, 1);
Edge<string, int> g2 = new(D, B, 1);

charGraph.AddEdges(new List<Edge<string, int>>
{
    a1,
    a2,
    b1,
    b2,
    c1,
    c2,
    d1,
    d2,
    e1,
    e2,
    f1,
    f2,
    g1,
    g2
});

var pathsFromAToD = charGraph.GetPathsBetween(A, D).ToList();
foreach (var path in pathsFromAToD)
{
    Console.WriteLine(string.Join(" | ", path));
}
/*
    Output:
    (A) -> (B) (1) | (B) -> (C) (1) | (C) -> (D) (1)
    (A) -> (B) (1) | (B) -> (E) (1) | (E) -> (D) (1)
    (A) -> (B) (1) | (B) -> (D) (1)
    (A) -> (E) (1) | (E) -> (D) (1)
    (A) -> (E) (1) | (E) -> (B) (1) | (B) -> (C) (1) | (C) -> (D) (1)
    (A) -> (E) (1) | (E) -> (B) (1) | (B) -> (D) (1)
*/

Vertex.cs

public class Vertex<TVertex> : Identifiable
    where TVertex : IComparable<TVertex>, IEquatable<TVertex>
{
    public Vertex(TVertex value) : base()
    {
        Value = value;
    }

    public TVertex? Value { get; private set; }
    public bool Visited { get; private set; }
    public int? Distance { get; private set; }
    
    // BFS shenanigans, might need a rework
    public void Visit(int distance)
    {
        if (!Visited)
        {
            Visited = true;
            Distance = distance;
        }
    }

    public void Reset()
    {
        Visited = false;
        Distance = null;
    }

    public override string ToString()
        => Value is null
            ? "(null)"
            : $"({Value})";
}