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

Question

我有一个 pandas DataFrame，其中包含我最终想要连接并变成类似对象的图形的节点行。为此，我首先想到将此 DataFrame 转换为类似于邻接列表的内容，以便稍后轻松地从中创建图形。我有以下内容：

一个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 中的节点，则 returns 为真（这稍后将成为从节点 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"])

不久，如果节点i的end值与节点start的值相同，则节点i后跟节点j j 如果他们 cases 重叠

基于这个 directly_follows 函数，我想为我的 DataFrame df 创建一个额外的列作为邻接列表，包含节点 i 的列表 id i

之后的节点值

因此我想要的结果是：

    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]        []

基本上我想首先将列 adjacency_list 创建为空列表，然后循环遍历 Dataframe 的行，如果对于行 i 和 j directly_follows(row_i, row_j) returns 对，将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"])

现在首先，这个returns一个错误

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

其次，我非常怀疑这是解决这个问题的最 pythonic 和最有效的方法，因为我的实际 DataFrame 包含大约 9000 行，这将提供大约 8100 万次比较。

如何用最少的时间创建邻接表？有没有比我的更快或更优雅的解决方案？

Answer 1

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

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 2

尝试：

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 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]             []

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

Create an adjacency list from a pandas Dataframe containing nodes

python

pandas

dataframe

graph

adjacency-list

输出