c# - 迭代连通分量算法

Question

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

我现有的代码专用于我的数据类型。一个分区是蛋白质，另一个是光谱。 Map 和 Set 是 C++ stdlib workalikes。

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<> class 而不是你的 map ，或者如果你想坚持使用你的 map ，请查看非常容易理解的代码(在类中它使用 Dictionary<T,HashSet<T>> 来保存节点和弧，因此与你的非常相似方法)