我有一个双向图,我正在寻找最有效的迭代方法将其分成连接组件。我的递归版本已经开始在大型数据集上溢出堆栈。我愿意从任何语言/伪代码移植,但为了完整性,我将在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]));
}
}
发布你的递归方法,这里的某个人会将它翻译成一个迭代方法给你。 – Brannon 2012-04-05 17:15:22
当递归吃太多堆栈时,作为第一次尝试保持相同的算法,您可以尝试将递归更改为从*栈*中消耗数据(通过“pop”)的循环(对相同函数的调用变成对该函数所需参数的堆栈)。当然,对于“堆栈”,我的意思是一个用户实现了LIFO列表,这需要一点点工作,但这种方式受限于堆而不是堆栈。 (也许这只适用于尾递归吗?我必须考虑它......) – ShinTakezou 2012-04-05 17:15:23
“components”,你的意思是子图吗? – Beta 2012-04-05 17:20:48