从文本文件创建连接列表

Question

所以我有这个问题。我想在从文本文件创建的列表列表中查找所有连接。我的文件中的示例数据：

ANALYTICAL_BALANCE BFG_DEPOSIT
CUSTOMER_DETAIL BALANCE
BFG_2056 FFD_15
BALANCE BFG_16
BFG_16 STAT_HIST
ANALYTICAL_BALANCE BFG_2056
CUSTOM_DATA AND_11
AND_11 DICT_DEAL
DICT_DEAL BFG_2056

我使用这个代码创建列表列表

data = [line.split() for line in open('data.txt')

我得到这样的东西：

[[ANALYTICAL_BALANCE,BFG_DEPOSIT],[CUSTOMER_DETAIL,BALANCE],[BFG_2056, FFD_15],[BALANCE,BFG_16],[BFG_16,STAT_HIST],[ANALYTICAL_BALANCE,BFG_2056],[CUSTOM_DATA,AND_11],[AND_11,DICT_DEAL],[DICT_DEAL,BFG_2056]]

所以我想要的是我们从数据中获取第一个列表：
[分析余额，BFG存款]
我们尝试在其他列表中查找BFG_存款，但BFG_存款必须放在第一位。
因此，我们可以看到我们没有任何联系。
然后我们再次尝试查找[CUSTOMER_DETAIL，BALANCE]，得到[CUSTOMER_DETAIL，BALANCE，BFG_16，STAT_HIST]。我们这样做，只要有连接，并为每个列表。如果没有，我们将返回这些连接的列表。
我第一次使用此数据创建dict并使用以下代码找到所有路径时：

def get_path(key,my_dict):
    if key not in my_dict:
        return None
    result = []
    curr = key
    while curr and len(result) <= len(my_dict):
        result.append(curr)
        curr = my_dict.get(curr,None)
        curr = key
    return result

for key,item in data.items():
    final[key]=get_path('{}'.format(key),data)

但我有钥匙的复本，必须保留，所以字典就不存在了。我尝试使用递归，但没有用

def get_simple_path(item, main_list, result):
    result.append(item[0])
    for i in main_list:
        if i[0] == item[1]:
            get_simple_path(i, main_list, result)

wynik = []

for i in data:
    result=[]
    wynik.append(get_simple_path(i,data,result))

有人建议我使用链表实现这个功能，但我仍然不知道如何找到所有连接。我要查找的输出如下所示：
那么对于这个数据呢

[[ANALYTICAL_BALANCE,BFG_DEPOSIT],[CUSTOMER_DETAIL,BALANCE],[BFG_2056, FFD_15],[BALANCE,BFG_16],[BFG_16,STAT_HIST],[ANALYTICAL_BALANCE,BFG_2056],[CUSTOM_DATA,AND_11],[AND_11,DICT_DEAL],[DICT_DEAL,BFG_2056]]

我希望所有连接都如下所示：

[

[ANALYTICAL_BALANCE,BFG_DEPOSIT],
[CUSTOMER_DETAIL,BALANCE,BFG_16,STAT_HIST],
[BFG_2056,FFD_15],
[BALANCE,BFG_16,STAT_HIST],
[ANALYTICAL_BALANCE,BFG_2056,FFD_15],
[CUSTOM_DATA,AND_11,DICT_DEAL,BFG_2056,FFD_15],
[AND_11,DICT_DEAL,BFG_2056,FFD_15],
[DICT_DEAL,BFG_2056,FFD_15]
]

Answer 1

一种常见的方法是创建邻接列表。这将是一个由节点标签键控的字典，其值为相邻标签的列表

下面是一个可能的实现：

def create_adj(edges):
    adj = {}   # or use defaultdict(list) to avoid `if` in the loop below
    for a, b in edges:
        if not a in adj:
            adj[a] = []
        if not b in adj:
            adj[b] = []
        adj[a].append(b)
    return adj

def all_paths(adj):
    def recur(path):
        node = path[-1]
        neighbors = [neighbor for neighbor in adj[node] if not neighbor in path]
        if not neighbors:
            yield path
        for neighbor in neighbors:
            yield from recur(path + [neighbor])

    for node in adj:
        yield from recur([node])

下面是一个运行示例：

data = [
    ["ANALYTICAL_BALANCE","BFG_DEPOSIT"],
    ["CUSTOMER_DETAIL","BALANCE"],
    ["BFG_2056", "FFD_15"],
    ["BALANCE","BFG_16"],
    ["BFG_16","STAT_HIST"],
    ["ANALYTICAL_BALANCE","BFG_2056"],
    ["CUSTOM_DATA","AND_11"],
    ["AND_11","DICT_DEAL"],
    ["DICT_DEAL","BFG_2056"]
]

adj = create_adj(data)

print([path for path in all_paths(adj) if len(path) > 1])

请注意all_paths还将包括长度为1的路径，这就是为什么在最终打印输出中，这些路径会被排除在长度条件之外