Combinaison optimisation-problème typique-problème d'ensemble stable maximum

Problème typique et méthode d'exécution

Problème de jeu stable maximum

Dans le graphe non orienté $ G = (V, E) $, trouvez un ensemble stable avec la plus grande somme de poids (un ensemble de nœuds qui ne sont pas adjacents les uns aux autres).

Méthode d'exécution

usage

Signature: maximum_stable_set(g, weight='weight')
Docstring:
Problème de jeu stable maximum
contribution
    g:Graphique(node:weight)
    weight:Caractère d'attribut du poids
production
Somme de poids d'ensemble stable maximum et liste des nombres de sommets

python

#Données CSV
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)

résultat

(5.0, [1, 4])

python

# pandas.DataFrame
from ortoolpy.optimization import MaximumStableSet
MaximumStableSet('data/node0.csv','data/edge0.csv')

python

#Données aléatoires
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()

Les données

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