Thuật toán thành phần kết nối lặp lại

Question

Tôi có biểu đồ hai chân và tôi đang tìm cách lặp lại hiệu quả nhất để chia thành các thành phần được kết nối. Phiên bản đệ quy của tôi đã bắt đầu tràn ngăn xếp trên các tập dữ liệu lớn. Tôi sẵn sàng chuyển từ bất kỳ ngôn ngữ/mã giả nào, nhưng để hoàn thành, tôi sẽ được mã hóa trong C#.

Mã hiện tại của tôi chuyên về các loại dữ liệu của tôi. Một phân vùng là protein, một là phổ. Bản đồ và Set là C++ stdlib workalikes.

void recursivelyAssignProteinToCluster (long proteinId, 
             long clusterId, 
             Set<long> spectrumSet, 
             Map<long, Set<long>> spectrumSetByProteinId, 
             Map<long, Set<long>> proteinSetBySpectrumId, 
             Map<long, long> clusterByProteinId) 
{ 
    // try to assign the protein to the current cluster 
    var insertResult = clusterByProteinId.Insert(proteinId, clusterId); 
    if (!insertResult.WasInserted) 
     return; 

    // recursively add all "cousin" proteins to the current cluster 
    foreach (long spectrumId in spectrumSet) 
     foreach (var cousinProteinId in proteinSetBySpectrumId[spectrumId]) 
     { 
      if (proteinId != cousinProteinId) 
      { 
       Set<long> cousinSpectrumSet = spectrumSetByProteinId[cousinProteinId]; 
       recursivelyAssignProteinToCluster(cousinProteinId, 
                clusterId, 
                cousinSpectrumSet, 
                spectrumSetByProteinId, 
                proteinSetBySpectrumId, 
                clusterByProteinId); 
      } 
     } 
} 

Map<long, long> calculateProteinClusters (NHibernate.ISession session) 
{ 
    var spectrumSetByProteinId = new Map<long, Set<long>>(); 
    var proteinSetBySpectrumId = new Map<long, Set<long>>(); 

    var query = session.CreateQuery("SELECT pi.Protein.id, psm.Spectrum.id " + GetFilteredQueryString(FromProtein, ProteinToPeptideSpectrumMatch)); 

    foreach (var queryRow in query.List<object[]>()) 
    { 
     long proteinId = (long) queryRow[0]; 
     long spectrumId = (long) queryRow[1]; 

     spectrumSetByProteinId[proteinId].Add(spectrumId); 
     proteinSetBySpectrumId[spectrumId].Add(proteinId); 
    } 

    var clusterByProteinId = new Map<long, long>(); 
    int clusterId = 0; 

    foreach (var pair in spectrumSetByProteinId) 
    { 
     long proteinId = pair.Key; 

     // for each protein without a cluster assignment, make a new cluster 
     if (!clusterByProteinId.Contains(proteinId)) 
     { 
      ++clusterId; 

      recursivelyAssignProteinToCluster(proteinId, 
               clusterId, 
               pair.Value, 
               spectrumSetByProteinId, 
               proteinSetBySpectrumId, 
               clusterByProteinId); 
     } 
    } 

    return clusterByProteinId; 
} 

Khi ShinTakezou đề xuất tôi đã tái cấu trúc để xếp chồng lên đống và hoạt động tốt. Tôi đã sử dụng phương pháp DepthFirstSearch từ ví dụ của digEmAll.

var clusterByProteinId = new Map<long, long>(); 
int clusterId = 0; 
var clusterStack = new Stack<KeyValuePair<long, Set<long>>>(); 

foreach (var pair in spectrumSetByProteinId) 
{ 
    long proteinId = pair.Key; 

    if (clusterByProteinId.Contains(proteinId)) 
     continue; 

    // for each protein without a cluster assignment, make a new cluster 
    ++clusterId; 
    clusterStack.Push(new KeyValuePair<long, Set<long>>(proteinId, spectrumSetByProteinId[proteinId])); 
    while (clusterStack.Count > 0) 
    { 
     var kvp = clusterStack.Pop(); 

     // try to assign the protein to the current cluster 
     var insertResult = clusterByProteinId.Insert(kvp.Key, clusterId); 
     if (!insertResult.WasInserted) 
      continue; 

     // add all "cousin" proteins to the current cluster 
     foreach (long spectrumId in kvp.Value) 
      foreach (var cousinProteinId in proteinSetBySpectrumId[spectrumId]) 
       if (!clusterByProteinId.Contains(cousinProteinId)) 
        clusterStack.Push(new KeyValuePair<long, Set<long>>(cousinProteinId, spectrumSetByProteinId[cousinProteinId])); 
    } 
} 

Answer 1

Dưới đây là một ví dụ về một lớp helper chứa một đồ thị vô hướng và cho phép để có được các thành phần kết nối của nó (lặp đi lặp lại):

public class Graph<T> 
{ 
    public Dictionary<T, HashSet<T>> nodesNeighbors; 
    public IEnumerable<T> Nodes 
    { 
     get { return nodesNeighbors.Keys; } 
    } 
    public Graph() 
    { 
     this.nodesNeighbors = new Dictionary<T, HashSet<T>>(); 
    } 
    public void AddNode(T node) 
    { 
     this.nodesNeighbors.Add(node, new HashSet<T>()); 
    } 
    public void AddNodes(IEnumerable<T> nodes) 
    { 
     foreach (var n in nodes) 
      this.AddNode(n); 
    } 
    public void AddArc(T from, T to) 
    { 
     this.nodesNeighbors[from].Add(to); 
     this.nodesNeighbors[to].Add(from); 
    } 
    public bool ContainsNode(T node) 
    { 
     return this.nodesNeighbors.ContainsKey(node); 
    } 
    public IEnumerable<T> GetNeighbors(T node) 
    { 
     return nodesNeighbors[node]; 
    } 
    public IEnumerable<T> DepthFirstSearch(T nodeStart) 
    { 
     var stack = new Stack<T>(); 
     var visitedNodes = new HashSet<T>(); 
     stack.Push(nodeStart); 
     while (stack.Count > 0) 
     { 
      var curr = stack.Pop(); 
      if (!visitedNodes.Contains(curr)) 
      { 
       visitedNodes.Add(curr); 
       yield return curr; 
       foreach (var next in this.GetNeighbors(curr)) 
       { 
        if (!visitedNodes.Contains(next)) 
         stack.Push(next); 
       } 
      } 
     } 
    } 
    public Graph<T> GetSubGraph(IEnumerable<T> nodes) 
    { 
     Graph<T> g = new Graph<T>(); 
     g.AddNodes(nodes); 
     foreach (var n in g.Nodes.ToList()) 
     { 
      foreach (var neigh in this.GetNeighbors(n)) 
       g.AddArc(n, neigh); 
     } 
     return g; 
    } 

    public IEnumerable<Graph<T>> GetConnectedComponents() 
    { 
     var visitedNodes = new HashSet<T>(); 
     var components = new List<Graph<T>>(); 

     foreach (var node in this.Nodes) 
     { 
      if (!visitedNodes.Contains(node)) 
      { 
       var subGraph = GetSubGraph(this.DepthFirstSearch(node)); 
       components.Add(subGraph); 
       visitedNodes.UnionWith(subGraph.Nodes); 
      } 
     } 
     return components; 
    } 
} 

Cách sử dụng:

static void Main(string[] args) 
{ 
    var g = new Graph<long>(); 
    g.AddNodes(new long[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }); 
    g.AddArc(1, 2); 
    g.AddArc(1, 3); 

    g.AddArc(9, 6); 
    g.AddArc(6, 7); 
    g.AddArc(6, 8); 

    g.AddArc(4, 5); 

    var subGraphs = g.GetConnectedComponents(); 

} 

Bạn có thể sử dụng lớp Graph<> thay vì bản đồ của bạn hoặc nếu bạn muốn gắn với bản đồ của mình, hãy xem mã khá dễ hiểu (bên trong lớp được sử dụng Dictionary<T,HashSet<T>> để giữ nút và vòng cung, vì vậy rất giống với cách tiếp cận của bạn)