バランス重視グラフ

Question

は、私はこのように見ている辺の集合を持っています。 「バランスのとれた」の意味では、どの頂点にも同じエッジ数があることを意味します。現在のコードは

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があるかどうかをチェックします。前のステップでチェックされているので、ここでカウントを確認する必要はありません。