Pandas 中的边缘收缩

Question

我在 Windows 7

上使用 Python 2.7

从这个问题：Python networkx : edge contraction 我们知道如何使用 networkx 进行边缘收缩。但这也可以使用 pandas 吗？

假设我有一个 dataframe df 表示从 fld1 到 fld2 的有向边，而 r_val 是该连接的权重。

这是 df 定义的网络的图片：

import pandas as pd
df = pd.DataFrame({'fld1': ['a',    'a',    'b',    'c',    'c',    'g',    'd',    'd',    'e',    'e',    'f']
                ,  'fld2': ['b',    'c',    'f',    'd',    'g',    'd',    'e',    'b',    'c',    'f',    'b']
                , 'r_val': [0.1,    0.9,    1,  0.5,    0.5,    1,  0.8,    0.2,    0.2,    0.8,    1]})

df
Out[4]: 
   fld1 fld2  r_val
0     a    b    0.1
1     a    c    0.9
2     b    f    1.0
3     c    d    0.5
4     c    g    0.5
5     g    d    1.0
6     d    e    0.8
7     d    b    0.2
8     e    c    0.2
9     e    f    0.8
10    f    b    1.0

我想收缩r_val等于1的边，使df变成df2。这意味着，使 fld1 等于 fld2，其中 r_val == 1。 r_val == 1 在两个方向上的情况（在节点 B 和节点 F 的情况下）例如）删除哪个节点并不重要。

df2 = pd.DataFrame({'fld1': ['a',    'a',  'd',    'd',    'e',    'e'  ]
                ,  'fld2': ['b',    'd',   'e',    'b',    'd',    'b'  ]
                , 'r_val': [0.1,    0.9,   0.8,    0.2,    0.2,    0.8]})

df2
Out[6]: 
  fld1 fld2  r_val
0    a    b    0.1
1    a    d    0.9
2    d    e    0.8
3    d    b    0.2
4    e    d    0.2
5    e    b    0.8

编辑

这将需要迭代完成，直到不再有 r_val 等于 1。当一些边收缩时，它们会产生也可能等于 1 的新边。

Answer 1

不是 pandas 向导，但这是一种似乎可行的方法。

一次迭代将是；

# Find rows where 'r_val' = 1 and replace its 'fld1' with 'fld2' in 
# the entire frame.
df = df.replace(list(df['fld1'][df['r_val']==1]), list(df['fld2'][df['r_val']==1]))

# Eliminate all edges that have collapsed
df = df[df['fld1'] <> df['fld2']]

# Sum up 'r_val' for all edges with the same 'fld1' and 'fld2'
df = df.groupby(['fld1','fld2'], group_keys=1)['r_val'].sum().reset_index()

使用您的数据作为示例运行；

Start:

   fld1 fld2  r_val
0     a    b    0.1
1     a    c    0.9
2     b    f    1.0
3     c    d    0.5
4     c    g    0.5
5     g    d    1.0
6     d    e    0.8
7     d    b    0.2
8     e    c    0.2
9     e    f    0.8
10    f    b    1.0

First iteration:

  fld1 fld2  r_val
0    a    b    0.1
1    a    c    0.9
2    c    d    1.0
3    d    b    0.2
4    d    e    0.8
5    e    b    0.8
6    e    c    0.2

Second iteration:

  fld1 fld2  r_val
0    a    b    0.1
1    a    d    0.9
2    d    b    0.2
3    d    e    0.8
4    e    b    0.8
5    e    d    0.2

没有更多 r_val = 1，我们完成了。

Pandas 中的边缘收缩

Edge Contraction in Pandas

python

graph-theory

pandas