平衡有向图

Question

我有一组边缘看起来像这样的：

​​3210

现在我想检查我的图是平衡的。在“平衡”下，我的意思是说任何顶点都有相等数量的输入和输出边缘。我目前的代码是：

public static bool IsGraphBalanced<T>(List<Edge<T>> edges) 
{ 
    var from = new Dictionary<T, int>); 
    var to = new Dictionary<T, int>); 

    foreach (var edge in edges) 
    { 
     if (!from.ContainsKey(edge.From)) 
      from.Add(edge.From, 0); 

     if (!to.ContainsKey(edge.To)) 
      to.Add(edge.To, 0); 

     from[edge.From] += 1; 
     to[edge.To] += 1; 
    } 

    foreach (var kv in from) 
    { 
     if (!to.ContainsKey(kv.Key)) 
      return false; 
     if (to[kv.Key] != kv.Value) 
      return false; 
    } 
    // mirrored check with foreach on "to" dictionary 

    return true; 
} 

我可以用Linq替换吗？

P.S.的edges尺寸是100-150下的项目，所以我在乎的可读性，而不是性能

Answer 1

这里是一个更简洁的方式利用Enumerable类ToLookup，All，Count和Any扩展方法（我会让你决定它是否是更易读与否）：

public static bool IsGraphBalanced<T>(List<Edge<T>> edges) 
{ 
    var from = edges.ToLookup(e => e.From); 
    var to = edges.ToLookup(e => e.To); 
    return from.All(g => g.Count() == to[g.Key].Count()) 
     && to.All(g => from[g.Key].Any()); 
} 

的ToLookup方法类似于GroupBy，但产生了可重复使用的数据结构（因为我们需要2次通过）。

然后from.All(g => g.Count() == to[g.Key].Count())检查每个From是否有相应的To及其计数是否匹配。请注意，如果密钥不存在，则ILookup<TKey, TElement>索引器不会抛出异常或返回null，但会返回一个空的IEnumerable<TElement>，这允许我们合并检查。

最后to.All(g => from[g.Key].Any())检查是否每个To都有对应的From。这里没有必要检查计数，因为它们在上一步中已被检查过。