6

私は2部グラフを持っており、それを連結成分に分割するための最も効率的な反復方法を探しています。私の再帰バージョンは、大きなデータセットのスタックをオーバーフローし始めました。私はどの言語/擬似コードからでも移植したいと思っていますが、完全を期すためにC＃でコーディングします。

私の既存のコードは私のデータ型に特化しています。1つのパーティションはタンパク質で、もう1つはスペクトルです。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]));
    }
}
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 に答える