6

我有一个二分图，我正在寻找最有效的迭代方式将其划分为连接的组件。我的递归版本已经开始在大型数据集上溢出堆栈。我愿意从任何语言/伪代码移植，但为了完整起见，我将使用 C# 进行编码。

我现有的代码专门用于我的数据类型。一个分区是蛋白质，另一个是光谱。Map 和 Set 是 C++ 标准库的类似工作。

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]));
    }
}
4

1 回答 1

6

这是一个辅助类的示例，它包含一个无向图并允许（迭代地）获取它的连接组件：

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>>保存节点和弧，因此非常类似于你的方法）

于 2012-04-05T18:20:54.257 回答