[PYTHON] Kombinationsoptimierung - typisches Problem - maximales Schnittproblem

Typisches Problem und Ausführungsmethode

Maximales Schnittproblem

In dem ungerichteten Graphen $ G = (V, E) $ wird angenommen, dass das nicht negative Gewicht $ w_ {ij} $ jeder Seite $ e_ {ij} = (v_i, v_j) \ in E $ gegeben wird. Suchen Sie zu diesem Zeitpunkt $ V_1, V_2 (= V \ setminus V_1) $, das $ \ sum_ {v_i \ in V_1, v_j \ in V_2} {w_ {ij}} $ maximiert.

Ausführungsmethode

usage

Signature: maximum_cut(g, weight='weight')
Docstring:
Maximales Schnittproblem
Eingang
    g:Graph(node:weight)
    weight:Attribut Charakter des Gewichts
Ausgabe
Gesamtschnittgewichte und eine Scheitelpunktliste

python

#CSV-Daten
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)

Ergebnis

(27.0, [2, 4, 5])

python

# pandas.DataFrame
from ortoolpy.optimization import MaximumCut
MaximumCut('data/node0.csv','data/edge0.csv')[1]

python

#Zufällige Daten
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()

Daten

• data/node0.csv
• data/edge0.csv