繰り返し接続されたコンポーネントアルゴリズム

Question

私は二部グラフを持っていますが、私はそれを接続されたコンポーネントに分割する最も効率的な方法を探しています。私の再帰的なバージョンは、大きなデータセットでスタックをオーバーフローし始めました。私は任意の言語/擬似コードから移植するつもりですが、完全性のために私はC＃でコーディングします。

私の既存のコードは自分のデータ型に特化しています。 1つの区画はタンパク質であり、他の区画はスペクトルである。 MapとSetはC++ stdlibワークスタイルです。

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; 
} 

ShinTakezouがヒープ上にスタックを置くようにリファクタリングしたと示唆しました。私はdigEmAllの例からDepthFirstSearchアプローチを使用しました。

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

ここで無向グラフを保持し、それの連結成分（繰り返し）を取得することを可能にするヘルパークラスの例です：

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; 
    } 
} 

は使用方法：

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(); 

} 

あなたは可能性がありマップの代わりにGraph<>クラスを使用するか、マップに固執したい場合は、理解しやすいコードを見てください（クラス内ではDictionary<T,HashSet<T>>はノードとアークを保持するので、あなたのアプローチと非常によく似ています）