使用Linq構建一個圖類;你能讓這段代碼看起來更好嗎？

Question

我創建了一個不可變的簡單圖類（它不需要支持循環或多邊）。每個節點由一個整數值表示，從0到numNodes。

此代碼有效，但我認爲Linq查詢和for循環相當難看。你能想出一個更清晰的方式來填充_edges嗎？

public class Graph { 
    private IList<IList<int>> _edges; 
    public int Nodes { get; private set; 
} 

public Graph(int numNodes, IList<Tuple<int,int>> edges) { 
    Nodes = numNodes; 
    _edges = new List<IList<int>>(); 

    for(int i = 0; i < numNodes; i++) { 
     _edges.Add(new List<int>(
     (from e in edges where e.Item1 == i 
     select e.Item2).Union(
     (from e in edges where e.Item2 == i 
     select e.Item1).Distinct()))); 
    } 
} 

public IEnumerable<int> Neighbors(int node) { 
    return _edges[node]; 
} 
} 

Answer 1

什麼是這樣的：

public class Graph2 
{ 
    private IList<HashSet<int>> _edges; 

    public int Nodes { get; private set; } 

    public Graph2(int numNodes, IList<Tuple<int, int>> edges) 
    { 
     Nodes = numNodes; 
     _edges = new List<HashSet<int>>(numNodes); 
     for (int i = 0; i < numNodes; i++) 
     { 
      _edges.Add(new HashSet<int>()); 
     } 

     foreach (var edge in edges) 
     { 
      _edges[edge.Item1].Add(edge.Item2); 
      _edges[edge.Item2].Add(edge.Item1); 
     } 
    } 

    public IEnumerable<int> Neighbors(int node) 
    { 
     return _edges[node]; 
    } 
} 

使用HashSet的意思是，你不必擔心重複或有複雜的LINQ表達式。你也只能循環一次邊緣。

不幸的是，你仍然有最初的for循環來創建空的HashSets。

Answer 2

public Graph(int numNodes, IList<Tuple<int, int>> edges) 
{ 
    Nodes = numNodes; 

    _edges = Enumerable.Range(0, numNodes).Select(num => 
        edges.Where(x => x.Item1 == num).Select(x => x.Item2) 
          .Union(edges.Where(x => x.Item2 == num).Select(x => x.Item1)) 
          .Distinct().ToList() as IList<int> 
     ).ToList(); 
} 

Answer 3

下面是使用GROUP BY替代：

public Graph(int numNodes, IList<Tuple<int, int>> edges) { 
    Nodes = numNodes; 
    _edges = new IList<int>[numNodes]; 
    var groups = from e in edges 
     group e by e.Item1 into g 
     select new { Key = g.Key, Items = g.Select(s => s.Item2) }; 

    foreach (var grp in groups) { 
     _edges[grp.Key] = grp.Items.ToList(); 
    } 
} 

這將避免初始化邊緣收集的循環初期，但你必須訪問，當然鄰居時，則照顧。

也許更漂亮是：

public class Graph { 
    private IList<IEnumerable<int>> _edges; 
    public int Nodes { get; private set; }  
    public Graph(int numNodes, IList<Tuple<int, int>> edges) { 
     Nodes = numNodes; 
     _edges = new IList<int>[numNodes]; 
     var groups = from e in edges 
      group e by e.Item1 into g select g; 

     foreach (var grp in groups) { 
      _edges[grp.Key] = (from g in grp select g.Item2).ToList(); 
     } 
    } 

    public IEnumerable<int> Neighbors(int node) { 
     return _edges[node]; 
    } 
}