平衡有向圖

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。這裏沒有必要檢查計數，因爲它們在上一步中已被檢查過。