从包含节点的数据帧创建邻接列表

Question

我有一个pandas数据框，其中包含了我最终想要连接成一个类似于图形的对象的节点行。为此，我首先想到将这个数据帧转换成类似于邻接列表的东西，以便以后可以轻松地从中创建一个图形。我有以下资料：

数据帧：

df = pd.DataFrame({"id": [0, 1, 2, 3, 4, 5, 6],
                   "start": ["A", "B", "D", "A", "X", "F", "B"],
                   "end": ["B", "C", "F", "G", "X", "X", "E"],
                   "cases": [["c1", "c2", "c44"], ["c2", "c1", "c3"], ["c4"], ["c1", ], ["c1", "c7"], ["c4"], ["c44", "c7"]]})

看起来是这样的：

    id  start   end     cases            
0   0   A       B       [c1, c2, c44]    
1   1   B       C       [c2, c1, c3]     
2   2   D       F       [c4]             
3   3   A       G       [c1]             
4   4   X       X       [c1, c7]         
5   5   F       X       [c4]             
6   6   B       E       [c44, c7]        

一个函数directly_follows(i, j)，如果第i行中的节点后跟第j行中的节点，则该函数返回true（这将是从节点i到节点j的图中的一条有向边）：

def directly_follows(row1, row2):
    return close(row1, row2) and case_overlap(row1, row2)

def close(row1, row2):
    return row1["end"] == row2["start"]

def case_overlap(row1, row2):
    return not set(row1["cases"]).isdisjoint(row2["cases"])

简而言之，如果nodei的end值与nodej的start值相同，并且它们的cases重叠，那么nodei后面紧跟nodej

基于这个directly_follows函数，我想为我的DataFrame df创建一个额外的列，它充当一个邻接列表，为节点i包含一个列表，其中包含紧跟在i之后的节点的id值

因此，我期望的结果是：

    id  start   end     cases            adjacency_list
0   0   A       B       [c1, c2, c44]    [1, 6]
1   1   B       C       [c2, c1, c3]     []
2   2   D       F       [c4]             [5]
3   3   A       G       [c1]             []
4   4   X       X       [c1, c7]         []
5   5   F       X       [c4]             []
6   6   B       E       [c44, c7]        []

基本上，我想首先将列邻接列表创建为空列表，然后在数据帧的行中循环，如果行i和j直接跟随（行I，行j）返回True，则将j的id添加到i的邻接列表中

我是这样做的：

def connect(data):
    data["adjacency_list"] = np.empty((len(data), 0)).tolist()
    
    for i in range(len(data)):
        for j in range(len(data)):
            if i != j:
                if directly_follows(data.iloc[i], data.iloc[j]):
                    data.iloc[i]["adjacency_list"] = data.iloc[i]["adjacency_list"].append(data.iloc[i]["id"])

首先，这将返回一个错误

SettingWithCopyWarning: A value is trying to be set on a copy of a slice from a DataFrame

第二，我非常怀疑这是解决这个问题的最具python风格和效率的方法，因为我的实际数据帧由大约9000行组成，这将提供大约8100万个比较

如何以最省时的方式创建邻接列表？有没有比我更快或更优雅的解决方案

Answer 1

尝试：

k=0
def test(x):
    global k
    k+=1
    test_df = df[k:]
    return list(test_df[test_df['start'] == x].index)
df['adjancy_matrix'] = df.end.apply(test,1)

输出：

   id start end        cases adjancy_matrix
0   0     A   B  [c1,c2,c44]         [1, 6]
1   1     B   C   [c2,c1,c3]             []
2   2     D   F         [c4]            [5]
3   3     A   G         [c1]             []
4   4     X   X      [c1,c7]             []
5   5     F   X         [c4]             []
6   6     B   E     [c44,c7]             []

Answer 2

一个选择是应用以下函数-它不是完全矢量化的，因为数据帧不特别喜欢嵌入列表之类的可变对象，而且我认为不能以矢量化的方式应用集合操作。不过，它确实减少了所需的比较次数

def f(x):
    check = df[(x["end"] == df["start"])]
    return [
        row["id"]
        for i, row in check.iterrows()
        if not set(row["cases"]).isdisjoint(x["cases"])
    ]


df["adjacency_list"] = df.apply(f, axis=1)

或者，作为一个大lambda函数：

df["adjacency_list"] = df.apply(
    lambda x: [
        row["id"]
        for i, row in df[(x["end"] == df["start"])].iterrows()
        if not set(row["cases"]).isdisjoint(x["cases"])
    ],
    axis=1,
)

输出

   id start end          cases adjacency_list
0   0     A   B  [c1, c2, c44]         [1, 6]
1   1     B   C   [c2, c1, c3]             []
2   2     D   F           [c4]            [5]
3   3     A   G           [c1]             []
4   4     X   X       [c1, c7]            [4]
5   5     F   X           [c4]             []
6   6     B   E      [c44, c7]             []

Answer 3

自连接选项：

df['adjacency_list'] = df.apply(lambda s: df[(df['start'] == s.end) &
                                             (df['id'] != s.id)].index.tolist(), axis=1)
print(df)

输出：

   id start end          cases adjacency_list
0   0     A   B  [c1, c2, c44]         [1, 6]
1   1     B   C   [c2, c1, c3]             []
2   2     D   F           [c4]            [5]
3   3     A   G           [c1]             []
4   4     X   X       [c1, c7]             []
5   5     F   X           [c4]            [4]
6   6     B   E      [c44, c7]             []