1

我有一个通用列表说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 :- 从手机上发布这个..所以请原谅格式错误

4

1 回答 1

0

这是解决方案：

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;
    }
}
于 2013-01-30T13:28:40.407 回答