How to sort list of tuples that contain a directed acyclical graph?

Question

I want to sort a tuple list that contains a directed graph. The list looks like this: List<(string, List)> tupleList;

Im trying to use a simple IComparer but i cannot get the test cases to pass. I have no idea why.

public class Class1
{
    public static List<(string, List<string>)> OrderList(List<(string, List<string>)> tupleList)
    {
        // Use the custom TupleComparer to sort the tupleList
        tupleList.Sort(new TupleComparer());

        return tupleList;
    }
}
public class TupleComparer : IComparer<(string, List<string>)>
{
    public int Compare((string, List<string>) x, (string, List<string>) y)
    {
        if (x.Item2.Contains(y.Item1))
        {
            return -1; // x should come after y
        }
        else if (y.Item2.Contains(x.Item1))
        {
            return 1; // x should come before y
        }
        else
        {
            // If no dependencies found, compare based on their original positions
            return 0;
        }
    }
}

These are my tests. All pass but one.

public class LinkedListTests
{
    [Test]
    [TestCaseSource(nameof(GetTupleLists))]
    public void Test1(List<(string, List<string>)> tupleList)
    {
        var result = Class1.OrderList(tupleList);

        Assert.AreEqual(result[0].Item1, "p1");
        Assert.AreEqual(result[1].Item1, "p3");
        Assert.AreEqual(result[2].Item1, "p4");
    }
    private static IEnumerable<List<(string, List<string>)>> GetTupleLists()
    {
        // Return different instances of the tupleList for test cases
        yield return new List<(string, List<string>)>
        {
            ("p1", new List<string> { "p2", "p3" }),
            ("p3", new List<string> { "p4" }),
            ("p4", new List<string> { "p5", "p6" })
        };
        yield return new List<(string, List<string>)>
        {
            ("p1", new List<string> { "p2", "p3" }),
            ("p4", new List<string> { "p5","p6"}),
            ("p3", new List<string> { "p4" })
        };
        yield return new List<(string, List<string>)>
        {
            ("p3", new List<string> { "p4" }),
            ("p1", new List<string> { "p2", "p3" }),
            ("p4", new List<string> { "p5","p6"})
        };
        yield return new List<(string, List<string>)>
        {
            ("p3", new List<string> { "p4" }),
            ("p4", new List<string> { "p5","p6"}),
            ("p1", new List<string> { "p2", "p3" })
        };
        yield return new List<(string, List<string>)>
        {
            ("p4", new List<string> { "p5","p6"}),
            ("p1", new List<string> { "p2", "p3" }),
            ("p3", new List<string> { "p4" })
        };
        yield return new List<(string, List<string>)>
        {
            ("p4", new List<string> { "p5","p6"}),
            ("p3", new List<string> { "p4" }),
            ("p1", new List<string> { "p2", "p3" })
        };
    }
}

Answer 1

The problem here is that this will compare only directly connected nodes (i.e. one having an edge between them). Consider the first test case:

new List<(string, List<string>)>
{
    ("p1", new List<string> { "p2", "p3" }),
    ("p3", new List<string> { "p4" }),
    ("p4", new List<string> { "p5", "p6" })
};

Since p1 and p4 does not contain a direct edge they will be considered equal by comparer while clearly (based on your logic) p1 is less then p4. Also it introduces quite a conundrum i.e. p1 == p4, p1 < p3 and p3 < p4, which breaks transitivity. This approach will work if your List will contain all "descendant" nodes.

P.S.

If // x should come after y then you should return 1 not -1 because default order is ascending, though this will not match the test case assertion.