Combinatorial optimization-Typical problem-Maximum stable set problem
Typical problem and execution method
Maximum stable set problem
In the undirected graph $ G = (V, E) $, find the stable set (set of nodes that are not adjacent to each other) with the maximum sum of weights.
Execution method
usage
Signature: maximum_stable_set(g, weight='weight')
Docstring:
Maximum stable set problem
input
g:Graph(node:weight)
weight:Weight attribute character
output
Maximum stable set weight sum and vertex number list
python
#CSV data
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import graph_from_table, networkx_draw, maximum_stable_set
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
t = maximum_stable_set(g)
pos = networkx_draw(g, node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=t[1])
plt.show()
print(t)
result
(5.0, [1, 4])
python
# pandas.DataFrame
from ortoolpy.optimization import MaximumStableSet
MaximumStableSet('data/node0.csv','data/edge0.csv')
| id | x | y | demand | weight | |
|---|---|---|---|---|---|
| 1 | 1 | 5 | 8 | 1 | 3 |
| 4 | 4 | 2 | 2 | 1 | 2 |
python
#Random number data
import networkx as nx, matplotlib.pyplot as plt
from ortoolpy import networkx_draw, maximum_stable_set
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 1)
t = maximum_stable_set(g)
pos = networkx_draw(g, nx.spring_layout(g), node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=t[1])
plt.show()
data
Recommended Posts