KosarajuTests.cs

using Algorithms.Graph;
using DataStructures.Graph;
using NUnit.Framework;
using FluentAssertions;
using System.Collections.Generic;
using System.Linq;

namespace Algorithms.Tests.Graph;

public class KosarajuTests
{

    [Test]
    public void GetRepresentativesTest()
    {
        // Create a graph with some SCC. 
        var graph = new DirectedWeightedGraph<int>(10);

        var vertex1 = graph.AddVertex(1);
        var vertex2 = graph.AddVertex(2);
        var vertex3 = graph.AddVertex(3);
        var vertex4 = graph.AddVertex(4);
        var vertex5 = graph.AddVertex(5);
        var vertex6 = graph.AddVertex(6);
        var vertex7 = graph.AddVertex(7);

        graph.AddEdge(vertex1, vertex2, 1);
        graph.AddEdge(vertex2, vertex3, 1);
        graph.AddEdge(vertex3, vertex1, 1);
        graph.AddEdge(vertex3, vertex2, 1);
        graph.AddEdge(vertex2, vertex4, 1);
        graph.AddEdge(vertex4, vertex5, 1);
        graph.AddEdge(vertex5, vertex4, 1);
        graph.AddEdge(vertex5, vertex6, 1);

        // Run the agorithm and obtain the representative vertex of the SCC to which each vertex belongs.
        Dictionary<Vertex<int>,Vertex<int>> result = Kosaraju<int>.GetRepresentatives(graph);

        // Check every Vertex belongs to a SCC
        result.Should().ContainKey(vertex1);
        result.Should().ContainKey(vertex2);
        result.Should().ContainKey(vertex3);
        result.Should().ContainKey(vertex4);
        result.Should().ContainKey(vertex5);
        result.Should().ContainKey(vertex6);
        result.Should().ContainKey(vertex7);

        // There should be 4 SCC: {1,2,3}, {4,5}, {6} and {7}
        // Vertices 1, 2 and 3 are a SCC
        result[vertex1].Should().Be(result[vertex2]).And.Be(result[vertex3]);

        // Vertices 4 and 5 are another SCC
        result[vertex4].Should().Be(result[vertex5]);

        // And the should have a different representative vertex
        result[vertex1].Should().NotBe(result[vertex4]);

        // Vertices 6 and 7 are their own SCC
        result[vertex6].Should().Be(vertex6);
        result[vertex7].Should().Be(vertex7);
    }

    [Test]
    public void GetSccTest()
    {
        // Create a graph with some SCC. 
        var graph = new DirectedWeightedGraph<int>(10);

        var vertex1 = graph.AddVertex(1);
        var vertex2 = graph.AddVertex(2);
        var vertex3 = graph.AddVertex(3);
        var vertex4 = graph.AddVertex(4);
        var vertex5 = graph.AddVertex(5);
        var vertex6 = graph.AddVertex(6);
        var vertex7 = graph.AddVertex(7);

        graph.AddEdge(vertex1, vertex2, 1);
        graph.AddEdge(vertex2, vertex3, 1);
        graph.AddEdge(vertex3, vertex1, 1);
        graph.AddEdge(vertex3, vertex2, 1);
        graph.AddEdge(vertex2, vertex4, 1);
        graph.AddEdge(vertex4, vertex5, 1);
        graph.AddEdge(vertex5, vertex4, 1);
        graph.AddEdge(vertex5, vertex6, 1);

        // Run the algorithm and get SCC as lists of vertices. 
        var scc = Kosaraju<int>.GetScc(graph);

        // There should be 4 SCC: {1,2,3}, {4,5}, {6} and {7}
        scc.Should().HaveCount(4);

        // Vertices 1, 2 and 3 are a SCC
        scc.First(c => c.Contains(vertex1)).Should().Contain(vertex2).And.Contain(vertex3);

        // Vertices 4 and 5 are another SCC
        scc.First(c => c.Contains(vertex4)).Should().Contain(vertex5);

        // Vertices 6 and 7 are their own SCC
        scc.First(c => c.Contains(vertex6)).Should().HaveCount(1);
        scc.First(c => c.Contains(vertex7)).Should().HaveCount(1);
    }
}