2012-04-05 48 views
6

我有一个双向图,我正在寻找最有效的迭代方法将其分成连接组件。我的递归版本已经开始在大型数据集上溢出堆栈。我愿意从任何语言/伪代码移植,但为了完整性,我将在C#中编写代码。迭代连接组件算法

我现有的代码专门用于我的数据类型。一个分区是蛋白质,另一个是光谱。 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])); 
    } 
} 
+0

发布你的递归方法,这里的某个人会将它翻译成一个迭代方法给你。 – Brannon 2012-04-05 17:15:22

+2

当递归吃太多堆栈时,作为第一次尝试保持相同的算法,您可以尝试将递归更改为从*栈*中消耗数据(通过“pop”)的循环(对相同函数的调用变成对该函数所需参数的堆栈)。当然,对于“堆栈”,我的意思是一个用户实现了LIFO列表,这需要一点点工作,但这种方式受限于堆而不是堆栈。 (也许这只适用于尾递归吗?我必须考虑它......) – ShinTakezou 2012-04-05 17:15:23

+0

“components”,你的意思是子图吗? – Beta 2012-04-05 17:20:48

回答

5

这里有一个助手类,它拥有一个无向图,并允许获得它的连接部件(反复)的例子:

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>>来保存节点和弧线,所以与你的方法非常相似)

+0

你好,有没有一个适用于线条的版本(即有起点和终点)?建议非常感谢 – BKSpurgeon 2017-07-10 04:51:01

+0

嗨,使用'g.DepthFirstSearch(startPoint).ToList()'你会得到连接到起点节点的节点列表。然后,您可以检查endPoint是否存在于该列表中,如果是这种情况,则表示startPoint连接到endPoint。 – digEmAll 2017-07-11 08:55:43