c# - 如何根据层次结构对对象进行排序？

Question

给定 2 个对象 People 和 Relation:

public class People
{   
    public int id ;
    public string externalId;
    public PostalInfo postalInformation;
}

public class Relation
{        
    public int id ;
    public int type ;
    public string sourceExternalId ;
    public string destExternalId ;
}

People 存储某人信息的位置。
Relation 存储了 2 个 People 之间的联系。

如何根据等级对人员进行排序，从“最老的”(较深的)到不太重要的？

旧的，我指的是与其他元素绑定(bind)较少的元素。因此，在订购时我可以验证和创建这些元素而不会丢失引用。但由于验证是由人进行的，我迫不及待地等待所有的人都通过验证来一次提交它们。

var peoplesAwaitingValidation =
    new List<People> {
        new People{ id = 1 , externalId = "A" },
        new People{ id = 2 , externalId = "B" },
        new People{ id = 3 , externalId = "C" },
        new People{ id = 4 , externalId = "D" },
        new People{ id = 5 , externalId = "E" },
        new People{ id = 6 , externalId = "F" },
    };

var relationsAwaitingValidation =
    new List<Relation> {
        new Relation{ id = 1 , sourceExternalId = "A", destExternalId = "B" },
        new Relation{ id = 2 , sourceExternalId = "A", destExternalId = "C" },
        new Relation{ id = 3 , sourceExternalId = "A", destExternalId = "D" },
        new Relation{ id = 4 , sourceExternalId = "E", destExternalId = "A" },
        new Relation{ id = 3 , sourceExternalId = "E", destExternalId = "B" }
    };

//Expected result :
var orderedPeoplesAwaitingValidation = new List<People> {
                                                    // Weight
        new People{ id = 6 , externalId = "F" },    // 0 
        new People{ id = 5 , externalId = "E" },    // 1
        new People{ id = 1 , externalId = "A" },    // 2 
        new People{ id = 3 , externalId = "C" },    // 3
        new People{ id = 4 , externalId = "D" },    // 3
        new People{ id = 2 , externalId = "B" },    // 5
    };

我想到的图形表示:

1        2        3   // <==  Weight
E  --->  A  --->  B
            --->  C
            --->  D
   --->  B

F==0

mcve and attempt

Answer 1

您应该对您的关系进行多次迭代，以找到从我们知道权重的点开始的新关系。

Dictionary<string, int> weights = peoplesAwaitingValidation
    .Where(x => relationsAwaitingValidation
        .Count(o => o.destExternalId == x.externalId) == 0)
    .ToDictionary(o => o.externalId, o => 0);
int processed = 0;
while (processed < relationsAwaitingValidation.Count - 1)
    foreach (Relation r in relationsAwaitingValidation)
        if (weights.ContainsKey(r.sourceExternalId) &&
           !weights.ContainsKey(r.destExternalId))
        {
            weights.Add(r.destExternalId, weights[r.sourceExternalId] + 1);
            processed++;
        }

注意:此代码假定始终至少有一个根用户与其没有任何联系。