创建群集所需的 C# 算法

Question

我有一个通用列表说List<TransactionInfo>

TransactionInfo类有三个属性：-

public long TransactionId { get; set; }
public string BuyerName { get; set; }  
public string SellerName { get; set; }

如果以下是我列表中的数据：-

1 A B   
2 A C
3 A D
4 G H
5 C M
6 D E
7 A F
8 H L
9 L R
10 Y Z

然后，我想根据成员之间的事务创建组集群。我想编写应该返回新列表的 LINQ 查询

ClusterInfo 类包含一个属性：-

public List<TransactionInfo> Transactions { get; set; }

List<ClusterInfo>应包含：-

集群[0]：-

1 A B
2 A C
3 A D
5 C M
6 D E
7 A F

集群[1]

4 G H
8 H L
9 L R

集群[2]

10 Y Z

如何选择这些新列表：-所有直接或间接的买家/卖家都应该是一个集群的一部分。

谁能帮我编写 LINQ 查询来实现这一点。如果不是 LINQ，那么简单的 for 循环解决方案也就足够了。

PS ：- 从移动设备发布此内容.. 所以请原谅格式错误

Answer 1

这是解决方案：

static public void Main()
{
    // Example of dataset
    List<TransactionInfo> transactionInfos = new List<TransactionInfo>()
    {
        new TransactionInfo(1, "A", "B"),
        new TransactionInfo(2, "A", "C"),
        new TransactionInfo(3, "A", "D"),
        new TransactionInfo(4, "G", "H"),
        new TransactionInfo(5, "C", "M"),
        new TransactionInfo(6, "D", "E"),
        new TransactionInfo(7, "A", "F"),
        new TransactionInfo(8, "H", "L"),
        new TransactionInfo(9, "L", "R"),
        new TransactionInfo(10, "Y", "Z"),
    };
    // Creates the graph and add the arcs
    UndirectedGraph<string> graph = new UndirectedGraph<string>();
    foreach (TransactionInfo transactionInfo in transactionInfos)
        graph.AddArc(transactionInfo.SellerName, transactionInfo.BuyerName);
    var result = (from clusterByNode in graph.GetConnectedComponents()  // Gets the connected components
                  select (from transactionInfo in transactionInfos  // Gets the transaction infos
                          join node in clusterByNode on transactionInfo.BuyerName equals node  // Joins the transactionInfo with the node in the connected component
                          select transactionInfo).ToList()).ToList();
}

与类：

public class TransactionInfo
{
    public long TransactionId { get; set; }
    public string BuyerName { get; set; }
    public string SellerName { get; set; }
    public TransactionInfo(long transactionId, string buyerName, string sellerName)
    {
        TransactionId = transactionId;
        BuyerName = buyerName;
        SellerName = sellerName;
    }
}

以及，查找连接组件的类：

public class UndirectedGraph<T>
{
    private Dictionary<T, HashSet<T>> linkedNodes = new Dictionary<T, HashSet<T>>();
    public void AddNode(T node)
    {
        if (!linkedNodes.ContainsKey(node))
            linkedNodes.Add(node, new HashSet<T>());
    }
    public void AddArc(T node1, T node2)
    {
        if (!linkedNodes.ContainsKey(node1))
            linkedNodes.Add(node1, new HashSet<T>());
        linkedNodes[node1].Add(node2);
        if (!linkedNodes.ContainsKey(node2))
            linkedNodes.Add(node2, new HashSet<T>());
        linkedNodes[node2].Add(node1);
    }
    public IEnumerable<HashSet<T>> GetConnectedComponents()
    {
        HashSet<T> visitedNodes = new HashSet<T>();
        foreach (T nodeToVisit in linkedNodes.Keys)
        {
            if (!visitedNodes.Contains(nodeToVisit))
            {
                HashSet<T> connectedComponent = GetConnectedComponent(nodeToVisit);
                visitedNodes.UnionWith(connectedComponent);
                yield return connectedComponent;
            }
        }
    }
    private HashSet<T> GetConnectedComponent(T from)
    {
        HashSet<T> result = new HashSet<T>();
        Stack<T> nodesToVisit = new Stack<T>();
        nodesToVisit.Push(from);
        result.Add(from);
        while (nodesToVisit.Count != 0)
        {
            T nodeToVisit = nodesToVisit.Pop();
            foreach (T linkedNode in linkedNodes[nodeToVisit])
            {
                if (!result.Contains(linkedNode))
                {
                    nodesToVisit.Push(linkedNode);
                    result.Add(linkedNode);
                }
            }
        }
        return result;
    }
}