最大カット問題
無向グラフ$G=(V, E)$において、各辺$e_{ij}=(v_i,v_j)\in E$に非負の重み$w_{ij}$が付与されているとする。このとき、$\sum_{v_i \in V_1, v_j \in V_2}{w_{ij}}$を最大にする$V_1, V_2(=V \setminus V_1)$を求めよ。
実行方法
usage
Signature: maximum_cut(g, weight='weight')
Docstring:
最大カット問題
入力
g: グラフ(node:weight)
weight: 重みの属性文字
出力
カットの重みの合計と片方の頂点番号リスト
python
# CSVデータ
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import graph_from_table, networkx_draw, maximum_cut
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
t = maximum_cut(g)
pos = networkx_draw(g, node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=t[1])
plt.show()
print(t)
結果
(27.0, [2, 4, 5])
python
# pandas.DataFrame
from ortoolpy.optimization import MaximumCut
MaximumCut('data/node0.csv','data/edge0.csv')[1]
| id | x | y | demand | weight | |
|---|---|---|---|---|---|
| 2 | 2 | 10 | 5 | 0 | 1 |
| 4 | 4 | 2 | 2 | 1 | 2 |
| 5 | 5 | 0 | 5 | 1 | 1 |
python
# 乱数データ
import networkx as nx, matplotlib.pyplot as plt
from ortoolpy import networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 4)
for i, j in g.edges():
g.adj[i][j]['weight'] = 1
t = maximum_cut(g)
pos = networkx_draw(g, nx.spring_layout(g), node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=t[1])
plt.show()
