Python：在具有嵌套字典的组中的节点之间查找路径

Question

我有一个包含房地产历史交易记录的数据集。每个属性都有一个ID号。为了检查数据是否完整，我为每个房产确定了一个“交易链”：我选择原始买家，并通过所有中间买家/卖家组合，直到我找到最终的记录买家。对于这样的数据：

Buyer|Seller|propertyID
Bob|Jane|23
Tim|Bob|23
Karl|Tim|23

事务链将如下所示：[Jane, Bob, Tim, Karl]

我用三个数据集来做这个。第一个只包含每个房产的第一个买家的名字。第二个包含所有中间买家和卖家的名字，第三个只包含每个房产的最终买家。我使用了三个数据集，这样就可以遵循vikramls answer here给出的过程。你知道吗

在我的图形字典版本中，每个卖家都是对应买家的一个键，经常引用的find\u path函数可以找到从第一个卖家到最后一个买家的路径。问题是数据集非常大，所以我得到了一个最大递归深度到达错误。我想我可以通过在另一个字典中嵌套graph字典来解决这个问题，其中它们的键是属性id号，然后在id组中搜索路径。然而，当我尝试：

graph = {}
propertyIDgraph = {}

with open('buyersAndSellers.txt','r') as f:
    for row in f:
        propertyid, seller, buyer = row.strip('\n').split('|')
        graph.setdefault(seller, []).append(buyer)
        propertyIDgraph.setdefault(propertyid, []).append(graph)
f.close()

它将每个买家/卖家组合分配给每个房产id。我希望它只将买家和卖家分配给他们相应的房产id

Answer 1

您可以尝试以下操作。我改编自https://www.python.org/doc/essays/graphs/的链接

Transaction = namedtuple('Transaction', ['Buyer', 'PropertyId'])

graph = {}
## maybe this is a db or a file
for data in datasource:
    graph[data.seller] = Transaction(data.buyer,data.property_id)

## returns something like
## graph = {'Jane': [Transaction('Bob',23)],
##        'Bob': [Transaction('Tim',23)],
##        'Time': [Transaction('Karl',23)]}
##

def find_transaction_path(graph,  original_seller,current_owner,target_property_id path=[]):
    assert(target_property_id is not None)

    path = path + [original_seller]
    if start == end:
        return path
    if not graph.has_key(original_seller):
        return None
    shortest = None
    for node in graph[start]:
        if node not in path and node.property_id == target_property_id:
            newpath = find_shortest_path(graph, node.Buyer, current_owner, path,target_property_id)
            if newpath:
                if not shortest or len(newpath) < len(shortest):
                    shortest = newpath
    return shortest

Answer 2

我不建议附加到图中。它将附加到每个节点。最好先检查是否存在，而不是在将它附加到已经存在的对象之后。你知道吗

试试这个：

graph = {}
propertyIDgraph = {}

with open('buyersAndSellers.txt','r') as f:
    for row in f:
        propertyid, seller, buyer = row.strip('\n').split('|')
        if seller in graph.iterkeys() :
            graph[seller] = graph[seller] + [buyer]
        else:
            graph[seller] = [buyer]
        if propertyid in propertyIDgraph.iterkeys():
            propertyIDgraph[propertyid] = propertyIDgraph[propertyid] + [graph]
        else:
            propertyIDgraph[propertyid] = [graph]
f.close()

这里有一个可能有用的链接：

syntax for creating a dictionary into another dictionary in python