Алгоритм итерационных подключаемых компонентов

Question

У меня есть двудольный граф, и я ищу наиболее эффективный итеративный способ разделить его на подключенные компоненты. Моя рекурсивная версия начала переполнять стек большими наборами данных. Я готов переносить с любого языка/псевдокода, но для полноты я буду кодировать в C#.

Мой существующий код специализирован для моих типов данных. Одна перегородка - это белки, другая - спектры. Map and 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 предложил переделать стопку в кучу, и она отлично работает. Я использовал метод DepthFirstSearch из примера 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

Вот пример вспомогательного класса, который содержит неориентированный граф и позволяет получить компоненты связности его (итеративно):

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>>, чтобы удерживать узлы и дуги, поэтому очень похож на ваш подход)