如何对包含有向非循环图的元组列表进行排序？

Question

我想对包含有向图的元组列表进行排序。该列表如下所示： 列表<(string, List)> tupleList;

我尝试使用一个简单的 IComparer，但我无法让测试用例通过。我不知道为什么。

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;
        }
    }
}

这些是我的测试。全部通过，只有一个。

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

这里的问题是，这只会比较直接连接的节点（即它们之间有边的节点）。考虑第一个测试用例：

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

由于

p1

和

p4

不包含直接边，它们将被比较器视为相等，而显然（根据您的逻辑）

p1

小于

p4

。它还引入了一个相当大的难题，即

p1 == p4

，

p1 < p3

和

p3 < p4

。

附注

如果

// x should come after y

那么你应该返回

1

而不是

-1

，因为默认顺序是升序，尽管这与测试用例断言不匹配。